WUPC2020 参加記
WUPC2020に、ICPCチームメンバーであるxelmephさん（@Xelmh）と2人で参加しました。
私にとっては初めてのチーム戦でしたので、記念に参加記を綴っておきたいと思います。
コンテスト前
同じ大学なのでもちろん地理的な距離も近く、せっかくの機会なので顔合わせも兼ねてオンサイトでチーム戦をしようということになりました。ICPCチームメンバーのもう一人は他の用事が重なってしまったため、今回は2人での参戦に。
まだTwitterとLINEでしか繋がっていない関係性でしたので、駅で待ち合わせをしてちゃんと実在の人間が現れたときはほっとしました。幻覚ではなかったと信じています。
早めにランチを済ませてxelmephさんのお家にお邪魔する予定だったのですが、食後のアイスティーのサーブが遅れ、 お家についたのはコンテスト30分前でした。時間に余裕を持っておいてよかった〜。 若干焦りつつ物理的な環境構築とアカウント作成、登録を済ませ、とりあえず序盤は奇数問を私、偶数問をxelmephさんが読み進めていこうという打ち合わせをしていると、あれよあれよという間にコンテストが開始しました。ICPCはもう少し気持ちの準備をする時間が取れるといいな。
コンテスト中の立ち回り
Aは私が通します。（0:03）
その間にxelmephさんがBの考察を終わらせ提出するもWA。後から提出コードを見るに、0でないという条件を見落としてしまっていたようです。しかし焦らずすぐにリカバー、さすがの冷静沈着さでした。（0:09）
（Bはコンテスト終了後に読んだのですが、私はすぐには解けなかった気がします。）
Cを読んで、考察ノート上でいじくりまわしていたら二項係数が見えてきたので私が実装します。前日にOSのクリーンインストールをして環境構築をし直していたため、modintのスニペットが展開されないバグに襲われ焦りましたが、「mint」と入力して一呼吸待ってからTabを押すとちゃんと出てきました。（これだから重いエディタさんは……。）提出すると無事AC。ふー、一安心。（0:29）
私がCを解き終えてEとGを読んでいた頃、xelmephさんが「J、SCCするだけでは？」と。読み進めるの早いなー。考察を聞いてみると確かに解けそうな気がしてきます。ということで、SCCのライブラリを持っていた私が実装を担当。しかしsample3が合いません。落ち着いてsample3の図を見ると、非連結な島もあるじゃん、ということに気付きます。DSUで予め同じ塊にあるかどうかを判定すればいいのでは、と書いてみると、sampleが合いました。ほっとしながら提出するとなぜかWAを食らう。あれあれ、困りました。（0:46）
2人で固執しても仕方ないと思い、Jの再考察をxelmephさんに任せて私は他の問題を読みにいきます。 ここで順位表を確認すると、Fがかなり解かれている様子。既にFを読んでいるxelmephさん曰く、「ちょっと考えたけど、あんまり見えてこなかった。」とのこと。これは私が解かねばな、と開いて考察。15分ほど考えて、ジャンプできる回数が素因数2の個数と等しくなることは見えてくるも、sample2を見るとジャンプ回数が多い方がいいってわけでもなさそう。うーん。
私のFの考察が行き詰まっていたので、とりあえずここまでの考察をxelmephさんに話して2人で考えていると、ジャンプする回数をすべて試せば良いことに気付きました。やっぱり考えをまとめて人に話すのって大事だなぁと実感。
実装はシンプル、サクサクっと書き上げました。が、最大ケースのsample3が合いません。えぇ…… 。
私がバグに苦しんでいる間に、xelmephさんがJのうまくいかない原因を解明し手直しして再提出するもWA。この辺り、暗雲が立ち込めていましたね。（1:30）
その後もどうもFのバグの原因が私には見つけられなかったので、コードを見せながらxelmephさんに相談すると、「ここって、intでいいの？」と。あああああ！！それだ！！！私はなんてド初心者ムーブをかましてしまったんでしょう……。llに書き換えてさくっとAC。このバグで20分くらい無駄にしました、大変申し訳ありませんでした……。（1:48）
改めて順位表を見にいき、どれを仕留めようか考えます。E、G、J、Mが狙い目っぽい。まだ読んでいなかったMを開くと、問題文に全方位木DPをしてくださいと書いてありました。グラフ問題はxelmephさんの得意分野なのですが、抽象化全方位木DPをライブラリとして持っている私の方がさすがに早く書けるかもと判断し、Mの実装を担当します。
ここでxelmephさんも一旦Jを離れ、Gに移ることに。ただのナップサックDPをした後に、できたDPテーブルを再利用すれば休憩の処理がうまくできそうなことを序盤に見出していたので、その考察を伝えた上であとはお任せしました。
私がMの実装を終えてsampleを試すと、それっぽい値を出力しながらも若干ズレています。xelmephさんに泣きつくと、私の考えた遷移が間違っていることが判明。DPの値と別に、部分木の明るさの合計値も管理しなければいけなさそうなことに気付き、実装し直し。無事ACです。（2:27）
xelmephさんはGの実装をバグらせている様子。私はナップサックDPに対しての苦手意識を未だ払拭できないままなので、頑張れ頑張れと応援するのみ。すみませんでした。
私はMをACした後、Eに向かいました。Nが入る場合と入らない場合で分けてcombinationやらいろいろすれば解けそうだなと思って考察を進めるも、次々と例外パターンが出てきます。この方針じゃうまくいかなさそう……。 xelmephさんに少しEを考えてもらったところ、素因数分解してbitDPできそうとのこと。私には微塵も見えなかった方針でびっくりしちゃいました。
ここでEをxelmephさんに任せ、Gは私にバトンタッチです。Gを改めて考察してみると、曖昧だった休憩の処理方針が鮮明に見えてきました。実装すると、なんと一発でsampleが合いました。あれあれ、もしかして私DP得意かも？と心の中で少し誇らしげに。提出したら一発AC。これは気持ちよかった。（3:39）
これ以降、終了までほとんどの時間をxelmephさんはE、私はJに費やしました。 Jについてですが、SCCしてDAG上でトポソ順にDPすれば、ある頂点に関してそれより上流にある頂点は全部列挙できそうだと思い、bitsetを持たせたDPを書くも、提出前になんとなく予感はしていた通りのMLE。その後もずっと考え続けましたが何も手が出ませんでした。
終了3分前、ついにxelmephさんがEのバグを手元では取りきりsampleを合わせて提出するも、22/33まではACで、23ケース目でRE……うっうっ……。でも粘りがすごかったです。私は隣でうーんうーんと言う機械になってしまっていたので。
そんなこんなでコンテストが終了しました。結果は6完の87位。青コーダー2人のチームとしては不甲斐ない結果となってしまいましたが、初めてのチーム戦、とっても楽しかったのでよしです。
感想・反省
考察がまだ不十分な状態だったとしても、言語化してチームメイトに伝えることによって、自分の考えもまとまってくるし、自分には思いつかなかったアイデアもいただけるしで良い事づくしだなと思いました。ただ、実装している最中はさすがにあまり声をかけすぎないようにした方がいいと反省。3人であれば、1人実装しつつ、他の2人で考察するスタイルはありだなと思いました。
また上述の反省とも繋がるのですが、中終盤は個人戦に専念しすぎず、同じ問題を複数人で考えた方が解ける確率が高いように感じました。今回で言えば、最後EかJのどちらかに2人で挑んでいれば、少なくともあと1問は通せたように思います。
自分用の覚書として書いている部分も大いにあるので書き殴りの文章になってしまいましたが、私の初めての競プロチーム戦参加記は以上です。WUPCの運営の皆さん、このような楽しい機会をご提供いただきありがとうございました。
