ICPC 2020 国内予選参加記

チーム結成

6/22のこのツイートから、私にとっては最初で最後のICPCへの挑戦が始まりました。

これを見たnrktさんからすぐにDMをいただき、さらに私の方からxelmephさんにオファーしたら快諾していただけたため、その日のうちにチームが結成できてしまいました。便利な時代になりましたね。

チーム名は「XENT」になりました。込められた意味については以下です。

チームメンバー紹介

nrktさん
国内予選時AtCoder水色。Pythonista。今回ICPC初参加。コミュ力が高そう、というか高い。実装が丁寧な印象。序盤の問題をペナを出さず安定した速度で埋めてくれて、チームに安心感をもたらす。後半は考察側に回り、ひたすら考えてくれる。私の考えた嘘解法を落とすサンプルケースを作るのが得意。ありがとうございます。

xelmephさん
国内予選時AtCoder青色。C++er。過去2回ICPC国内予選参加経験あり。PC周りの知識がかなりありそう。C++を理解している人が書きそうなコードを書く。グラフ系の問題が得意。万物からグラフ構造を見出せる特殊能力を持っているので「あーこれDAGになってるね」とかいきなり言い出すのだが、私はいつも理解が追いつけない。すごい。

本番前日

ICPC国内予選のジャッジは、テストケースをダウンロードし、ローカルでプログラムを実行して出力されたファイルを提出するという形で行われるので、想定解よりも時間計算量が多少悪くても、動いてしまえば勝ちです。

ルール改定により事前に準備したコードの貼り付けがOKになったことを存分に活用しようということで、xelmephさんがstd::mutexを使った並列処理のテンプレを準備していました。

f:id:Rorent:20201107122349p:plain

（まさかこの事前準備に救われることになろうとは、この時点では全く思っていませんでした……！）

本番

チーム練は主にオンラインでしていたのですが、やはり考察の共有やお互いの状況確認が容易との理由から、本番は大学のゼミ室を借りてそこに集まることとなりました。

当日16時頃に3人揃い、本番まで少しだけ作戦会議。練習でやってきた通りまずはAをnrktさん、Bを私、Cをxelmephさんが解くこと、わからなくなったらすぐ周りにHELPを求めること、「多分こうだろう」という考察をしてしまった部分を前提だと思い込まないように気を付けること、幾何や実装ゲーはxelmephさんに投げること、構文解析は私が多少は重点的に練習していたので解きたいということなどを確認しました。

そんなこんなしているうちにもう開始10分前です。さすがにいつものコンテストと同じように1分前に「ぞい」を呟くのはバタバタしてしまいますが、「ぞい」が早いと他の競プロerから「おもらし」と叩かれてしまいます。気合の入り方は手動と比較して弱くなってしまうのですが、仕方がないので今回は予約「ぞい」で妥協しました。

さて本番開始です。ブラウザの更新ボタンを押すと「database broken」みたいなエラーメッセージが表示されます。チームメイトも同じような状況。さすがにこんなことで今までのICPCに向けた精進・チーム練が水の泡になってしまうのは悲しすぎると思い、負荷を掛けてしまうのは承知で復旧したときにはすぐ問題を見れるように一心不乱に更新ボタンを連打していました。

5分経過した段階で、ふと「これが私たちのチームだけだったらどうしよう」という考えがよぎり、事前メールに書いてあった緊急連絡先に電話すると、繋がりませんでした。きっと他のチームも電話を掛けていたのでしょう。私たちだけではないと思えて、少し安心しました。

開始10分後やっと問題が見れるようになり、担当のB問題を開きましたが、 急なシステム回復でまだ心の準備ができていなかったようで、問題文がなかなか頭に入ってこなくて焦りました。丁寧に、冷静に読み直すと、どうやらUnionFindで順にマージしていって、頂点pを含む木のsizeを出力するだけのようです。実装すると、サンプルが合いません。まずいまずい。Bなんかで時間かけていられるもんか。

ここでnrktさんが「A通りました」と。「おつかれさまです」といいながら内心めちゃくちゃ焦っていました。nrktさんは「とりあえずD読みますね」とのこと。HELPを求めようか迷いましたが、もう一度考え直してみると、既にpと連結な頂点につながっている辺だけ処理すれば良さそう。書き直してサンプルが合い、ファイルを間違えないように慎重に提出するとAC。よかった〜。

「B通りました、xelmephさんCどんな感じですか？」と聞くと、「んー多分いけそう」 のような答えだったので、「じゃあ私もとりあえずDいきますね」と返答し、Dを開く。おっ、構文解析じゃんと、ちょっと嬉しくなる。

（こんなことを言っていたやつがいてですね）

Dを読んで、とりあえずサンプルを手計算で確認していたのですが、隣のxelmephさんの手が止まっていそう…？あんまり声を掛けすぎても焦りを助長してしまうのでよくないとは思いつつ、「どんな感じですか？HELPいきましょうか？」と聞くと、「 なんか実行が終わらないんだよね」と。

とりあえずCに戻り問題文を読むと、問題設定は非常にシンプルで理解しやすいものでした。「w固定して、残り全探索でいけると思う」とxelmephさんの考察を聞き、間違いなさそうなことを確認。私が問題概要を把握した頃xelmephさんのPCでプログラムの実行が終わったので、提出すると、なんとWA……！正直かなり焦りました。なにせペナが+20分と激重なので。このとき、早解きでは抜けられないなと覚悟していました。

先程の考察で合っているのは確信していたのですが、約数の個数のオーダーがあまりわかりません。ただ計算量を丁寧に見積もっていられるような冷静な状態ではなく、とりあえず数分で実装できそうなアルゴリズムだったので、「私も書いてみますね」と言って爆速で実装をしました。

実装完了しサンプルチェックをします。お…遅い……。サンプルで確か30秒程かかってしまいました。（あとで考えてみると、多分 p/w の約数を再び列挙していたのが原因だと思います。） 一応テストケースをダウンロードし、私のPCで進捗を出力しながらプログラムを実行しますが、終わる気配がありません。

xelmephさんにコードを確認してもらうと、同じことを書いているつもりとのことでしたが、とりあえず私のコードで出力された途中経過とxelmephさん側で出力された値の差異をチェックします。diffコマンドなんてものがあるんですね。私は目視でチェックする気満々でしたので、さすがxelmephさんでした。

どうやら数ケース出力される値が違いそう。しかし私のマシンでの実行は終わりません。
ここでxelmephさんが「並列実行するのでコード送って」と。それだ〜〜〜〜〜〜〜。

私のPCでの出力はもはや微動だにしないうちに、xelmephさんの方では並列実行パワーでテストケース2つとも実行終了し無事AC！本当にほっとしました。我ながらいいリカバーができたと思いますし、さらにxelmephさんの事前準備も活きて、チーム戦の醍醐味を感じました。あと、もしオンラインでやっていたら、こんな連携プレーなかなかできなかっただろうなと思います。

ただ、これ以降はチームでひたすら椅子を温め続けました……。問題ごとに感想を書きます。

D
私とnrktさんはほぼここに張り付いていました。
構文解析パートは簡単。そこをささっと書いて、next_permutationでサンプルが合った、わいわいとしているうちは楽しかったかも。
O(n!) はもちろん無理。階乗のオーダー落とすのは大抵bitDPなんですよねとか考えたが、どうもうまくいかなさそう。 最終的な結果を決めうち？でも例えばSから'A'が出力されるとしてS中に'A'が複数あるときはどれが勝ったことにすればいいんだろう……。（ここの考察をもう少し詰めるべきでしたね）
|S| ≦ 100 で、一つの式は5文字からなるので、最大20程度の式しかなさそう（この評価は間違っていそうです）で、式を評価した結果を220で全探索すればうまくいく？そしてその結果になるような全順序の場合の数を求められればよさそう、bitDPでトポソの数え上げ？どうやるんだっけ…うーん……。
としているうちにタイムアップ。

E
ぱっと見包除で解けそうな感じがするよねという話になったが、結局最後まで分からず。通しているチーム数も少なく、これよりはDのがチャンスがあると思っていました。

F
残り1時間となった頃に、xelmephさんが読んですぐに「Undo可能なUnionFindで辺の重みが小さい順に消去していくだけな気がする」と言っていて、私も少し考えてみると、確かに合っていそうな気がします。その時刻で避難所の候補でなくなったものをチェックする処理を愚直にやると間に合わない気がしましたが、UnionFind木の根だけチェックすればうまく処理できそうという話になりました。xelmephさんに私のライブラリを渡し実装を託すも、最後まで答えが合わず、タイムアップとなってしまいました。

G
私は読んでいません。

H
チラ見程度。 最小包含円とかいうやつなのかな？わかりません。

結果・感想

3完で全体70位でした。

f:id:Rorent:20201108005543p:plain

「あと1問の壁」を越えたかったけど、やっぱりその壁は高かったです。コンテスト終了直後、やり切った感じは全くありませんでした。
不甲斐ない成績ではありましたが、名古屋大学では1位で、どうやら国内予選を突破できそうとのことです。よかった……！この数ヶ月間の私たちなりの努力が報われたようで、本当に嬉しかったです。成績に関してくよくよ言ってももう仕方がないですし、予選突破できたことに胸を張っていきたいです。

私はオンサイトの大会にいくことが競プロerとしての一つの目標でしたので、アジア地区大会が楽しみでなりません。トップ競プロerの強さを肌で感じたいです。またせっかくの機会ですし、TLでお見かけする競プロerさんとの交流も積極的にしていけたらいいなと思っています。

コンテスタントとしての目標は、「あと1問の壁を越える」こととしておきます。長時間のチーム戦をすると、私たちの実力だと大抵「ここからあと1問解けるかどうか」という状況になってくるんですよね。今までのチーム練や各種の有志コンではなかなかその壁を突破することができなかったですし、今回の国内予選でもそうでした。アジア地区大会までにさらに精進を重ねて、本番では清々しくコンテスト終了を迎えることができたらなと思います。