昨日はICPC2020国内予選に参加しました。チームは毎度おなじみのSPJ(クマー、zkou、私)です。
本番の記録
- 16:30〜
あれ？サイトに繋がりません。めちゃくちゃ焦ります。電話をしても繋がりません。なんか10分ぐらいしたら急に治りました。
- 16:40〜
打ち合わせの通りに私がA、zkouがBを通します。クマーがCで苦戦しているので見ていくと、3乗根っぽいのはわかりますが解けません。(ここ戦犯ポイント1) めちゃくちゃみんなで高速化を考えてると、愚直解の実行が終わっています。ここまでで1時間くらい使ったのが結果的にはかなり痛かったね、、、
- 17:40〜
DとEを並列に読みます。Dは構文解析パートは易しそうで、その後の解法について制約等からbitDPとかを考えるんですけど、これが良くなかったです。(戦犯ポイント2) 答え決め打って頑張るとかまでは思いついていたので、どうして順序を割り振ってbit全探索が出てこなかったのか、、、 結果的にDを通していれば余裕で予選通過だったので非常に悔やまれます。
Eは最初木DP？とか思うんですけど、全然木じゃなかったです笑(くまーにおこられました)
- 18:30〜
EがbitDPで高速ゼータ変換してうんちゃらするとかいう方針をzkouが思いつきます。(天才) 私は高速ゼータ変換良くわかっていないので(これは良くない)、一人でDを考えていました。
Dがよくわからないので、Fを見にいくと、これは部分永続Union-Findで勝てそうな問題に見えます。 辺の長さが小さい順からUFの辺を削除していって(これは部分永続Union-Findで簡単にできます(逆から辺を貼ればいいので))、最大じゃなくなった頂点集合を消していき、最終的に頂点集合のサイズが1となったときに残っている頂点が答えっぽいことに気付きます。これはどう見てもΟ(NMlogN)くらいかかりそうなんですけど、ちょっと高速化すればここまでにはならなさそう？と思ってコードを書き、実装すると5分くらいでデータセット1が終わります。
ノリノリで提出すると、WAと出てイライラします。入力と出力をじーっと比較すると、なんと1行まるまる飛んでいます。(N,M)=(1,0)のコーナーケースが入っていたそうです(ひどい) ここを直してFをACしました。
- 19:00〜
くまーとzkouがEを頑張って書いているのですが、サンプルすら合いません。デバッグを応援しながらDを考えるのですが、全然解けません。デバッグを応援していると、終了直前でなんとかEが通り、そのまま終了。
結果は23位で大学内8位、予選敗退でした。
感想
初めての参加ということもあり、緊張しましたがコンテスト自体は非常に楽しかったです。結果も、黄黄青の3人チームにしては上出来だと思いますが、Dが通せなかったのがとても悔しいです。
来年はもっと強くなってリベンジしたい、そう思いました。
