ICPC2023 アジア横浜大会　優勝記

2023 年度のアジア横浜大会に Speed Star で参加してきました。自分は非早生まれの M1 の代なので、今年が参加権のある最後の大会でした。 ICPC は参加し始めて 5 年目、やはり一度は WF に出たいという気持ちが強かったので、今回の横浜にはかなり気合を入れて臨んでいました。 結果として優勝できたのは本当に嬉しかったです。念願の WF(のはず) なので頑張りたい。

チームについて

去年までは KOMOREBI という同級生のチームで 4 年間出続けていましたが、チームメイトが段々競プロに割ける時間が少なくなってきたことと、一度は他の人とも組んでみたい気持ちもあったなど様々な事情から解散。本当はこのチームでも WF に行きたかったです。 新しいチームメイトとして元々目をつけていたのは SSRS だったので、まず初めに誘いました。SSRS に OK して貰えたのはよかったものの、そこからの 3 人目のチームメイト探しはかなり難航。というのも、東大の橙以上は大体が既にチームを所属が近い人達で組んでいて、余っている選手がほぼいませんでした。そのため、今年の初めの半年弱は SSRS と二人チームで Universal Cup 等の 5h コンテストに参加していました。

SSRS の競プロer としての特徴は、かなり多くのバチャやコンテストなどで見てきていたのでよく知っているつもりだった(大体自分と同じ早解き特化タイプで、自分よりかは高難度の典型・デが得意)のですが、実際にチームとして参加してみると思っていたより自分と得意はばらけていて、相性は悪くないんじゃないかな～的なことを思っていました。このあたりで多分チームに足りないのは(変な設定の問題が得意なタイプの)天才型かな、と認識していた気がします。

紆余曲折あって、そろそろメンバーを決めないといけないということで 5 月頃にツイッターで募集。DM してくれた Segtree が - (当時は黄色だったけど)橙 - 俺は高校の後輩で知ってる - SSRS とも JOI で交流がある - 得意は被らなさそう ということで三人目として誘いました。

この辺りから大体の担当は

noimi: 簡単-中盤枠、数え上げ、DP SSRS: 簡単-中盤枠、(数式弄るタイプの FPS 含む)数学、デ、典型、その他面倒枠(幾何とか) segtree: 構築、設定がキモい問題、インタラクティブ

みたいな感じでやっていた気がします。ただ noimi も SSRS も中難度までは割と万遍なく解くタイプで、かつ(コピペ検索アリなら)実装スピードもあまり変わらないということで、前半は解けた方から適当にやっていました。

練習としては UC, nowcoder で十分演習回数が足りていたのでその他は特に行いませんでした。

このチームはオンラインで 5h に出るときに問題概要を一読目で解けた問題以外は完全に discord に(最初から)書くという少し稀有な気がする作戦を取っていました。

これをしていた辺りから、SSRS の問題文読解速度の異常な速さがチーム内で話題になっていました。 自分も今まで累計で 10 回以上は CF div2-A の FA が取れたくらい英語問題文の斜め読み＋早解きには自信があったのですが、前にオフサイトで練習したときに同時に読んでみたところ俺より読むのが 3 倍は速くて完全に自信が破壊されました。

国内予選

まあ何しても通るだろと高をくくっていました。記憶があんまり定かではないんですが、確か BDE と SSRS と協力して G を解いたような気がする。 H が通されなかったことで優勝。 元々このチームは完数勝負にならない限りペナで国内チームに負けることはほぼないだろうなと思っていたので、予想通りの結果になって多少安心していました。

day -1 day 0

学部の頃入っていたサークルの駒場祭出店を手伝っていました。day 0 で OBOG と飲みに行ったら予想以上に飲む羽目になってしまい、1 時に帰宅して風呂で 3 時まで爆睡した上に翌日 6 時に起きて駒場に行ったので最悪でした。まあ前日なんて多少眠い方が本番前に寝れないなんてことがないからいっか！とか適当なことを思っていました。

day 1

駒場祭に行って、大学のトイレで嘔吐してから横浜に向かいました。この辺りのことは始まる前/負けた後に言ったらクソダサいかな～と思って言ってなかったのですが、勝ったから言えるぜ！でも割と体調は良かった気がします。

アジア予選前はある程度作戦を組んでいました。1 週間前くらいまでは、SSRS が JAG 夏合宿で一人でも序盤他チームに勝っていたことを考えると、マクロも要らないし一人で AB やらせてその間に他の問題を二人が読む、という作戦でいました。

ただ、本番の数日前に

という会話をし、納得したのでこの作戦に切り替えることにしました。確かに、UC 等の強いチームが多く出るコンテストでは、序盤から順位表情報が充実していて難易度が推定しやすいのですが、アジア予選の参加チームはそれに比べると強いチームは少ない上、上位のチームも早解き型ではないということで問題を先に把握する効用は確かに大きいと思いました。

リハーサル中に作戦の方向性を決め、いくつかの細かい取り決めを行いました。例えば、

  • SSRS が先に読んだ問題で読んだ瞬間に解けた問題が 2 問(X, Y) があった。どちらも自信があるが Y の方が明らかに知識/既出 driven で解けた問題であり、難しい。こういう場合は多少実装が遅くなっても先に Y を通してしまって他チームに非適切な情報を与えてしまった方が良いので Y から書く。

等です。

実際に決まったスタートの作戦は

SSRS: C 以降を読む segtree: PC のセットアップ→B もしくは SSRS から考察するべき問題を貰う noimi: PC のセットアップ中に A, B を解いてそのまま書き始める

というものでした。まあ B は解けなかったわけですが…

実際、序盤なんて一人でもいいと思うので、SSRS の役目を二人で担ってでも最初期に問題を把握するメリットは大きいんじゃないかなと思います。

チームの席が一番後ろだったので色々な知っている JAG スタッフの顔が見えました。知っている人に手を振ったり、ダル絡みしたりしていたんですが、非交流通知が出されていたみたいで、余り乗ってくれなくて悲しかったです。ちなみに JAG の人は、ツイッターが露悪的であればあるほど英語やだな～って顔で日本語で話しかけると日本語で回答してくれがちという法則を発見しました！

帰りの電車で SSRS とどうしたら tonosama に勝てるかな～という話をしていました。まあ問題セット次第なのはそれはそうで、難問枠が典型寄り/実装寄りだったりするか、簡単目のセットで全完(or 0 AC を除いた問題の速度)勝負だったりしたら勝てそうだが、AGC 的なパズルが出たらキツそうという話をしていました。

day 2　本番

コンテスト当日まで「東大チームに負けなくて 2 位以内なら WF はほぼ確」だと思っていたので、当日に tatyam から 1 位以外のチームは playoff 送りと聞いてひっくり返っていました。対 tonosama の勝ち負けはおまけだと思ってたのに… このことで、前日までは「まあ他の東大チームに負けなければいい」くらいの気持ちだったのが、「優勝しなければ…」という心構えに急に変わりました。 全然関係ないんですが、朝寝ぐせがヤバくて闘ってたら普通に遅刻しかけて悲しかったです。まさか入場最後とは…

本番はこんな感じでした (https://segtree.hatenablog.com/entry/2023/11/27/011031) で済まそうかなと思ったのですが、折角なので自分視点の動きも書いておくことにします。

(0:05 くらい) Segtree が PC 設定諸々終わる

この間に A は完全に解けていて、B の読解が中途半端みたいな感じでした。条件式がかかれていたので、そっちから理解しようとしたら案外変数が多かったのと割と解釈しずらい式で迷走してしまいました。 とりあえず PC を受け取って A を実装することにする。まあ DP かなとか思いつつ、DP 書くなら…と思ってマクロを一部書いてから実装することにした。

A AC(0:08)

このままパソコンの前で B を読んでる間に SSRS が全部読めた、F はすぐ書けるというのでパソコンを渡す。その間に何故か B の解釈が自分の中で入れ替わってて「あれ毎回長さ c のやつだけ見れば良くね？」みたいな謎の嘘で行けると思い込み始める。このタイミングで segtree は D が詰めれば終わると言われて渡されていた。

F AC(0:12)

SSRS が返ってきたので ↑ の B を書いたところ、書いている途中で大嘘に気づく。SSRS を呼び寄せて長さが c とは限らないんだよね～と相談開始したらすぐに変数分離じゃね？と言われてわからなかった自分を罵倒する。セグ木があれば一発ということがわかり、セグ木を写経するなら俺より速いということでパス。この間に segtree と D の確認をする。 概要と中身をさっと聞き、まああってそうだけど文字列の一致判定とか怠くね？みたいな話をするが、なんか行けるらしいのでそのまま任せて簡単と言われた H を読む。フローっぽいとだけ伝えられた。 順序と分割と二つのステップがあるのが怠いが、順序はいつものなのですぐわかる。順序を調べるときに書くいつもの式 (\sum s) v_1 + (\sum s + s1) v_2 \le (\sum s) v_2 + (\sum s + s2) v_1 を書いていたので、流れでΣをバラシて二点間の関係に落とすと後は燃やす埋めるそのまま。ここら辺のどっかで B が通る

B AC(0:25) segtree が D を書き始める。まあ H は Dinic 書かないといけないしパソコン貰えそうになってから細かい部分詰めるか、という気持ちになって一旦他の問題の概要を聞くことにした。 このタイミングで、SSRS が C, E, I : ムズそう J: 難しくなかったとしても面倒そう K: 謎 G: 中 みたいな評価が下していて、すぐに解けそうな問題はなかったので一旦 998 を中心に概要を大体聞いた。流石にそろそろ順位表を見ようと思い、見たところ E が tonosama にかなり速く解かれていたので E を考えることにする。確かこのタイミングで負けてて軽く萎えたような覚えがある。 D が少し燃えかけていたので H を実装に移る準備をしつつ解法を SSRS に聞いてもらい、一緒に辺の貼り方を考えてもらう(いつも Luzhiled's memo に頼り切りのため…)。初心に戻って普通に最小カットの方で解釈したら合ってそうだったので、D を印刷してもらってパソコンを貰う。Dinic を写経したりしてるうちに D のバグが分かってそうだったので、何回かパソコンの受け渡しをしつつ実装を進める。確かこの間に E が解けた気がする。通すまでが速い→変な解法じゃない　ということで多項式がすぐ見えて、O(M2N) を O(N 2N) に落とすのも、自分はこういったタイプの高速化が得意なので特に苦労せず出た。このタイミングで G も解けていた。

なんやかんやあって

D AC(0:53) H AC(0:57)

G もそこまで実装にかからなさそうだった上、E を詰めてから書き始めたかったので、まず SSRS に PC を渡す。バグった辺りで E が一瞬で書けることを主張して、印刷デバッグをしてもらっている間に E を AC。 この辺りで脳が起きてきて実装も早くなってきた気がする。

E AC(1:10)

無事にバグもその間に見つかり、すぐ修正出来ていた。

G AC(1:14)

E を解き終わった後にその後のムーブを考えた。 残りが C, I, J, K の 4 問で AC が出ているのが K 1 チームというとても動きづらい状況だった。 その段階での問題の評価が、

C: 回転がなかったらラグ反のアレで解けている、Polya を使えば解けそうだけど 2 周期以上の時も毎回取り切るは嘘 I: 幾何っぽいが進展は無 J: 差分が凸なのでそれを管理するタイプのマージテク木 DP っぽい K: インタラクティブで幾何だから嫌だけど、AC 出てるしそこまで難しくなさそう

ということで並行目に考えることにした。 segtree, SSRS: K noimi: C, J

の具合だったはず。C を少し考えたら 2 周期の時は回文が残ることが必要十分であることが分かり、まあどうせ 3 以上でもそうだろみたいなところまでわかったが、肝心の回文は長さごとに求める必要がありそうで困る。 J も DP は一気にマージする必要がありそうで、デカいところに一回ずつマージしていくみたいなことが出来ずに困る。(今見ている頂点で何回使ったかの情報もマージする過程では必要になるので) ただ下凸にはなるし流石にそういう系だろ…で固まる。

この間で K は解けそうという話になり、時間もあったので一旦全員で K を考える。SSRS が算数で出来ると主張しだしたが、ぼくは中学数学の式を見たくなかったので「信じるので一人で書いてください」みたいなことを言って丸投げした。

その間に J を考えていたが、台湾のチームが解いていることに気づく。実は Day 1 で確認していたのだが、台湾のチームは国内予選？で逆から見ると Incremental Bridge Connectivity になるだけの問題を解いていなかったので、そこが解いているということは凸性を保つタイプのマージとかではないんじゃないか…？と薄っすら思い始める。 配置できる必要十分な個数条件は有名なので、そっちを fix する方向で考えるとそれっぽい貪欲が思い浮かぶ。適当なケースとタイブレークを考えてみると、交換によって上手く回りそうなことをなんとなく確認したので segtree にも聞いてもらって一回書いてみようということになった。

K AC(1:47)

J は lazy segtree + HLD が必要だったので、上目遣いで SSRS を見つめて弱音を吐くことで代わりにそこを実装してもらうことに成功。空で書いててすげーとなった。この間に残り二人で I を考える。自分的には arg sort した後に両側累積ベクトル和を取った凸多角形について考えることが筋がよさそうだと思ったが、segtree は濃度で考えた方が分かりやすそうだとなったので、個人個人で考えることに。 自分の方針は実際には writer と同じだったのだが、完成形も同様に凸多角形で考えることが何故か思い浮かばず、そちら側は点で処理してしまっていたため解けなかった。

しばらくすると HLD が書き終わったので、受け取って書き始める。 アルゴリズムの中身自体は単純だが、軽くバグってしまった。HLD と main のどっちがバグってるかもわからなかったので SSRS とデバッグする。結果的には両方バグってて最悪だった。多少時間をかけたものの、そこまで炎上はせずに無事 1 発 AC。この問題はランダムテストを書くことを覚悟していたので、書かずに済んでよかった。そういえば結局一回も書かなかったな…

J AC(2:13)

segtree が I が多分解けたというので話を聞く。累積和で判定できると聞いて、まあ確かに arg 小さい方から使うべきだし微調整は出来るからあってそうという気持ちになった。SSRS は疑っていたが、まあ時間もあるしそれならすぐ実装できそうだからと思い、自分が書くことになった。二人に後ろから見てもらいながら書いていたが、自分が考えたわけではない解法の実装はあまり上手く行かないなと感じた。普段だったら「薄い方と濃い方で両方やるから最初から 2 回解くことを前提に～」みたいなことを考えるが、そのときは何も工夫せずにそのまま書いてしまった。 途中で SSRS に繰り返しは同じところで処理した方がいいのでは？a, b と c, d を swap すれば出来ると言われたのでそれでやった。そもそも a, b, c, d じゃなくて a[0], b[0], a[1], b[1] にするべきなんだよな～～～～ まあ何はともあれ書き終わり多少のバグを取って AC。

I AC(2:34)

解法が多少は不安だったので通って嬉しかった。グータッチをする。 ここで順位表を見て 2 位とかなりの差をつけた 10 完であることを確認した。C もかなりの進捗はある上に、2時間半あるなら多分通るだろと思っていた。ペナ差で負けることは無さそうだったので、落ち着いて C を解くことに。 まず全員に考察を共有して考え始める。回文と偶奇性について色々わかりはじめ、SSRS がカタラン数の K 乗の例の母関数を持ち込んでいたので(神！)具体的な式も立ち始める。結構複雑になりそうだったので、modint を segtree に写経してもらう。二人で落ち着いて 2 乗の式を立てて、サンプルを試すことにした。一発では合わなかったが、色々な箇所を直していくと無事サンプルがあった。ここからは計算量を落とすことに。

括弧列に直した後に、累積和の差が 0 に着地する回数と回文の長さで 2 乗の式を立てていたが、どちらを固定しても指数部分や分数部分が邪魔になって上手く式をまとめられないという話になったが、SSRS が畳み込みの式になることを指摘し、丁寧丁寧丁寧に式を変形、変形する度にコードも変えてサンプルを試し…とすることで無事畳み込みの式が出来た。 畳み込みを写経し、実装してみると(一回畳み込みの写経をミスったが)無事サンプルが合う。ただ、TL がかなり不安だったので 3e6 で一回手元で試すことにした。試したところ 0.8sec 程度で流石に通るだろ！と思いながら DOM judge を開いたところ 3:59:52 とかでめちゃくちゃ焦る。凍結前間に合わせてぇ～～～と言いながら急いで操作するものの、流石に間に合わず、提出が 4:00:03 に。手元で時間を見ていたことを少し後悔。

ジャッジにはめちゃくちゃ時間がかかっていたので、手元で約数の和がもっとも大きい数を探してみることにした。 こんなコードを書いた。

vector<int> d(3e6 + 1);
rep(i, 1, si(d)) {
  for(int j = 0; j += i; j <= 3e6) d[j] += i;
}

と書いていたら SSRS に「逆！逆！」と言われる。あー j と i どこか逆になったか？と思い見てみるが、合ってそうなので「え、いや合ってね？何が？」と聞いたら「for 文の順番です」と言われる。 見てみると自分が灰色以下であることが分かった。マクロに頼ってると for 文が書けなくなるんですよね～～～いや、流石に恥ずかしい。

そんなこんなしていたら C が通ったので喜ぶ。(あんまり嬉しそうにすると全完したのが分かってしまって他のチームに悪いかも、ということで予め喜びは抑えることに決めていた。) for 文が書けなかった恥ずかしさも吹き飛ぶ。

理論的にペナ差が逆転不可能であることを確認してから、残りの 1 時間は復習をしたり、弁当を食べたりしていた。この 1 時間で喜びも少しずつ収まってしまった。

振り返り

後でもう少し詳しく書く。

東大の他の 2 チームは全員が自分と同学年で、色々思うところはあったので、仮に自分達が優勝して引導を渡してしまうなら「あのペナがなければ…」みたいな差ではなく、断トツで勝ちたいという気持ちがあったので、その点は軽く安心していた。

終わった後にTwitterの当時の TL を見てみたら、案の定凍結直後提出についていろいろ言われていた。「こういうことしそうなチームではないが、流石にこれは偶々とは思えないのでのいみが考えたしかありえない。悪い顔をして提出している様が目に浮かぶ。最低なやつだ。」(意訳)みたいなことを言われていてゲラゲラ笑っていました、嘘です泣きました。 SSRS は終わった後やばい！天才！みたいに褒められていたのに、俺は性格の悪そうさについてのみ言及されていて悲しい。 hitonanode さんにその話をしたら「普段の行いですね😁」と言われた。そ、そんな…

まあ、おかげ様でこのコピペ検索禁止の時代遅れクソコンテストにもうしばらく出られることになったので、まだまだ頑張っていこうと思います。5h で対戦する皆さまよろしくお願いします。