ICPC2019 国内予選 参加記
ICPC2019 国内予選に参加しました。nicklawさん、NOSSさんと私のチームで4完41位、学内1位で予選突破しました。
チームメイトの参加記
やったこと
A問題は縦方向の和のmaxなので私が秒で実装し、通しました。Bをnicklawさんに書いてもらっている間に、私がC、NOSSさんがDを考察していました。
Cを生やした（つもりになっていましたが、誤読でした・・・）のでDの概要をNOSSさんに聞いて、しばらく考察していました。するとNOSSさんが「dpでは？」と言い、何やら遷移を生やし始めたので信じることにしました（実装の方針などを私も少し考えました）。
BがWAったので私がCを書き始めたのですが、この時点で誤読に気づいてめちゃくちゃ焦りました。間もなくBが修正できたようなので実装をしてもらうことにして、Cを解き直していました。nicklawさんがBを通したので、Cの解き直しを2人で行いました。
解法は、各分銅に対して使わない、左に乗せる、右に乗せるを全探索して、(右に乗せる重さの和 - 左に乗せる重さの和)を列挙します。これで全てのaを作れれば0、そうでないなら作れなかったもののうち1つに対して、a - (右に乗せる重さ - 左に乗せる重さ)を追加する分銅の重さの候補として列挙します。これらの候補及び既存の分銅を用いて全てのaを作れるか判定する、といった感じでした。
これを実装すると無限にサンプルが合わないのでプリントデバッグに入り、NOSSさんがDの実装を始めました。後でわかったのですが、合わなかった原因は、追加する分銅を左に乗せるか右に乗せるかを考慮するのを忘れていたことでした。
この間2人でCとDを書いてはバグらせ書いては無限時間実行され書いてはバグらせを繰り返し、その間nicklawさんも含めてバグ探しに専念しました。2完が見えて焦り始めていたところでCとDを立て続けに通せました。Cは先述したところの修正をしたら通りました。Dは計算量的にやばかったのですが、コンパイルオプション-O3をつけたら爆速で実行されて通すことができました。
この時点で残り1時間ほどでしたが、Eは実装が重そうなので飛ばし、Fを3人で考えました（何も生えませんでした）。
反省
- 早とちりしないで紙で実装をちゃんと詰めること
- コンパイル時点での最適化は大事
- ワンマンプレイをしない
感想（という名のポエム）
まずはなんと言っても、目標にしていたアジア大会出場を曲がりなりにも達成できてよかったです。自分自身としても嬉しいですし、M1の先輩の最後のICPCで国内予選を突破できたことが嬉しかったです。また、おそらくチームのうち誰一人欠けても4完はできなかったと思います（チームメイトもすごかったし、自分が抜けても危うかったと自負してる（ほんまか？））し、チームプレイをちゃんとできたのかなというところが最高でした。小中高通じてこれと言って何かをやった経験があまりなかった自分にとって、大学で競技プログラミングに出会い、打ち込めるようになったこと、それを仲間とともにできる環境があったこと、ICPCに出られたこと、全てが夢のように思え、奇跡であると感じています。このめぐり合わせに感謝しつつ、アジア大会に向けて日々過ごしていきたいなと思います。
