ICPC2020 国内予選参加記
-
参加までの流れ
今年で3年目のICPCに今年も挑戦。
去年のチームメンバーであったtempuraさんは社会人になり組めなくなったので、新しいメンバーとしてmoririn君をスカウト。
その結果、3人とも橙以上の学内topチームになり、絶対に負けられない戦いに...(学内のICPC参加権利を持つ橙以上の人は現在5人のはず)
意気込み↓
国内予選2位目標で頑張りたい
— heno (@heno_code) 2020年11月5日
-
コンテスト開始
5分ぐらいログインできなくて焦る。電話をするとつながらないので、全国的にログインできないんだなあと推測して少し安心する。
と思ったら突然ログインできるようになり、そのままコンテストが始まったのでびっくりする。
-
コンテスト序盤
ABをyamunaku & moririn にまかせて、Cを読む。
ABを一瞬で通してくれたので、一安心。CもO((約数の個数)^2)をすると3分ぐらいで実行が終わってくれたので、そのままAC。
という風にかなり良い感じの滑り出しを決めた。(ICPC2019国内予選、ICPC2019ベトナム大会、ICPC2020模擬国内ではかなりのスロースタートだったので、珍しく良い感じ)
-
コンテスト中盤その1
Dにyamunaku&moririn, Eを自分が担当する。
Dの考察が早々に終わったみたいで、構文解析を誰が書くかで少し迷ったが、Eに一番強いのが自分だと思ったので、yamunakuにDの実装を託した。
ここから、
yamunaku:Dの実装
heno:Eの考察
moririn:Fの考察
の3並列が始まる。
※試合後にこの話をしたらある人に「DEF3並列は攻めてるなあ」と言われてしまった
-
コンテスト中盤その2
-
Eの話
とりあえず連結成分ごとにわけると、サイズが30*60に見える。
よーーーーーーーーーーーーーーーーーーーーーーーーーくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよく凝視すると(この間5分~10分)、15*60になることに気付く。
あとはbit DPを実装するだけ(かなり重かった)。計算量はO(2^(N/4)*N*M)
-
Eが通った後の話
Dの様子を聞いたら「書き終わってデバッグ中」とのことだったので、yamunaku君に託したままFを手伝いにいく。moririn君からFの考察を聞くと既に考察が終わっていたので、実装する。(これも結構実装重かった...)
結局Dは早々に通り、Fは30分後ぐらいに通った。この時点で国内予選通過を確信する。(6完時点で暫定１位だった。)
-
コンテスト終盤
GとHを見ると、GがフローっぽくてHが幾何。Gが解ける問題に見えたので3人ともGを見る。
色々考えた結果O(N^3M^3log(NM)^2)とかいう多項式(笑)の解法を実装したが、バグを取り切った時点で残り時間が数分しかなく、実行続けたままコンテストは終わりを迎えてしまう________
-
コンテスト後
10分ぐらい実行させると実行が終わったので、「あと20分あればなあ」と負け惜しみをする。
遠吠え↓
まじで7完したかった、悔しい
— heno (@heno_code) 2020年11月6日
G,10分ぐらい実行したら終わったからあと20分ぐらいあれば通ったかな...
— heno (@heno_code) 2020年11月6日
-
反省点
Gがコンテスト中に通せなかったのは実力不足(フローへの理解&慣れ不足)であり、悔しい。
大阪にいたため京都で行われた打ち上げに参加できなかった。前日から京都入りしておくべきだった。
-
アジアに向けての意気込み
国内予選と同様、2位を取れるように頑張りたい。
-
おまけ
最後はGに張り付いていて1時間ほど順位表を見ていなかったため、コンテスト終了直前は「KINGと自チームを除いて、7完チームが2チームぐらい、6完チームが少なくとも10チームはいるんだろうな」と思っていた。終了後の順位表を見てかなりびっくりした。
