2/29~3/3にベトナムで開催されたThe 2024 ICPC Asia Pacific Championshipにチーム GoodBye2023 で参加し26位だった。
他のチームメイトの参加記:
keymoon.hatenablog.com
メンバー
- Yu：唯一の現役
- shibh：文字列が得意
- keymoon：CTFが得意
(以下敬称略)
事前準備
年末年始辺りから本格的な練習を始めた。全員が大学の近くに住んでいることからチーム練のために大学に集まりやすく、昼から5hバチャを走ってラーメンを食べて帰るみたいな生活を毎日のように送っていた。
練習でもできるだけ本番に近づけられるように、ライブラリを印刷する、問題文を印刷する、USキーボードを使う、WF OSを使うなどをしていた。主にkeymoonがこの辺の事前準備をめちゃくちゃ頑張ってくれていて*1、詳細はkeymoonの参加記を見るといろいろ書いてある。
Day0
ホテルに着いた時点で既に夜中の一時半とかだったので急いで風呂に入って寝た。全くベトナムの宿に期待していなかったが、思っていた何倍も綺麗でよかった。
Day1
プラクティスがあった。keymoonがプラクティスで確認することリストを用意していたが、スマホの持ち込みを禁止されて急遽コード写経タイムが始まった。ここで私が本番持ち込むライブラリの裏に書き込んでしまい、一枚目だけ予備のライブラリを使うことになってしまった *2
clarバトルの末、日本から持ってきた大量のお菓子を持参する権利を手に入れた。
Day2（コンテスト）
初動では私がCLionの設定とテンプレートの写経をして、他2人が前後から問題を読むことにしていた。
コンテスト開始前に風船の数を見て問題数が12問であることを確認。テンプレートの写経を終わらせて問題管理用シートを書いていると、正面の席にいたBocchi The Techが「13問ある！」と言っているのが聞こえてきて、慌ててMを書き足した。風船を数え間違えてたらしい。更にこの後shibhの問題文からM問題が抜けていることに気づき、運営に問題文を換えてもらう。
Hが解けそうと言われ渡される。0と1の多い方を選んで残せばよさそうだと思い実装。全部0/1にすると移動させる1/0を捨てる場所がなくて壊れることを指摘され、修正して提出するもWA。最初から0/1しか存在しない場合にも捨てる場所を用意してしまっていることに気づいたため修正しAC(0:22)。
次にJを渡されて考える。明らかに往復のどちらかは最短経路を使えばよい。帰りで新しく使う辺が1箇所以上存在するので、その辺を全探索すると解けることがわかる。実装も解法の説明も軽いと判断し、実装をshibhに押し付けてほかの問題を考えることにした。この後割とすぐ通してくれて3完(0:57)。
他の問題の概要をいくつか共有され、その中で一番解けそうな見た目をしていたEを考える。条件を満たさない行/列を消していくことを考えると、1回の操作で行と列をひとつずつ消すことはできそう。最後に行/列のどちらかが余った場合も2回の操作で2つずつ消していくことができ、これは明らかに操作回数の下界を達成しているので正当性がある。2つずつ消すと最後1箇所残ることに後から気づくが、これも適当にやると1回の操作で消すことができる。手で作った強めのケースが動いたので信じて投げるとAC(1:32)。
Gが実は愚直が通るという大胆予想を共有され、あってもおかしくないなと思い実装キューが空いたので実装してもらうもさすがにWA。
Cが解けているらしく実装してもらいますがWA。隣接の差分を見ると みたいな条件になるらしい。
の計算がバグっていたらしく直すも通らず。ここで自分もデバッグに参加して、
60 1 みたいなケースで壊れていることに気づく。
色々試すと未定義動作を踏んでいたっぽい挙動をしており、int128に変えるとAC(2:29)。
Kの解法をshibhから共有される。 を求めるパートと
を求めるパートの2つがあり、前半パートがBITを持ちながらDFSするとできるらしい。正しそうなので一緒に後半パートを考える。ある部分木からある部分木を抜いた部分の中で
番目に小さい頂点、みたいなものをクエリ毎に求める問題で、しばらく考えて並列二分探索で解けることに気づく。lower_boundのoff-by-oneや添字ミスでかなりバグらせた後、手元のケースが全て合い投げるもREが出る。
このあたりでshibhとkeymoonがGを解いており、PCを渡して実装してもらいAC(2:44)。
提出したKを印刷してしばらく眺めてもバグは見つからず、愚直解とランダムケース生成を書いたが、どれだけassertを追加しても落ちない。この時点で残り20分程度になっており通しきれるか怪しくなってきたので提出デバッグを開始。ひとつずつassertを減らすと、 として
の親ではない値が出てきていることがわかった。そんなわけないだろ！
TLEが出ていてKと交互に書いていたFをkeymoonが通し(4:54)、コンテストが終了。
あとからホテルでKの最後の提出をCodeForcesのミラーコンテストに投げてみると、自分のコードが負の値を出力していた。そこでやっとすべてに気づき、#define int long longと書いて提出してみるとAC。
よく見ると入力の制約にも と書いてあるのに
int で受け取っていた。そんなことある？重めの実装に気をとられて全く意識していませんでした……*3
Day3
ハロン湾に観光に行った。五時に起こすな！とか もっと近場に観光地ないの？とか思っていたが、行ってみるとそれなりに面白かった。
Day4
ホテルの近くにラーメン街みたいなところがあり、そこで横浜家系ラーメンを食べた。普通に店員に日本語が通じていて面白かった。
まとめ
コンテスト結果としてかなり散々で、特にKのオーバーフローに気づけなかったのに関しては本当に反省すべき。Fを通してもらわなければ更に散々だったので助けられた。
偉い人の話だとWFボーダーギリギリで通るか通らないかという感じの順位なようで、期待しすぎずに待ちたい。
shibhが他大学の大学院に進学するため今のチームとしてはこれが最後ですが、私はまだ4回くらいチャンスがあるのでこれからも頑張ります。
Good Bye!
