ICPC2020 国内予選 参加記
はじめに
2020/11/7 に行われた ICPC 国内予選に suibaka, nakano, otera1999 の3人で参加しました．
結果は 29位 と力及ばず，ここ3年で最も低い順位をとってしまいました．
この結果，僕と nakano は今回で引退となります．せっかくなので記録を残しておきます．
コンテスト中の流れ
僕が B, D, E をやって，otera くんが A, C, F をやっていました．nakano は考察担当で実装はしません．
以下僕が解いた分の問題の流れをば（A, C, F は読んですらいないので全く知らない）．
- B 問題
- これ直前に Twitter かなんかで同じ問題なかったっけ？と思いながら適当に書くと WA になり，めっちゃたまげた
- 無限に悩んで，挙げ句考察担当に（B問題なのに）合ってるか確認する始末…
- 結果だけいうと，提出するファイルを間違えていただけだった．提出担当やめろ
- D 問題
- n が小さかったんで bitDP でできたりしない？
- 一個ずつ決めていく方針だと後ろの未確定の分で困るね．うんうん
- nakano が答え決め打ちしてそれ以外の文字が前と後ろどちらにあるかだけ決めればいいんでは？という．すげー
- サクッと実装して，終わり．（終わってから思ったんですけどこの問題結構好きです．
- E 問題
- 独立集合の数え上げ．むずそー
- nakano と考えていると，斜め方向で状態を考えれば，隣接する2つは選べないので状態数が fib(n/2) ぐらいになって嬉しいねとなる
- 斜め方向なのでちょっと実装方針に悩む
- 詰めて書いたところ，なんかバグる -> ループを m / 2 回回していたが，左上から右下まで見るので m 回回さないとだめだった．
- サンプルが合うので，ぶん回す -> なんと間に合わないままコンテスト終了
- 計算量は大体 m * n * fib(n/2) だが，dp テーブルを unordered_map (or map) で管理しているので定数倍 (or log) の分重い
- 4分割してそれぞれで解くのでこれに 4 倍がつき，さらにテストケース数分あるので冷静になると，確かに間に合わないかもなという気もする
