高校生として出た最後のプログラミングコンテスト。チーム戦楽しかった。
チーム
with sinatori
戦略としては、最初の方は交互に解き、後半はそれぞれが得意なものをやる感じ。地力の差があまりなさそうだったので。
データ構造、グラフは自分で解きにいき、文字列、幾何は相方に投げていた。本選前のバチャの感触としては、8位以内はまあいける、3位以内も狙えそうだと感じた。
予選
あんまり覚えてないので適当に。
11完2ペナで1位。何気にプログラミングコンテストで1位取ったの初めてかもしれない。
2,4,6,8,10,12を担当。この時は完全に偶奇で担当が分かれた。
1~4はスムーズに通ったが、6が正四面体を転がすとかいう謎問題で、詰まった。そのため1~6が通ったのが開始80分後とかで、この時は普通に通過圏外だった。
6はずっとスマートに解こうとしていたが、諦めて紙を破って正四面体を実際に作り、それを見つつ大量の場合分けをして通した。
そこからすぐ7,8をほぼ同時に通し、9,10に取り組む。ここまで2人の提出タイミングがずっと同じだったのが面白かった(別々の問題のはずなのに)。
10は平方分割を考えるとすぐに解け、奇跡的にノーペナでAC。ここまでで2時間半くらい。
9がかなりつらそうだったので応援しつつ、どこかのチームが通していた12を眺める。
雰囲気で重心分解を考えるとうまくいくことが分かるので実装すると、ほぼ詰まることなくAC。
しかもこの間に9のバグが取れていたらしく、9もACして11完に。9と12を同時に提出したので、ほぼ同時にACが帰ってきてテンションが上がり、思わずハイタッチしてしまった。
順位表を見た感じかなり高順位で通過できそうだったのでとても嬉しくなった。11は少し考えたが解けなかった。
10、12がこの速度で解けたのは完全に運だが、ともあれ成功したのでヨシ。
本選
こっちはかなり強烈な記憶になった気がする。
10完∞ペナで7位。悔しい。
2,4,7,8,11,12を担当。
1~3はスムーズに通る。
4の解法が10分考えてやっと分かったので、かなり焦りながら実装した。するとWA。
初期化忘れかと思って直してもWAのままで、序盤で2ペナを作ってしまったことで完全に冷静さを失った。そこで、落ち着くために7に行くことにする(6が幾何だった)。
すると7も全然綺麗な解法が分からず、分かった解法も自力で多倍長整数を実装する必要があり、ライブラリも持っていなかったので焦りまくった。
それでもなんとか適当に実装するとAC。この時点で75分位経っていた。
4が嘘解法だと思ったので、7をやっている最中に相方に4を考えてもらったが、普通に合っているらしい。コードを確認すると最後の処理を書き忘れていただけだった。申し訳なさすぎる。
8の見た目がまともそうだったので考えると、2番目の最短路を求めるだけの問題だったので安心した。普通にAC。この時点で2時間くらい。
その間に相方に投げていた6がバグが取れないらしかったので、9に行ってもらう。
ここで自分が6を見たほうが(精神衛生上)良かった気もするが、焦っていたのでそんなことは考えず、12に特攻する。たぶん2人とも焦っていて良くなかった。
12はJOIのバブルソートを解いていれば貼るだけの問題で、当然貼るのは不正なので頑張ってライブラリを写経する。SuperConで鍛えた写経能力の見せ所(適当)。
2Dセグ木は中々重かったが、1ペナでAC。この時点で2時間半くらい経っていたが、流石にこのあたりになると頭が冷静になってくる。ペナ数ももはや気にしても仕方のない領域に来ていた。
そこで6を眺めると、すぐにバグの原因が分かる。ACして一安心した。
相方が、9が分からなくて10が分かったらしいので、自分が9をやることにする。しかし分からない。AtCoderみたいな問題を出さないでくれ。
残り1時間くらいのタイミングで初めて順位表を見ると、7位くらいだったが、今から10,11を通せば良い位置に行けそうだと踏み、11をやることに。
秘技・制約エスパーを用いるとO(3^n)のDPが使えそうだと分かる。パスごとに最小コストを前計算し、強連結成分にパスを追加しながらDPしていく感じ。
残り30分くらいで実装は終わったが、微妙にバグっていたので気合を入れてデバッグをすると残り10分でバグが分かり、残り7分くらいでAC。流石に脳内物質がドバドバ出た。
隣を見ると相方が10のWAで苦しんでおり、自分は問題すら見ていないのでお祈りをしていたが、流石にヤバそうだったので見る。バグらしきものは修正できたものの、WAのままコンテスト終了。方針ミスだったらしい。幾何本当にむずそう。
感想
チーム戦、戦略とコミュニケーションが大事になってきて中々面白い。ただミスった時はだいぶメンタルが削られる。ICPCに出るかどうかは迷い中。
あと幾何2問は、きついです......。それでも全完するチームがいるの、何？？
