JOI夏季セミナー2018参加記
夏季セミナー2018参加記
去年に引き続き夏季セミナーに参加してきたので参加記を
SuperConに参加していないので夏休み唯一のなんか競プロ系のアレな気がする
受験生がそれなりに来ていて嬉しかった
一日目
IOI金メダリスト(予定 確定!!!)(プレッシャーをとてつもなくかけていく)等3人と僕で新宿でラーメンを食べる
当ブログはIOI日本代表を応援しています
豚骨ラーメン～レッドコーダーを目指して～ pic.twitter.com/XXUEO7Q4S6
— 迷路 (@pazzle1230) 2018年8月15日
どっかを経由してバスに乗ってこれから4泊5日を過ごす何とかっていうところに行く
集合場所に行くと部屋に最大人数入れるようにするマラソンマッチで最適解みたいな感じに机と椅子が並んでいた
しかしレッドコーダーの温床だったので最適解を超える解が出てきて机と椅子が並び替えられた
最初の配置明らかにおかしくて，大人数を部屋に入れる気がなかった
自己紹介とかあり，IOI日本代表(非公式含む)8人のうち7人がいてすごいと思った
本はいろいろあって，暗号理論以外だったら何でもいいなという気持ちでグラフ理論にしたけど
もうちょっと読んでみたら暗号理論でも普通に良かったなみたいな気持ちになった
グラフ理論にした決め手は，チューターがよく知らない人だけどすごそうなオーラが出ていたからなんですが
その後本ごとにそれぞれの部屋に別れた後
ぼく「...」
チューター「...」
ぼく「...」
チューター「...」
みたいなことをする，これから5日間お世話になる人なのでコミュニケーションは当然欠かせない
チューターによる基礎用語と基礎知識解説みたいなのを聞いてなるほどなぁとなる
その後適当に読んで自分がやりたい章を決めるみたいな感じになって，彩色を選んだら五人の内
僕しかいなかった．平面グラフは三人いたので幾何できない僕はプロだなぁという気分でした
まあ数学ができるので一人だけの章の人がもう一人いることがわかるのでわかる
夕飯の量が多いんですよね
正直この時点であのとても有名な五色定理をやろうと決めていたため余裕やろみたいな気分になってた
まあ当然これは嘘でコンピュータを使って証明が何ページにも渡ったと言われているので5日では不可能なんですが僕は天才なのでできます．
4という数字は不吉なので僕は知らないことにしています．
セミナーが終わったところで風呂に入りボードゲーム大会が始まる
カルカソンヌとかして，せっかくSwitchがあるので某先輩所持のマリカーやぷよテトをした
多分寝たの三時か四時，何してたか忘れましたが
二日目
朝ごはんを食べる
去年と変わってなくて飽きたことに気づく
セミナー，読むだけ
講義，当然機械学習に興味があるので寝るわけなく真剣に聞く
前半寝ていて後半理解できなかった，悲しい
セミナー読むだけここらへんで多分普通の五色定理の証明を読み終わる
もういいのでは？みたいな気分になりながら読み続ける
夕飯食べる，当然昼飯はもう食べている
読む
終わり
何したか忘れたけどどうせボードゲームをしている
スタバ行ったしTwitterに上げてるかなと思ったら上げてなかった
確か寝たの四時
三日目
朝ごはんは飽きているので食べなかった
今ドキの女子なのでスタバだけでお腹いっぱいになるため
読む
ここらへんでもう一つの五色定理の証明方法がでてきてそっちを発表にしようという気持ちになる
多分ここらへんで少し競プロをした
チューターの人，まあ大悪魔専門家の人なんですがサイクル基底とかの話をしてたので聞いた
ミュージカル鑑賞が趣味の人に質問することでなんとか彩色の章を読み切った
やったぜ
夕飯たべるよね，昼飯は食べてる
交流なので交流する
カルカソンヌとかお邪魔者とかをやった気がする
コードネームで戦犯かましたのこの日だった気がする
イマドキの女子なので当然スタバに行く
明日の徹夜に備えて健康的な生活✌️ pic.twitter.com/FzLk3BYI1J
— 迷路 (@pazzle1230) 2018年8月17日
海辺で飲んだいつもの味を感じた
この日も寝たの四時ぐらいなのかなぁ...そんな事ある？流石に違う気がする
ツイートから寝た時間考えようとしても10:34とか表示されてておかしい，セミナー中に流石にスタバは行かない
四日目
朝ごはんはね，お気持ちをするとNo subで終わる
発表準備
iPadProを使ってイキりながら作っていくけど遠くからだと線とか見にくかったらしいですね
そうなる雰囲気は感じてたけど突っ切ってしまった
昼飯を食べる，夕飯はまだ
講義
当然量子コンピュータに興味があるので聞いていた
すごいよね，量子コンピュータ，見た目がかっこいい，マリオメーカー おやすみなさい
講義してくれた人に見られたら○されるのではないかという不安がわりとすごい
発表準備の時間で当然みんなスライドを作り終わる
Writer:双子なABCがあるので当然出て全完する
当然発表準備終わってないので風呂に入った後作り続ける
チューターの方々がボードゲームする相手がいなくて帰ってしまい悲しい気持ちになった
Kmc○deくんとか○ni○nくんがコドフォ出るって言ってたので一緒に出ようとAを提出してWAする．人生終了
Kmc○deくん達の調子を適当に聞いたらコドフォ出てなかった．なにかがおかしい
このままレートを下げて人生終了です．お疲れ様でした
最後の晩餐 pic.twitter.com/ksnAdq5piZ
— 迷路 (@pazzle1230) 2018年8月18日
財布が写真に写っているのは，写真に財布を写すことでなくした財布を見つけた人がいたからですね
みんな死んだ目でスライドを作り続けていて，作り終わった人からボドゲみたいな感じになってた気がする
僕が持ってきたけど出し忘れていたコヨーテもやった
そういえば一〜四日目のどっかで人狼をしました，いつだったかは忘れました
最終的にチューター三人？と参加者四人？ぐらい？だった気がする
流石に書くのが遅すぎて記憶曖昧すぎた
ワードバスケットとコヨーテだけやりました
2つしかやってないからね
この日は何時ぐらいに寝たんでしたかね
五日目
寝てないんですけど
寝てないので当然そのまま朝ごはんも最終日だし食べに行った
2つのボードゲームでN時間消えた事実が怖すぎて怖い
発表ね
他の人達の発表は当然楽しみだったのでワクワクしながら 寝ていた 見ていたんですけど
面白すぎて気づいたら半分終わって昼飯になっていた 本当に一瞬で終わったのでびっくりした
感覚的にはまばたきしている間に終わっていた感じでした
なんか午後の発表が始まってすこししたら三人組が発表を聞きにやってきた
ここでIOI代表が8人揃っているわけなんですがすごい，なんのイベントなんですかね
情報オリンピック委員会のイベントなんですが
自分の発表，去年もそうだったんですが本に書いてることそのまま詰め込んで詰め込むだけみたいな
なんの理解の助けにもならないものになってる感じがあって悲しい
発表に使ったスライド
10分って短い気がする
流石に午後は全部起きれたけど普通に難しくてなかなか理解できないね
まあわからないのでただ座り聞き続けるだけの人と化していた
終わった後，某チューター等数人でカラオケにいった
IOI代表三人の歌声を聞けるというすごい体験でした
僕はなぜか夏季セミ途中から喉が死んでいてやばかった
夕飯としてラーメン食べました
夏季セミ期間で何回ラーメン食べたんですかね，すごい
大学生になったらこういう機会がなくなりそうなので悲しい，来年も参加者として参加したい
JOI'18春合宿参加記
JOI春合宿2018
JOI本選通ったため春合宿に行ってきました
これを書いているとき僕はまだ春合宿中です
何日目かあててみてください
文章の変化とかから頑張ればわかりそう
一日目
部活のえんやこらをした後に東大に入ってパスタを食べて偏差値を上げる
データセンターについた後、プラクティスを頑張る
1. なんかコミュニケーションなんですがコミュ障なのでなかなか通らない
2. エスパーなんですが、超能力者なので3回ぐらいで通る（超能力者なので）
3. Output OnlyなんですがOutputする、LinuxかCに慣れてないと厳しそう
4. 電 子 レ ン ジ 4問目なので当然一番難しい
この後オリセンに行き講義を受ける
簡潔データ構造面白そうとなるけど途中までだったので悲しい気持ちになる
頭がないので計算量とてつもなく気持ち悪いと思いました
ねる
二日目
起床できる
朝ごはんに向かうとめっちゃ混んでいる、やばい
社会性の塊なのでバスの出発時間には当然間に合う
競技1日目が始まる
一問目
木で頑張ろうみたいな
何もわからず何もわからなかったため何もわからなかった
部分点だけセグ木で取る
二問目
幾何で頑張ろうみたいな
とりあえず部分点だけ取ろうとしたらめっちゃバグるためめっちゃバグる
終わる
三問目
整数二個はやばいためやばい
横に置くのと縦に置くのとそのまま置くのの数を全探索$O(N3)$を書く部分点ですね
そのまま置くのを高速化すれば嬉しそうみたいなことが分かる
sum(nCk * 4k * mPk)みたいな感じで二項定理とかで頑張ろうとするけど無理
ところで、そのまま計算することが小さければできるのでテーブルっぽく表示させて眺めます
なんか遷移が見えます（超能力者なので）
そこをDPにすることでなんとか満点がとれます
16+0+100でした
講義を受ける
双対難しいんですが慣れない5時間コンテストの疲れから序盤で寝てしまい途中から覚醒するも何も理解できないやつをする
解説
ねる
三日目
朝ごはんに行くとめっちゃ混んでいる（前日比INF倍、階段で下の階まで及んでいて何が起きているんだとなる）
社会性に満ちているのでバスの出発時刻+5分ぐらいに着く
競技二日目
一問目
整数二個じゃ～ん
眺める
わからないねと思い二問目三問目をやってきてから解く
わからなすぎるため小課題1の全列挙を書く
わからないね
全列挙ということは小さければ計算できるね
テーブル表示させよっか
にらみます
dp[i][j] = dp[i-1][j]*j+dp[i-1][j-1]*(i-j+1)という遷移が見えます（超能力者なので）
流石にレッド超能力者にはブルー超能力者なので及ばず部分点で止まりました
二問目
Output Only
完全に見た目がマラソンだったので最初に焼きなましか山登りを書いて時間内回そうみたいな気持ちになる
実装がバグって2時間半ぐらいかかる（vectorはeraseすると添字ズレするのに気づくことできないね）
回すけどすぐ更新止まるし頂点がかたまっていて乱数バグってんじゃーんとなる（解説情報ですが本質です、青なので気づけない）
まあそのまま何回か実行して出しまくるとある程度取れる
裏で回すと重くなるためやるべきではなかった
三問目
難しくないですか？難しいと思います
前に人の1後ろに行くことにしばらく気づかずなんか詰まる
それに気づいたらなんか座標+iが嬉しそうなことに気づいてO(1)で出せるように頑張りにぶたんする
なんか定数倍か何かがきつすぎたのか、scanfやprintfに直しても通らずlong longをintにしたら通った
49+54+100=203でした
講義を聞く
純粋関数型データ構造
怖いね
解説を聞く
一問目がわからない
寝る
四日目
朝起きる
前日の教訓を活かして早めに向かう
あまり並ばずにすむ（並ぶ）
社会性が高いのでバスの集合時刻に間に合う
競技三日目
一問目
コミュニケーション
与えられた頂点に番号がついているグラフを、頂点に番号がついていないグラフで表現しろみたいな問題
無向グラフだと考えることで頑張ってとく
有向グラフなので簡単に解けるらしくキレる
二問目
びたろうくんだれやねん
DAGなのでダイクストラで部分点を取ろうとしてTLEになってハマるを無限時間続ける
DAGなのでDPで出来る
部分点が取れる
満点思いつきたかったね
三問目
パット見簡単枠現実不可能枠
お気持ちになることで小課題1解法で小課題2まで通す
終了
やばDP書くけど重複して数えていることに気づき死ぬ
講義を聞く チューターが少ないことが印象的でした
解説を聞く
三問目理解できない
寝ます
五日目
起きる
もう全然混んでいない
余裕のバス搭乗AC
一問目
2乗DPを書きます。部分点を得られます
セグ木DPを疑いながらわからないため諦めます
二問目
リアクティブですね
補集合で二分探索を疑うとわかりかけるけど考察して実装始めると記憶が消えるため何もわからない
終了
三問目
グラフ、全点始点でうまくダイクストラを前計算して良さそうなのいくつか持てば良さそうとなる
部分点1しか通らなくて終了する
8+19+12=39
春合宿に感謝を告げて終了
サンキュー春合宿
二問目、春合宿中に1か2を争う簡単さっぽくて人生終了
通してたらJAPAN2だったんだよなぁって永遠に言い続けて死んでいきます
六日目
チューター企画のSKIコンビネータがある
純粋に難しいため難しく、異世界の科学を異世界の言語で学んでいる気分になっていた
面白いので頑張りたかったけど圧倒的に頭が足りなかった
地頭の塊になりたかった
まあここまでで実質終了なため終了
五、六日目の夜にワードバスケットやコードネームをやって楽しみました、楽しかった
JOI'18本選参加記
JOI本選参加記
JOI予選通過したため本選に行ってきたので参加記をたくさん書きます*1
結果としては100-100-13-31-5で249点でした、ボーダー上という雰囲気を感じてどっちに転ぶかわからず怖いです
とりあえず落ちたという暗示をかけて落ちても楽な気持ちで、通ったらとてつもなく幸せになれるようにしておきます
前日
宿泊をするため荷造りがある
夏季セミとは違い1泊のため難易度は下がっているが少なくとも7はあるため辛いがPCKなどで鍛えたので日が変わってからAC
これもう前日じゃないね
1日目
お昼ごはんを食べることにして食べるが、他の人は土曜日なのに学校があるらしくそれまで世界史を勉強する
全然進まない
難易度7を通す気持ちになりStrapを読む
一瞬わからない
しばらくわからない
家をでるぐらいになってようやくわかるけど難易度7でわからないのはまずい
お昼を食べる
うどんにわさびを全部とかしたら結構きつかったため全部溶かすのがおすすめです
TXに乗る
オタクなのでTXでパソコン広げるオタクになりStrapを実装する
バグる
結局通せないままつくばにつく*2
荷物をおいてプラクティスに行く
プラクティスの問題が開始前に見ていいらしいので見ると問題名から去年と同じとわかる
余裕をぶっこいて問題文見ずに開始を待つ
始まる
1問目、2問目、3問目までやるだけなのでやる
ここらへんで通ってるか確認しに行くと1問目が通っていない、オーバーフローです、人生終了
4問目をあー去年もやし先輩めっちゃバグらせてたやつだ！と言いながら書く
バグらせる
なんとか時間めっちゃかけて通す
5問目は半分全列挙なのでやるだけと言いながら書く
バグる
なんかupper_boundで添字-1したんですが謎の値が出るためM越えるかを場合分けして逃げる
終わったため他の人のところへ行くと、◯◯◯oooさんにEmacsというゲームソフトを教えてもらう
色々あってほんとすごい、Vimと敵対しているエディタだと思ってたけどゲーム機だったんですね
講義始まる
去年より良さげなところでやり、椅子で隠れるためどう考えても精進が出来る(JOI委員会の人へ、許してください)
Strapをなんとかして通し、EnJOIable logo designを通す
Telegraphを解説見ちゃったけど実装したい気持ちになるのでやると全然出来ないため死ぬ
講義終わる
多分夕ご飯
色々食べる
WAと書かれた名刺をもらうため終わりを確信する
食べ終わる
去年の教訓を活かし、即風呂をするとみんプロにより余り混んでいないことがわかりAC
風呂を上がったらもやし先輩の部屋に集まり何か考察しようみたいな感じになるけど雑談で終わる
一方僕はTelegraphが実装できない
0時を回ったため寝る
なかなか寝付けず、天井の緑の光に苛立ち始める
気づいたら寝ていた
二日目
目覚ましを6時半にセットしたはずが5時に起きる、眠気がやばい
とりあえずお腹痛めていたためトイレに行く
その後適当に時間つぶして食堂に行くとめっちゃ混んでてなんで競プロerがこんなに時間守ってるんだとなる
去年より鮭の塩加減は良くなっててよかった
本選会場に行く
なんか緊張ヤバイけど頑張るみたいな気持ちになる
始まる
1問目
うーん...やるだけ
2問目
うーん...頭良く出来そうだけど頭ないのでRMQで殴る
ここらへんで易化しすぎでしょ、やばやばってなる
3問目
おいおい苦手なやつ来たぞコレとなる(cf. yukicoderの双子のどっちか回のトランペットか何か)
グリッド状でうまくやるやつ苦手なのでとりあえず貪欲を書いてしまう
なんか部分点1が通る
ここで天才なので縦に使うときと横に使うときでしかブッキングせず、ブッキングした同士を辺で結ぶと二部グラフになることに気づく
この瞬間、フローシラバス外では...みたいな気持ちが何処かに消える
そしてhttps://beta.atcoder.jp/contests/soundhound2018/tasks/soundhound2018_cとhttps://mathtrain.jp/bipartitematchingが頭の中に入ってくる
フロー書けないため増加道探すの頑張ってかくぞ〜！ｗとなる
1時間がとける、なんか書けたつもりになってもWAなので無理っぽいとなり諦める
トイレに行く
あっ、DPでは？となり頭の中が昔の予選6のbitDP達で一杯になるも、右に遷移していくと流石に情報持ちきれないやろとなる(必要な情報がななめなので)
諦め
本選後の解説で斜めに遷移すればいいと言われ衝撃が走った
それはそうみたいな感じだけど常識覆される感があった
4問目
見る
4問目のグラフなんて難しいに決まってるやんけ...となる
けどどう見てもダイクストラは使いそうな雰囲気あるし行けそうみたいになる
部分点オタク精神を発揮して部分点1を見る
SとU一緒なら一番後ろの分岐点までの最短路を引けば行けるねとなる
ここでなんかスパゲティを書くことで同時に部分点2も同時に通る(なんで通ったかわかりません)
部分点3を見ると、ワーシャルフロイドやってくれ感バリバリに出ているため書きたくなるため書く
もしかしてこの部分点は全経路列挙してそれぞれに試せということなのでは？みたいな気分になりDFSを書く(おそらく間に合いません)
トイレに行く
書くとワーシャルフロイド意味ないなという気持ちになるためS,U,Vを始点にダイクストラをする
そして、経路復元しながら見ていったとき、ある頂点以降でUから、Vからの最短がわかるためメモ化DPできるのではとなる
PLLである頂点以降でのUから、Vからの最短の和が最小になるような組を持つ
行けるやろこれみたいになるもめっちゃバグる
なんかシグナル11とか行って全部REっぽくなったりもする
残り30分ぐらいでなんとなく致命的なバグはなくなるけど答えあわない
なんか明らかにおかしいところがあったので直す
部分点オタクのため関数に分けてたのもなんとなくmainに全部やる
残り10分ぐらいで、Uからの最短が最小、Vからの最短が最小、Uからの最短とVからの最短の和が最小の3つを持たないといけないことに気づき実装する
手が震え、日本語配列キーボードのためミスタイプが増える
13:00ちょい前ぐらいに最低限かけた気がしたので最終提出†ファイナルサブミット†をする
手元でコンパイルするとCEが出る、人生終了
帰りの電車の中で直してオープンに出すと通る、後5,10分ほしかったね
5問目
どこかの間で5点だけ取って退散した
包除原理と高速ゼータ変換こわいね
後二日ぐらいで結果出ると思うのでぼーっと待ちます
テスト勉強をする気は起きません
どっちかというと競プロやりたい
並列二分探索（パラレルバイナリサーチ）
パラレルバイナリサーチ（並列二分探索）
CODE THANKS FESTIVAL2017Hが想定解はLCAでしたが並列二分探索でも解けるらしいのでやりたくなりました
並列に二分探索したくない？したいね
基本的にはこのブログをというかすべてです
英語読める人、圧倒的にそっち読んだほうがいいと思います。そして僕に教えてください
一般にQ個のクエリがあるとき、N人のメンバーそれぞれについていくつ処理したときに条件が満たされますか？という問題っぽい
普通に愚直にやると一個クエリ処理、N人調べる、もう一個処理...となりO(NQ)となりますね（実際にはクエリ処理計算量がコレにかかります）
目標としてはO( (N+Q) log Q)だと思います(クエリ処理あたりの細かいやつは無視です今は)
ここで何も考えず一人ずついくつクエリが必要かを二分探索するとO(NQ log Q)になります
明らかに悪化しているんですが並列二分探索って言ってるしN人同時に二分探索行えば軽く収まりそうですね
意味がわからないね
それぞれの人に対しlo[i]とhi[i]を持ちます、意味するところは察してください
すると一回一回のループである人が条件を満たしているか調べるのは(lo[i]+hi[i])/2個クエリを処理したときだけでいいので全部でN回ですね
そして一回一回クエリも全部処理するのでO(N+Q)となります
二分探索なのでこれにlog QがかかってO( (N+Q) log Q)になるのでうれしくなります
なんかよくわからないね
Meteors(SPOJ)
ブログで題材にされている問題です
まあ解かないとダメだろうとなり解くことにします
問題概要
N人のメンバーとM個の区画があり、N人にM個の区画が振り分けられています
この区画は環状につながっています
誰がその区画を担当しているかはO_i(1 ≤ i ≤ M)(1 ≤ O_i ≤ N)として与えられます
また、それぞれのメンバーが担当する区画に合わせてP_i(1 ≤ i ≤ N)(1 ≤ P_i ≤ 109)個の隕石が降り注ぐ必要があります
K回、L_i〜R_iまでの区画にA_i個ずつ隕石が降り注ぐというクエリが与えられます
それぞれのメンバーは何回目の隕石落下で目標を達成できるでしょう
解法
区間加算の点取得がBITで楽にできることをこれの解法を見てて知りました（区間加算区間和を考えればまあ自明っぽかった）
それぞれのクエリはBITを用いてL_iにA_iを、R_i+1に-A_iを足すことで達成できるのでQ個合わせて(O(Q log M))
それぞれの人について達成しているかは担当している区画全部見て和を調べるしかないので全員合わせてO(M log M)ですね
この二つを全部でlog Q回行うためO((Q + M) log M log Q)となります（あってるんだろうか）
めんどくさいのでchangedを持ち、変化なくなったら終了としました
実装としてはmid[(lo[i]+hi[i])/2]にiをpush_back
REP(q, k)を回してクエリ処理していき、mid[q]に入っている人を調べていきます
そうすればそれぞれの人について一回しか見なくて済みますね
このとき、その人の担当する区画を全部見て足すわけですが、最悪ケース考えるとなんと1018余裕で超えます、N WAしました悲しいね
その人の目標値を超えたタイミングでbreakしましょう
下のコードのBITは0indexedにしてます
int n, m, k; ll p[314514]; vector<int> o[314514]; int l[314514], r[314514], a[314514]; int hi[314514], lo[314514]; BIT bit; void apply(int k){ if(l[k] > r[k]){ bit.add(l[k], a[k]); bit.add(0, a[k]); bit.add(r[k]+1, -a[k]); }else{ bit.add(l[k], a[k]); bit.add(r[k]+1, -a[k]); } } int main(void){ cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m; REP(i, m){ int O; cin >> O; O--; o[O].push_back(i); } REP(i, n) cin >> p[i]; cin >> k; REP(i, k){ cin >> l[i] >> r[i] >> a[i]; l[i]--; r[i]--; } REP(i, 314514){ lo[i] = 0; hi[i] = k; } bool changed = 1; while(changed){ changed = 0; bit = BIT(m+1); vector<int> mid[314514]; REP(i, n) if(lo[i] != hi[i]) mid[(lo[i]+hi[i])/2].push_back(i); REP(q, k){ apply(q); for(auto mem : mid[q]){ changed = 1; ll sum = 0; for(auto sec : o[mem]){ sum += bit.get(sec); if(sum >= p[mem]) break; } if(sum >= p[mem]) hi[mem] = q; else lo[mem] = q+1; } } } REP(i, n){ if(lo[i] >= k) cout << "NIE" << endl; else cout << lo[i]+1 << endl; } }
Code Thanks Festival 2017 H - Union Sets
えー本番解けなかったのでね
LCAかけないからそっちも書くべきっぽいので並列二分探索書いた後書きます
問題概要
N個の集合のうち、ある二つの要素が属している集合を併合する操作をM回行います
このとき、要素X_iとY_iが何回目の操作で同じ集合に属すかという質問クエリがQ個与えられます
答えてください
解法
これも単純に考えたらO(MQ)ですね
質問の方がクエリになってますが実質クエリは操作の方ですね
並列二分探索によりO((M+Q) log M)になります（UnionFindの計算量は軽いから無視します(あの記号よくわからないので)）
int N, M, Q; int a[114514], b[114514]; int x[114514], y[114514]; int lo[114514], hi[114514]; int main(void){ cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M; REP(i, M) cin >> a[i] >> b[i]; cin >> Q; REP(i, Q){ cin >> x[i] >> y[i]; lo[i] = 0; hi[i] = M; } bool changed = 1; while(changed){ changed = 0; Union_find uf(N+1); vector<int> mid[114514]; REP(i, Q) if(hi[i]!=lo[i]) mid[(lo[i]+hi[i])/2].push_back(i); REP(i, M){ uf.unite(a[i], b[i]); for(auto q : mid[i]){ changed = 1; if(uf.same(x[q], y[q])) hi[q] = i; else lo[q] = i+1; } } } REP(i, Q){ if(lo[i] >= M) cout << -1 << endl; else cout << lo[i]+1 << endl; } }
明らかにこっちのほうが簡単だね
これから並列二分探索の問題は解いていきたいね（そんなたくさんでなさそう）
JOI2017/2018予選
JOI2017/2018予選
いよいよ待ちに待った予選ということで皆さんどうだったでしょうか
僕は2:00からモンハンワールドをやり、3:30就寝、9:00起きという規則的な生活を行いコンディションを整えました
多分発売されたらMHW買うと思います
予選開始直前にはコンビニへ赴き(5回(1回誤解に変換されて悲しい)ぐらい趣に変換されて悲しい)カフェラテとチョコを買いました
美味しかったです(飲食してる暇ありませんでしたが)
1問目
微誤読を行い場合分け必要そうな微難を感じたため読み直すと必要ないとわかる
int main(void){ cin.tie(0); ios::sync_with_stdio(false); int N, A, B, C, D; cin >> N >> A >> B >> C >> D; cout << min((N+A-1)/A*B, (N+C-1)/C*D) << endl; }
2問目
なんかいつものだなぁという気分になるので数えて+1する
int main(void){ cin.tie(0); ios::sync_with_stdio(false); int N; int m[110] = {}; int sum[110] = {}; cin >> N; REP(i, N) cin >> m[i]; int res= 0; REP(i, N){ if(m[i]) sum[i+1] = sum[i]+m[i]; else sum[i+1] = 0; res = max(res, sum[i+1]); } cout << res+1 << endl; }
3問目
何も考えず全探索
何も考えないので2問目より簡単そう
int main(void){ cin.tie(0); ios::sync_with_stdio(false); int H, W; int A[30][30]; cin >> H >> W; REP(i, H){ REP(j, W){ cin >> A[i][j]; } } ll res = INF_LL; REP(i, H){ REP(j, W){ ll sum = 0; REP(s, H){ REP(t, W){ sum += min(abs(s-i)*A[s][t], abs(t-j)*A[s][t]); } } res = min(res, sum); } } cout << res << endl; }
4問目
DPの添字どう取るか迷いはじめて迷う
dp[i][j][k] := i個目まで見ているときにi-j個目からi個目までが繋がってて最小値kのときの差
みたいなのをやりたくなるけどなんかkが大きくなりそうみたいな気持ちになり不可能ではみたいな気持ちになる
そこで最大値の最小化であることに気づく
二分探索だね！*1
適当に差の限界を決めると、左端を固定したらその範囲に収められるかを典型DPで出来ることに気づく
ここで左端はsum(Li)/2+1ぐらいまでで良さそうなのでそうする
int N; int L[1010], sL[1010] = {};; bool isok(int len){ FOR(mini, 1, sL[N]/2+1){ bool dp[52][52] = {}; dp[0][0] = 1; REP(i, N){ REP(j, i+1){ dp[i+1][j+1] = dp[i+1][j+1] | dp[i][j]; int l = sL[i+1]-sL[i-j]; if(i == N-1 && j == N-1) continue; dp[i+1][0] = dp[i+1][0] | (dp[i][j] && mini <= l && l <= mini+len); } } if(dp[N][0]) return 1; } return 0; } int main(void){ cin >> N; REP(i, N) cin >> L[i]; REP(i, N) sL[i+1] = L[i]+sL[i]; ll l = 0, r = 1000, m; while(r-l > 1){ m = (l+r)/2; if(isok(m)) r = m; else l = m; } cout << (isok(l) ? l : r) << endl; }
5問目
あーダイクストラね、はいはい、いつもの五問目*2、となる
ある地点までの距離dとそこに行けるようになるまでの時間tを持てば移動にかかる時間がわかりできそうとなるができない
なんか切りたいやつまでの距離によってtとdどっちが小さいほうが嬉しいか変わることに気づく
その地点までの距離dによって最短時間tが求まるねとなるので拡張ダイクストラっぽくやりたくなるのでやる
実質ヘビのJOIくん
int H, W; int A[31][31] = {}; ll dp[31][31][911] = {}; int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0}; PLLL mkpll(ll a, ll b, ll c, ll d){ PLLL p = {a, {b, {c, d}}}; return p; } int main(void){ cin.tie(0); ios::sync_with_stdio(false); cin >> H >> W; REP(i, H){ REP(j, W){ fill(dp[i][j], dp[i][j]+911, INF_LL); cin >> A[i][j]; } } priority_queue<PLLL, vector<PLLL>, greater<PLLL> > pq; pq.push({0, {0, {0, 0}}}); dp[0][0][0] = 0; while(pq.size()){ ll t = pq.top().fs, d = pq.top().sc.fs, y = pq.top().sc.sc.fs, x = pq.top().sc.sc.sc; pq.pop(); REP(i, 4){ if(y+dy[i] < 0 || x+dx[i] < 0 || y+dy[i] >= H || x+dx[i] >= W) continue; int yy = y+dy[i], xx = x+dx[i], tt = (d*2+1)*A[yy][xx]+t; if(dp[yy][xx][d+1] > tt && d+1 < H*W){ dp[yy][xx][d+1] = tt; pq.push(mkpll(tt, d+1, yy, xx)); } } } ll res = INF_LL; REP(i, 911){ res = min(res, dp[H-1][W-1][i]); } cout << res << endl; }
タプル使いたいなぁとなった
6問目
最初最小値だと思って簡単かも！となるがK番目だと気づく
調べたらなんかBITとかでできそうとなるためそれで39点取れる(ここで相当手間取った)
冷静に考えると想定解O(N log N)だろうしにぶたんが何処かで関わってくるだろという気持ちになる
適当に値Xを決めると、X以下の数がK番目の数になる区間の数はO(N)ぐらいで求められそうなことに気づく
この時点で残り15分ぐらい
焦って書くけど間に合わないね
終わった後考えたけど判定関数がうまくいってなさそうなのにどこがダメかわからない
誰か助けてください
int N, K, L; ll cnt[214514] = {}; vector<ll> a(N); bool isok(ll x){ int r = 0; ll cnt = 0; ll sum = 0; REP(l, N){ while(r < N && cnt < K){ if(a[r] <= x) cnt++; r++; } if(cnt < K){ return sum >= L; } sum += N-r+1; if(a[l] <= x) cnt--; } return sum >= L; } int main(void){ cin.tie(0); ios::sync_with_stdio(false); cin >> N >> K >> L; a.resize(N); REP(i, N) cin >> a[i]; ll sum = 0; int l = 0, r = N+1, m; while(r-l > 1){ m = (l+r)/2; if(isok(m)){ r = m; }else{ l = m; } } while(!isok(l)) l++; cout << l << endl; }
360点だった去年とは違いドキドキしなくて済みそうなので気が楽
自明な部分点は6問目の6点だけな気がするので(部分点だけで考えてないからわかんないけど)
ボーダーは306+αかなという気持ち
PCK2017本選参加記
パソコン甲子園本選に地域枠として行ってこれたので参加記的なのをホント適当に
一日目
朝起きたら東京駅に向かう
新幹線が8:45分発ぐらいなのに7:45ぐらいについて時間が有り余る
新幹線に久しぶりにのったけどすごいですね
とても快適だった
郡山についてそこから普通の電車でまた一時間ぐらいで会津若松にいく
ここらへんで師匠を拝見することができて徳を高めた気分になる
バスの場所に行くとすでにたくさんの人々がいた
競プロ界隈と関わりのない相方がいるので交流をとても控える（コミュ障なだけ）
会津大学に着く
開会式が堅苦しくてマジかってなる
本選開始
1問目2問目3問目とやるだけを処理するマンになる
4問目は相方が考察してくれたのでうぇい
5問目も相方が考察してくれたのでうぇい
6問目も相方が考察してくれたのでうぇい
7問目も相方が考察してくれたのになんか実行時間間に合わない気分になって実装せず死
8問目も相方が考察してくれたけどbeetさんの幾何ライブラリのEPSがアレだったらしく死
9問目以降は絶望なので終了
どう考えても7問目は解けたね（時間有り余ってるんだから実装するべきだった）
本戦系実力が出るのでとてつもなく苦手
よく見なくてもぼくほとんど何もしてないので悲しいね
交流会で開会式みたいなのが堅苦しすぎて誰か貧血で倒れて早く終わらせてくれという気持ちになる
情報系高校生の貧弱さを考えてほしい
ここらへんで相方を放って適当に交流し始める
WA_TLEさんを初めてしっかり認識しました
夜
みんなとおしゃべりしたい気持ちがあったけど眠さとかに負けてねてしまった
2日目
起床AC
朝ごはんAC
荷造りAC
集合AC
忘れ物AC
会津大学から歩いてホテルまで取りに行く
おもったより遠くてつらくなった
途中で会津バス(5)北柳原(7)「ラーメンの広告みたいなものがここに入る」(100)の写真をとった
音の響きが和を感じさせる五七百で素晴らしいと思った
ついたら暇なのでVRゴーグルを作る
後にこれがいたるところでかさばり邪魔となる
豚汁とおにぎりをどうせちょっとだろと思いもらう
普通に多くておなかがたぷたぷになったたぷ
解説を聞きに行く
相方の考察大体合っててこれ完全に俺戦犯なのではみたいな気分になり始める
終わった後ヅ大生が集まってたので話そうと思ったがコミュ力の欠如により無理だった
おそらくここで話しとけば今日のARC-Dがとけたんでしょうか
記念撮影して閉会式になる
思ってたより開会の偉い人たちの言葉が短くてやるじゃんとなる
入賞者全員が前に出て表彰されるので長くて眠くてやばになる
なんかみんな1万円以上もらってるのではみたいな気分になり悲しくなる
終了する
beetさんと少しだけ話す
コドフェスパーカー黒だと思ってたのでそりゃ見つけられねえわとなる
なんか思い描いていたbeetさんとなんか違った
かえる
帰りにラーメンを相方と食べる
帰宅
強連結成分分解とARC030C-有向グラフ
強連結成分分解
パソコン甲子園予選お疲れ様でした
僕は7問目で詰まって時間を溶かした結果、解けたであろう9問目を解けず7問目すら解けず終了しました
会津オフ会楽しんできてください
ところで10問目が強連結成分分解でしたね
強連結成分分解ということはわかったのですがライブラリ持ってないからと諦めたのでやりました
基本的にはうしさんのを参考にしました
それに、強連結成分をまとめた後のグラフ、それぞれの強連結成分に含まれる頂点の番号を返せるようにしたものがこちらです
class SCC{ private: vector<vector<int> > gg, rg; vector<int> order, comp; vector<bool> used; vector<vector<int> > ng, vs; int n, nn; public: SCC(){} SCC(int v) : gg(v), rg(v), comp(v, -1), used(v, 0), n(v){} void add_edge(int x, int y){ gg[x].push_back(y); rg[y].push_back(x); } int operator[](int k){ return comp[k]; } void dfs(int v){ used[v] = true; REP(i, gg[v].size()){ if(!used[gg[v][i]]) dfs(gg[v][i]); } order.push_back(v); } void rdfs(int v, int k){ used[v] = true; comp[v] = k; REP(i, rg[v].size()){ if(!used[rg[v][i]]) rdfs(rg[v][i], k); } } int build(){ REP(i, n){ if(!used[i]) dfs(i); } fill(all(used), 0); int k = 0; for(int i = order.size()-1;i >= 0;i--){ if(!used[order[i]]) rdfs(order[i], k++); } nn = k; //---------それぞれの強連結成分に含まれる頂点の番号---------- vs.resize(k, vector<int>()); REP(i, n) vs[comp[i]].push_back(i); //----------------------------------------------------------- //---------強連結成分をまとめた後のNew Graph!---------------- ng.resize(k, vector<int>()); REP(i, n){ REP(j, gg[i].size()){ if(comp[i] != comp[gg[i][j]]) ng[comp[i]].push_back(comp[gg[i][j]]); } } REP(i, nn){ sort(all(ng[i])); ng[i].erase(unique(all(ng[i])), ng[i].end()); } //------------------------------------------------------------ return k; } int size(){ return nn; } vector<vector<int> > graph(){ return ng; } vector<int> vertices(int v){ return vs[v]; } };
長いですね
おそらく変数名とか把握できてないので書き換えはもうできません
とりあえず某でverify的なのもしたところ(もとがうしさんのなのでもちろん通りましたが)
某氏に、ARC030Cを解けと薦められたので苦労の末ときました
ARC030C 有向グラフ
ARC-Eの何かしらを解けと言われた後、AtCoderProblemsでこれかな？って開いた後、難しそうだからいっか！みたいに閉じました
後からしっかりこの問題を名指しされたのではいってなって解くことにしました
明らかにSCCなのはわかり、することもわかり、実装も順調に進んでました
大体1時間ぐらいで最初の提出は出来ましたね
その後WAの原因がわからず死んでました
ときにはSCCの部分が間違ってるのではと思うこともありましたが気づきました
dfsの始点を最初に与えられた辺で入次数が0の頂点にしてたんですが、強連結成分が始点になるべきときに死んでました
強連結成分分解後に入次数0の頂点を始点として行えば成功しました(いえい)
解法
- SCC
- 入次数が0の頂点を始点にして以下のDFSをする
- dp[i][j] := 頂点iまでの文字から作ったj文字での辞書順最小の文字列 を持つ
- 各強連結成分ごとに含まれる文字をソートしたものを持つ
- ここで各強連結成分に含まれる頂点の番号を返すやつが役に立ちます
- あとはDAGを辿り一つ前の頂点の情報を元に貰うDPっぽいのをします
- うまく結果を返す方法が思いつかなかったから適当にやってます
- 始点の時はあからさまな例外処理をしてるね
- なんか通る
int n, m, k; char c[310]; SCC scc; vector<vector<int> > G; string dp[310][310] = {}; string res; void dfs(int v, int p){ vector<int> vs = scc.vertices(v); string s = ""; REP(i, vs.size()) s = s+c[vs[i]]; sort(all(s)); if(p != -1){ REP(i, 310){ REP(j, min(i, (int)s.size())+1){ dp[v][i] = min(dp[p][i], min(dp[v][i], dp[p][i-j]+s.substr(0, j))); } } }else{ REP(i, s.size()+1) dp[v][i] = s.substr(0, i); } REP(i, G[v].size()){ dfs(G[v][i], v); } res = min(res, dp[v][k]); } int main(void){ cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m >> k; REP(i, n) cin >> c[i]; scc = SCC(n); REP(i, m){ int a, b; cin >> a >> b; scc.add_edge(a-1, b-1); } scc.build(); G = scc.graph(); REP(i, 310) fill(dp[i], dp[i]+310, string(400, 'z')); res = string(400, 'z'); vector<int> v(scc.size(), 0); REP(i, G.size()){ REP(j, G[i].size()){ v[G[i][j]]++; } } REP(i, v.size()){ if(v[i] == 0){ dfs(i, -1); } } if(res == string(400, 'z')) cout << -1 << endl; else cout << res << endl; }
とても長かった
SCCつらいね
次は2SAT解いた後HL分解やります
