2019/07/12に開催された国内予選にチームAobayama_dropoutで参加しました。メンバーはいつもの碧黴さん・ゆきのんさん・僕です。
コンテスト前
金曜一限の単位が危ないことを自覚したので、頑張って間に合う時間に起きます。まだ落としてはいない、たぶん。
そのまま二限まで受けて、三限の途中で退室して山に登ります。会場の研究室に着くと、去年も見たでっかいカピバラのぬいぐるみがお出迎えしてくれました。
適当にリハーサルをやった後、まだ開始まで1時間あるので1問解こうとなって問題を開きます。解けないまま1時間が経ち（ええ……）、いよいよコンテスト本番です。
コンテスト中
去年と同じく、僕が最初からDを読むことにします。しかしDの問題文が届くまでしばらくあったので、碧黴さんがAを解くのを眺めます。まあAC。 Bをチラッと見て気持ち悪くなっていると、Dが届きました。読みます。
ゆきのんさんがBを書いているのを横目に考察を進めます。パッと見て解法が浮かばないので、とりあえずサンプルがどうなっているか手計算で確認します。 サンプルをやっているうちに、こういうのはどこまで決めたかを持つDPだったような気がしてきます。最初は[0,i)の結果を全部見ることでiをO(N)で求めるやつかと思ったのですが、当然違います。 何回Mが足されたか？をDPの添え字に持つと解けるように見えましたが、まだ[0,i)からiを求めることが必要だと思っていて、このままだと遷移にO(N)かかってしまいます。実は直前しか見なくていいんじゃないかと考えましたが、確信が持てません。
そうこうしているうちにBが通り、Cはまだ書けないということなので、とりあえず直前だけ見る遷移がO(1)のDPを書きます。書くとサンプルが合うので、半信半疑ながら提出するとAC！やったぜ。
Cの考察がまだ詰まっていないようなので、参加します。分銅の乗せ方はO(3M)である、と言うと間に合うことが判明したらしく、ゆきのんさんがすぐさま実装に移ります。その間に僕はEを読むことにします。 Eは考察要素がないので、Cを書いているのを見ます。横から口を出したり手を出したりしているとサンプルが合うので入力を流し込みます。そうしたら今度は実行が一生終わりません。前計算できる部分を見つけたのでチャチャっと書き直して再度実行、まだちょっと時間はかかりますがとりあえず終わります。出すとAC！
Eを書きます。どのように面を配置するかを決めてから、それが適切かどうかを判定することにします。（ここを枝刈りすると早くなるらしいのですが、ちょっとバグが怖そうです。） 適切かどうかの判定をするために、立方体の展開図とにらめっこしながら丁寧丁寧丁寧にマジックナンバーをハードコーディングしていきます。 書けたのでサンプルを試すと合いません。ちょっと考えると実は裏表をいじっていないことに気づきました。幸い修正は簡単で、方向を決めるフェーズで裏表も決めるように（状態数が32倍！）すると無事サンプルが合います。 テストケースをダウンロードしてきて恐る恐る実行します。カメの歩みみたいなスピードでoutputファイルが生成されていくのを祈るような気持ちで見つめ、提出するとAC！これは嬉しかったです。
僕がEをチンタラ書いている間に二人がFの考察をしていたので、僕も参加します。こういうのは大体不変量を見つけるんだよなあ！（大声）と思ってちょっと考えたんですが、ないです。 じゃあフローでしょ！ｗとなったのですが、無理です。 線形代数学では？と思って隣接行列をいじっていたらしいのですが、何もわかりません。 本当に何のとっかかりも見えないままコンテストが終了しました。
コンテスト後
結果は5完で全体7位でした！東京大学とか京都大学の学内予選は10位入賞が絶対条件ですが、そのうちの1枠を粉々に粉砕できて心地よいです。 これまでICPC関連のコンテストでは毎回毎回4完しかできていなかったので、今回ついに5つ目の問題を解けて感慨深いです。まあEみたいな問題がこんな後ろのほうにあるのも変ですが。
東北大学からはうちともう1チームがアジア地区大会に進出することに相成りました。良いですね～～～
研究室での打ち上げに混じらせてもらい、ずっとカピバラをモフっていると、実は研究室で持て余していたらしく、サークルに譲っていただけることになりました！ありがとうございます！ ということでそれを持って霧深い山道を下りました。
— こたつがめ (@kotatsugame_t) 2019年7月12日
まだ何もない部室に安置したところで今日の活動は終了です。直後のこどふぉはレジし損ねました。
