ICPC 2023 国内予選に pointN さん、niuez さん、ruthen で Big O of N cubed として参加しました。
チーム名の由来は 3 人ともハンドルネームに N が含まれていたためです。
本番前
今年の4月下旬くらいにチームが決まり、毎週末のどちらかを主な練習日に充てました。
走ったセット（時系列順）
- 模擬国内2015 (4/30)
- HUPC2023 Day1 (5/14)
- 模擬国内2016 A (5/21)
- 模擬国内2016 B (5/28)
- 模擬国内2017 (6/4)
- 模擬国内2018 (6/10)
- 模擬国内2023 (6/24)
- 模擬国内2020 (7/1)
模擬国内2023の結果は現役内では23位でした。（参考）
ライブラリに関しては、持っている量が圧倒的だったこともありほぼ niuez さんに丸投げしてしまいました。（ありがとう……。）
パソコンは ruthen のものを（新しいアカウントを作り）、キーボードとマウスは niuez さんのものを（練習・本番ともに）使いました。
エディタは CLion をしばらく使っていましたが動作が重く、一部の拡張機能の利用が認められたこともあり途中から VSCode に切り替えました。
前日
必要なライブラリの印刷は既に済ませていましたが、kazoeage.pdf や seisuuron.pdf などを追加で印刷しました。
直近にチームで走った模擬国内2020バチャのupsolveとして、F アローダイスを通して寝ました。
当日
14時くらいに大学の計算機室に集合しました。 国内予選のために他の部屋からプリンタを移動するなどの作業があったため、その手伝いなどをしていました。
初動については、ruthen が問題文を印刷し、そのまま A に取り組み、pointN さんが B を読み、niuez さんが問題を切り分けつつ C 以降に目を通すというところまでは練習時に決めていたため、その通りに動きます。
問題はこちら
A は特に難しいところはなかったため、問題なく AC しました。 かなり急いだつもりではありましたが、それでも全体 FA とは 2 分半ほどの差がありました。
pointN さんが B を読み終えたのでパソコンを渡して、自分は C を読みます。
構築問題で、 程度距離を開けながら配置していけばよさそうでしたが詰め切れず、D を読み終えた niuez さんから D の概要を聞きます。
概要を聞いて割とすぐに、個数制限付きナップサックで 2 べきに分割するテクニックを使うことで、答えの上界が 7 であることに気づきます。つまり 6 以下を全探索すれば良いということが分かります。
そこで niuez さんが候補の集合は集合の要素の和が になるため、5 つの要素を確定させれば残り 1 つは決まるということに気づきます。
ここで、答えの集合の最小の要素と、作るべき値の集合の 0 より大きい最小の要素が一致するため、4 要素を全探索すれば良いという嘘考察を生やしてしまいます。
その頃 B が AC したこともあり、pointN さんに C の概要を投げて、niuez さんが D の実装を始めます。 デバッグなどを終えて D を提出してみると WA が出たため、コードを印刷してデバッグを開始し、その間に pointN さんに C の実装を任せます。
D の実行があまりにも高速に終わったため、別に 5 要素を全探索しても良いのでは、ということで実装を変更したところ AC します。
その後 C も pointN さんが AC します。（完全に丸投げしたのに通していてすごい。）
E の AC 数が F より多かったため、E を考えます。
ぱっと見で の DP が思いつきますが、それ以上オーダーが落ちません。
しばらくして niuez さんが dp[i][y] = i 番目の要素の y 座標を y に固定し、x 座標は動かさない時の最小コスト というような DP を考案し（多分）、遷移を式変形して観察すると Range Minimum Query の Segment Tree で解けるということで実装を開始します。
実装を見つつ、ruthen と pointN さんは他の解法がないかを考えます。その後終了 30 分前くらいに、pointN さんが dp[i][c] = i 番目までの位置を決めており、現在のコストが c のときの最大の (x, y) の位置 という DP を考案します。
niuez さんの解法はやや複雑だが実装はデバッグだけという段階であり、pointN さんの解法は簡潔だがまだ実装が全く進んでいないため残り時間で書きあがるかわからないという状態だったため、niuez さんと pointN さんが交互にパソコンで実装するという形になりました。そしてその結果どちらも実装が終わらないままコンテストが終了してしまいました。
結果は 23 位で、Yokohama への進出が決定しました。
今思えば 3 人目としての理想的なムーブは、2 人の解法をそれぞれ理解したうえで、pointN さんの解法を niuez さんに伝えてそちらに集中しようと提案することではあったのですが、仮に pointN さんの解法が正しいとすると E は通されてなさすぎるのではないかと思ってしまい、確信をもって動くことができませんでした。（それでも niuez さんに概要を伝えるべきではありましたが。）
感想
とりあえず大学から 2 チーム出るという目標が達成できて良かったです。
他の 2 人に比べると実力が足りていない（というか、得意分野がない）と感じることが多いので、Yokohama までにはもっと練習しようと思います。
