迷いませんか?

プログラミング、電子工作、ゲーム・・・etc、色々やるけど中途半端なブログです。

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_chttps://mathtrain.jp/bipartitematchingが頭の中に入ってくる
フロー書けないため増加道探すの頑張ってかくぞ〜!wとなる
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点だけ取って退散した
包除原理と高速ゼータ変換こわいね

後二日ぐらいで結果出ると思うのでぼーっと待ちます
テスト勉強をする気は起きません
どっちかというと競プロやりたい

*1:"さんかき"をたく"さんかき"ます

*2: