はじめに
この記事は 東京高専SPC同好会/プロコンゼミ老人会 Advent Calendar 2023 の記事です。
2023/11/25-2023/11/26 に開催されたICPC 2023 Asia Yokohama Regionalに筑波大学からチーム "GoodBye2023" で参加し、9完9位でした。 本記事ではチーム構成やコンテスト中の動きなどについて記していきます。
チームについて
- 僕: 引退勢・アルゴ黄
- Aくん（仮名）: 引退勢・アルゴ黄（highest橙）
- Bくん（仮名）: アクティブ勢・アルゴ橙
の3人で組みました。 記事に名前を載せていいか聞いてないのでチームメンバーは仮名で呼ぶことにします。
チームメンバーのやる気があまり無かったこともあり、一度のみの練習で競技に臨みました。
コンテスト
事前の打ち合わせでは僕が事前準備担当でAくん・BくんにそれぞれA・Bを解いてもらう手筈だったのですが、Ubuntuにユーザー名とパスワードを入力した時点でPCがフリーズ。 どうしようもなさそうだったのでスタッフを呼んでPCを再起動して貰いました。 これが原因で僕たちのみ3分延長となったのですが、トラブルが起きている間も問題文を読むことはできていたので少し得だな～と思ってました。 再起動後にはAの解法が出ていたので僕は準備をせずにC以降の問題文読みをすることになりました。
C問題以降について、問題ジャンルと制約、可能ならおおよその難易度感を伝えるつもりで雑読みをしていきます。 適当に読んでいくとDが明らかにRun-Length Grammarの話でニヤニヤしつつ、Fがかなり楽そうな見た目をしていることに気がつきました。 Aが解けた時点で順位表を見るとFが1チームに解かれていたので簡単だと確信し手を付けることにします。 少し考えるとランレングス圧縮のように考えれば良いことがわかり、ABを解いてもらった後に実装、バグらせずに無事Fを解くことができました。
後は問題を読みつつ順位表と相談して解けそうな問題を探します。Dが阪大のチームに解かれており、そこで少し考えると O(n3) の区間DPが思いついたので実装を詰めます。 Aくん・Bくんはこの時点でEの考察を終え実装をしていたのですが、少し計算量が悪いらしくTLE。 Eの実装・計算量改善とDの実装・バグ取りをPCを交互に触りながら行い、90分時点で両方ACが出ました。
DEの実装をしている間にAくんがKを解いたらしく、概要と雑解法を聞いた時点で実装を任せ、Bくんと一緒に他の問題について考えていきます。 残りでACが出ている問題ははGHJで、順位表を見る限りだとGが少し楽そうです。 Jについてはいくつかの仮定を信じるとHLD+min-add遅延セグ木で解けるということを教えてもらいましたが、写経コストと嘘解法の可能性を考えて放置。 Hも燃やす埋めるに帰着できそうなことを教えてもらったので、辺の張り方などを詰めてもらうことにしました。 Gも2人で考察をしていると実験結果次第で解けそうなことが分かり、KのACが出たところでBくんに実験コードを書いてもらうと実行時間が十分間に合いそうなことが判明、そのまま実装をお願いしました。 1ペナこそありましたがGも無事AC。
この時点で競技開始から2時間半ちょっと。残りの可能枠はHIJで、JとHはおおよその解法が出ているがライブラリ写経が必要な状態です。 ここでAくんにDinic+HLD+Lazy Segtreeの写経を全て投げます。本来なら実力的に僕がやるべきなんですが、僕はUSキーボードに不慣れでまともに写経ができない状態でした。 Jを考えていると貪欲を信じて良い気持ちになれたので貪欲の実装部分をすぐ実装できるよう簡単に紙コーディングをしていきます。BくんはHの具体的なグラフ構築を詰めている状態です。 写経が終わったのでJを書くと一切バグらず一発で動き、半信半疑のまま投げるとなんと一発AC。 その後に実装してもらったHも問題なく一発でACを得ることができました。9完。
一桁順位もほぼ確定したので安心しつつ、最後の45分でIを考えます。 途中まで線形計画や行列の気持ちになって迷走していたのですが、比率が極端に偏っているものは作りようがないという点を考えるとうまく貪欲したい気持ちになってきます。残り20分しかないので細かい実装の仕方も分からないままコードを書き、途中でAくんがもう少しマシな方法を思いついたので実装役を交代します。 残り15分程度のところでBくんが想定解と同じベクトルを使った解法を思いつき、それを信じて実装役をもう一度交代。 コードは書ききったけどバグっている状態でアディショナルタイムを終え、コンテスト終了となりました。
結果・感想
9完9位でした。僕達の実力と練習量を考えると大成功と言えると思います。 ただもう少しで10完銅メダルだったこともあり、さらに良い結果が出せた可能性を考えると後悔もあります。
僕は来年から外部の大学院に進学するのでここでICPC人生は終了という気持ちだったのですが、実はAsia Pacific playoffに参加できる確率が結構高いらしいということを後で知りました。どうやら2023年でGoodByeとはならなかったようです。 アジア地区予選を終えチームメンバー全員のモチベーションも高いので、チーム練も行いながら次のコンテストに向けて頑張っていきます。
