ICPC2020アジア地区大会参加記

私qLethon(@pu__Ne)、totori(@totori_kpr)、binくん(@5bin101)の3人で チームATELIERで出ました。

結果は7完16位でした。良い結果だったと思います。 f:id:qlethon:20210318045528p:plain

1日目

一週間続いたAHCにより生活が壊れていて前日(？)朝7時に寝たため、かなりギリギリまで寝ていました。 受付は13:30までです。

なんとか受付を済ませ(全体的に確認作業は押していたっぽい)開会式を済ませます。

ログインに手こずりコンテストに若干遅れて参加したため、通話に参加したときは既にととりとbinくんがそれぞれABを読み始めていました。
私はチームメイトにテキトーにやっていいことを確認した上でCを読む宣言をしDを読み始めます。 Aを通したととりにゃあがDを読んでいたらしく、私が黙ってDを読んでいたことに若干キレていました。
Dは普通に分からないのでCを読んだあと、Bを通したbinくんに問題概要を説明します。 2人で考えて、binくんが2つの集合をマージしていく方針を考え、私がある点集合を取ったときにすべて同じ傾きにできるかという判定部分をO(N2)でできるという主張をしました。 方針をbinくんに伝え、私はやばかった大学の書類に少し手を付けた後実装に加わりましたが、間に合いませんでした。ととりはいつの間にかDを通していた。

コンテストが終わると冷えたAHCのレートが来ていました。思ったより高くて安心です。

ここからが本番です。
ICPCには早寝早起き部門というのがあり、1日目は早寝フェーズです。 しかしここは生活崩壊のプロ。開会式前に無理やり起きたおかげで今日は十分に眠いです。なんと22:30に寝ます。

2日目

まずは早起きフェーズです。00:30に起きます。優勝です。(絶望)
その後結局3:00くらいまで起きた後なんとか寝直して、なんと余裕を持って8:00に目覚めます。(開会式は8:45開始)

あまりの芸術点の高さに農工大メンバーからは歓声が上がりました。

余裕をもって目覚め、朝の心地よい空気の中意気揚々と開会式のzoomに入ると、迷子案内所にたどり着きました。

運営の方は我々のことをとても良く分かっていると思います。

前日までICPC本番であることの実感が全く無かったのですが、朝の清々しい空気と開会式により徐々に実感を得ます。気分は部活の試合時の朝集合です。高校では科学部でした。

チームミーティングが始まり今日の作戦を決めます。私はABをバグらせるので後ろを担当しろとととりに言われました。素晴らしい作戦だ。

コンテスト

ぞいの鳴る音と同時に私は一番後ろのKから読み始めます。難しそうなのですぐに飛ばしてJを読み始めます。 Jは簡単そうです。既に数チームが解いていて、問題も単純です。Bを通したととりにゃあにJKの報告をして、Jは通せそうなので他を任せます。まもなくJが通ります。通りました。(0:46)

Aは手こずっていたようで、ととりにゃあが介抱に行っていました。しばらくすると通ります。(1:12(+1))

C, E, G, H, Iあたりが次に解ける候補に上がっていて、私はIを少し考えたのですが、私の解く問題ではないと感じGを考えます。

しばらく考えると、ととりにゃあがGを分かりかけているらしいので私が今まで分かったこと(必要十分条件(未証明))を伝えて他の問題に行きます。
必要条件は連結成分を圧縮して二部グラフを考えるとすぐに分かります。二部グラフに必要な最小の辺を引いたあと、良い感じに接続し直すと制約を満たすように辺が貼れて、十分っぽい感じがします。

IはやりたくないのでHを考えます。素因数ごとに考えると、GCDのLCMは小さい方からk + 1番目を選ぶ操作であることが分かります。素数は大体105個あるのでこれだと間に合わないのでなんとかします。なりませんでした。 一応いろいろ考えたので後ろに書いておきます。

途中でととりのGは通ります。(証明: AC) (2:09(+1))

さらにbinくんと介抱のととりがIを通します。天才。(3:15) ここで私はHを諦めCとEの問題概要を聞きます。どう考えてもCが一番おもしろそうなのでCをやります。

制約にスタートとゴールは壁に接していると書いてあります。この制約は右手法を使わせるための制約です。6行で右手法を書けることをととりに報告すると、6未満手数全探索でいけそうとの返答がありました。それで解けそうですが、問題はシミュレーションを書かなくてはならないことです。厚い信頼により実装を任されます。

通話をスピーカーミュートし黙々と書きます。大体60分くらいで実装とデバッグが終わり通ります。(4:51)
通話に戻るとEのコードがバグっているようでした。ととりとbinくんの環境でサンプルの結果が違うらしく、2人は未定義動作を疑っていました。ととりが投げるとなぜか通ります。(4:57(+1))

ラスト10分で2完した勢いでととりがD, F, H, Kも投げます。
ここでATELIERに全完2位WF出場の可能性が芽生えます。

閉会式

1問ごとにCMが流れる解説を聞き流し、まもなくするとYes/Noが始まります。ICPCのメインイベントです。
eat_iceが潜伏作戦を取っていて、凍結後の順位表で全11問提出確定0ACの異常になっており、非常に盛り上がりました。少しでも会場の盛り上がりに近い雰囲気を感じたいと思い、Gatherで近くの人間の反応を盗み聞きしていました。Gather唯一の有効活用法です。

ATELIERもそこそこの盛り上がりを演じて16位に着けました。
同じ農工大のチームnowcowの2つ下です。

懇親会

閉会式が終わると懇親会の時間です。社交性のない人間にとってはないのと同じなので夜に開かれるであろうボドゲ/Among Usに備えて寝ます。

懇親会-夜の部-

起きると公式懇親会は既に終わっていました。
競プLoLでボドゲ大会が開催されていたのでそれに混ざり、その後はAmong Usをやりました。ここでかなり知らない人とお話ができたので良かったです。ゲームはコミュ障を救う。

感想

前日まであまり実感もモチベもなかったのですが、やってみるとかなり楽しく今までで一番短い5時間コンテストでした。(後から振り返ると、何をやっていたんだ？という気持ちになる)。
開会式などではかなり社会性がない人間競プロer向けの配慮がされていました。また、閉会式の進行などを聞いていても運営側の競プロへの思いが伝わってきました。非常に丁寧な対応で、今まで出場したコンテストの中で一番雰囲気が好きでした。スタッフも競プロ関係者[要出典]なのがそういった心象を与えたのかな。ICPCサイコ～～～ 来年も出ます。

Hの考察

TODO: 書かない

数列に含まれる素因数の数はO(NlogA)なので、素数ごとにいくつの要素で使われているか((2, 2, 6)なら2は3つの要素で使われていて、3は1つの要素で使われている)を持っておき、逆に$i$個の要素で使われている素数のリストも持っておきます。そうすると、クエリの範囲が多いときは$R - L$ - 1個