ICPC2023 国内予選 参加記（MasKoaTS視点）

はじめに

2023/07/07、ICPC2023 国内予選の方に参加しました。

Shirotsumeさん、fky_さんよりお誘いをいただき、神戸大学からUriboというチームで出場しました。

結果はABCDの4完37位で、おそらく国内予選は通過しました。

同チームから既にShirotsumeさんによる参加記が公開されていますが、私MasKoaTSの方からも簡単に感想等を記そうと思います。



練習・立ち回りについて

Shirotsumeさんの参加記にもある通り、対面で競プロのチーム戦を行うのはチーム全員にとって初めてだったので、まずはチーム戦に慣れるところからスタートしました。

私は他の二人と所属研究室（学科）が異なることもあり、初めの方は上手く意思疎通がとれないことも多々ありましたが、回を重ねるごとに自然と会話に混ざれるようになりました。

立ち回りに関しても、リーダー的存在であるShirotsumeさんを中心として、序盤の流れや担当する問題等を事前にきっちり決めていたのは大変良かったと思います。

特に、2週間ほど前に開催された国内模擬予選にて私がF問題で頓珍漢な考察・実装をして時間を浪費してしまったことをきっかけとして、「問題の解法が分かったときは他のチームメンバーとこれを共有し、全員の了解が得られたら実装に移る」というルールを定めました。

これがコンテスト本番でも功を奏し、問題文の誤読や嘘解法による時間の浪費が減って良い結果に繋がったのだと思います。

コンテスト本番について

以下、コンテスト本番における各問題の感想を簡単に述べていきたいと思います。

Problem A - スポンサー賞はどのチーム？

私が考察・実装を担当しました。

AtCoder Beginner ContestのB問題あたりで出題されそうな（最近だとA問題で出ても不思議ではない）ごく基本的な問題であり、特に苦戦する要素はありませんでした。

万が一にもペナを出すことがないよう慎重に実装し、無事に一発ACできました。

Problem B - あみだくじ

主にShirotsumeさんに考察・実装を担当いただきました。

解法は特に難しくなさそうでしたが、実装が大変だったようで、ペナを2つ重ねつつコンテスト開始から約40分後になんとかACできました。

コンテスト本番中、私はこの問題についてはあまり確認しておらずC問題以降の考察を行っていたのですが、コンテスト終了後に改めて確認した感じだと、素直に横線を引く場所を全探索すれば良いのかなと思いました。

ただ、確かに実装はそれなりに複雑そうであり、ペナが重なったのもやむ無しかな、という感じでした。

Problem C - 席替え

ShirotsumeさんがB問題で格闘している間、fky_さんとこの問題の考察を行っていました。

マンハッタン距離関連の問題なので45度回転で解けないかと考えましたが、上手くいかず暫く思案していたところ、fky_さんより「x座標とy座標の和の偶奇で分けたら上手くいくのではないか」という提案をいただきました。

正当性は少し怪しかったのですが、「もし嘘解法だったとしても、手元でテストケースやジャッジを作って簡単に検証できるから、やってみる価値はある」とのことだったので、お任せしました。

実装・バグ取りでかなり苦戦していたようですが、最終的にこれらをすべて成功させ、一発ACを取りました。

この辺りは流石ヒューリスティックガチ勢といったところです。素晴らしい。

Problem D - 効率的な問題セット

fky_さんがC問題の実装を行っている間、Shirotsumeさんとこの問題の考察を行っていました。

私が「二進法的に考えて 2^0, 2^1, 2^2, \dots みたいに決めるのが最適そうですけど、選ぶ配点が重複ありで配点の総和にも制約があるので厳しいですかね？」という感じでShirotsumeさんに尋ねたところ、「いや、二進法的な考え方で悪くないと思う」と返ってきた後、

  • 配点を 2^0, 2^1, \dots, \text{（配点の余り）} のように決めれば、明らかにすべての要件を満たせること
  • 上記より、答えの上限は 7 であること

の証明をいただきました。天才すぎる。

これらの事実から計算量 O(n^6) で答えを探索でき、しかも定数倍の分母に階乗が入るので、 n \leq 100 の制約下で比較的高速に問題を解くことが可能です。

結果、Shirotsumeさんがこの解法の実装を行い、無事にACを取れました。

Problem E - 改竄された史料

Shirotsumeさんより「午後だけだったらLISでいけそう」という意見があったため、LISをもとに色々と上手くできないか考えたのですが、特に良案は浮かびませんでした。

その後、再びShirotsumeさんより \mathrm{dp}[i][x][y] = \text{（下から $i$ 番目の順位で記録が $(x,y)$ の場合の最小改竄個数）} のようなDPを考えれば計算量 O(n^3) で解けそうという話をいただき、なんとか計算量を二乗まで落とせないか、チーム全員で考察していたところで時間切れになりました。

コンテスト結果

以上のように、今回の国内予選におけるチームUriboの最終結果はABCDの4完37位であり、神戸大学からはこのチームしか出場していないため、アジア予選進出はほぼ確実と思われます。

B問題で2ペナしたときはどうなることかと思いましたが、最終的に各チームメンバーの実力やこれまでの練習成果が遺憾なく発揮された素晴らしい結果が得られました。

また、今回私が解いたのはA問題のみであり、後の問題は他の二人と適当に考察・議論していただけだったので、改めて二人の実力の高さに感嘆しました。

おわりに

今回、私は初めてのチーム戦としてICPCの方に参加させていただきましたが、一人で競技に取り組むときとは違った達成感が得られ、とても楽しかったです。

今回の国内予選に当たって、共に参加しないかというお誘いをいただき、コンテスト本番で同じチームメンバーとして共闘してくださったShirotsumeさんとfky_さん、チームのコーチ兼監督を引き受けてくださった先生、本コンテストの準備・運営に携わってくださった方々、ならびに本コンテストに関してご支援・ご声援いただいた皆様に深く感謝申し上げます。本当にありがとうございました。

今後も研鑽を重ね、アジア予選でも最善を尽くしていきたいと思います。

以上、ここまでご精読いただき、誠にありがとうございました。