ICPC2016 国内予選 参加記
先輩( @LazyMii )と後輩と、「miyazoy72」というチーム名で参加し、33位でした。
恐らくアジア地区予選に出場できるのではないかと思います。
「SIMrit」という、熱意のある学内のライバルチームも参加していたので、学内1位の順位を取れたのは本当に運が良かったです。
(追記:地区予選進出が確定しました 順位と結果 | ACM-ICPC 2016 Asia Tsukuba Regional)
国内予選当日まで
チームでは、模擬国内予選A・Bに参加したり、1度だけICPCの過去問題を通して解くといった練習をしました。
模擬国内予選Aでは3完早解きで46位、模擬国内予選Bでは普通の速度で3完して40位台*1でした。
この程度の順位では恐らくアジア地区予選に行くことはできず、また前述のSIMritは両模擬国内予選で僕達よりも1問多くACしていたので、本当に歯がゆい気持ちでした。
この時から、「学内一位を取るならば早解きで勝つしかない」と考えていました。
コンテスト
予選にはLazyMiiさんの研究室から参加しました*2。
広い机とプリンタがあったので、良い環境だったと思います。
コードや詳細な解法については別記事参照。
ICPC2016 国内予選 コード置き場 - あったこといろいろ
A問題
問題文が短く、ABCのA問題かと思った。ついでにテンプレートを写しつつAC。
B問題
解法としては「得票数1位の人の票数 > (得票数2位の人の票数 + 残りの全票数)」を満たす、初めのタイミングが答えとなるという単純なもの。しかし、条件を満たしたタイミングでbreakしたため、入力を最後まで読まずプログラムが終了するバグが発生して20分ほど悩む。
早解きで勝とうと考えていた僕はこの時点でダメかもと思い始める。
C問題
パッと思いつくエラトステネスのふるい的な解法はTLEしそうに見えたが、一応LazyMiiさんに書いてもらいながら後輩と2人で考察。少しして前述のTLEしそうな解が問題なく通る。そんなんでええんか…
D問題
問題設定が単純でわかりやすかった。
「これに必勝法があるなら類題がいくらかありそうなものだし、どうせDPでいい感じに全探索やろ」とか思う。後輩にサンプルを解説してもらうと、区間で状態が持てそうなことに結構早く気づく。区間DPは、偶然参加していたSMR686で出題されており、pekempey先生の解説で理解していたので、本当に運が良かった。
この時はテンションが上がりすぎていて、ちょこちょこバグを出しながら*3メモ化再帰で書く。メモ化再帰恒例の、"dpテーブルは宣言したがメモ化を忘れるやつ"をやらかしながら、無事AC。
この辺でたしか2時間くらい経過していた気がする。SIMritはこのとき3完だが僕達よりもペナルティが小さかったため、僕達がACしてから20分以内にACされると逆転されるという状況だった。結果的にはこの20分の間に提出はなかったけれど、僕にとってほんとうにほんとうに長い20分だった。
👇pekempey先生の解説
TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv1 - pekempeyのブログ
E問題
D問題をACしたテンションと疲れで僕が使い物にならなくなっていたので、考察を2人にまかせて少し休憩。休憩が終わって全員で話し合った結果、「完成する物体は連結」「完成する物体はドーナツ型かパス型」「一つの立方体と交差する立方体は高々8個？」という結論になった。スタートする立方体を一つ選び、そこからDFSみたいなことをする解法を書くが、いかんせん僕が使い物にならなくなっていて 実装が遅い＆バグが出まくる という感じでヒドかった。LazyMiiさんに助けてもらいながら全体の40%くらい[要出典] 書いたところでコンテスト終了。
感想
Bのバグがなかなか取れなかった時は死を覚悟しましたが、Cの全探索をパッと書いてもらえたり、Dの解法がすぐに思い浮かんだのが功を奏しました。ある程度の難易度の問題に対して、早い段階で解法を思いつく能力を付けたいと思いました。
連続でコーディングしていると自分はすぐバテるらしいので、アジアに行けるならばそれまでにコーディングを分担できるようにしたいです。
競プロ引退気味だったLazyMiiさんが「また競プロやってみるかなぁ」*4と言ってくれたり、後輩が「僕も競プロ頑張りたいと思いました」*5と言ってくれたりしたので、本当に良かったです。ICPCは本当に偉大ですね。
たくさんお酒飲んでほえ〜なんですけども、多分ICPCアジア予選に出場できるんですよね。
— やざてん (@Yazaten) June 24, 2016
うれしいなぁ
