ICPC 2025 横浜参加記 - PCTprobability's blog

ICPC 2025 Asia Yokohama Regional に参加して 2 位を獲得し、playoff への進出権を獲得しました。色々といつもと環境が違ったため無事好成績を獲得できて良かったです。

チームメンバー

PCTprobability

B1
数え上げが一番の得意分野、次の長所は実装速度

harurun4635

B3
最近橙になり、実力をめきめきつけてきている。唯一のチームの幾何担当

kemuniku

B3
LR クエリが大好き。このチームで一番英語が出来る。

今回の目標は優勝だが、優勝の確率最大化程ではなく、とりあえず playoff に通過できる確率を出来るだけ上げつつ、優勝も狙うくらいの気持ちでいた。

ICPC 国内予選との違いとして、問題文が英語であることと US キーボードを使用しなければならないことが挙げられる。そこで、ダウンロード出来る yokohama の PC の環境において、設定から入力形式を US から JIS に変更できることに気付いたため使ってみることにした。問題点として以下が挙げられるが、普段 JIS を使っている人が US に適用するよりは楽だと思う。(今後の playoff や WF でも出来るとは限らないため、真似する人は自己責任でお願いします。)

| と _ を入力できるキーがないため、bitor,or で代用し、補間などを上手く使うか #define pb push_back などを US の状態で予め打っておく必要がある。
] の位置が JIS と違い [ の右にあるのでこれだけは慣れる必要がある。
焦って手元の配列を見ても欲しいものの位置が分からない。

スケジュールに 9:00 - 14:30 と書いてあるためコンテストがいつ始まるか謎だなと思っていたら突然あと 3 分で始まると言われてしまいびっくりした。

kemuniku に色々と環境構築をしてもらっている間に harurun と手分けして問題文を読むが、英語が出来ないため本当に何も読めない。C の sample の図に助けられてなんとか理解して考えていると、harurun が D が解けたと言っているため簡単枠なら任せておく。ただ結局 harurun が混乱してしまったらしく自分が引き受けて AC した。(0:13)

C は最適解だけならば AtCoder で既出であり、構築方法を考えているととりあえず右端と左端が繋がっていない解を 1 個構築した上で、1-i,j-n のペアを j-i にしたい。ここで先入れ先出しの貪欲をすると 1 のペアは出来るだけ小さくなり、n のペアは出来るだけ大きくなるため都合が良い。最適性は示せていなかったが行けると思ったため提出して AC。(0:30)

コンテスト中は謎の自信があったが今考えてみると貪欲の最適性が示せない。証明募集中です。

証明

右端と左端を切り離して考える。区間数を $x$ 、もし右端と左端が繋がっているとしたら 1-i,j-n を j-i とマッチさせられるペアの個数の最大値を $y$ としたときの $x-y$ を最小化したい。 $x$ は上の構築が最小値を与えている。また、1 のマッチ相手は出来るだけ小さく、n のマッチ相手は出来るだけ大きくなっているため $x$ の最小値を取る中で $y$ が最大化されていることも分かる。

$x$ が最適でない構築について、その構築を元に $x$ を達成する構築を作ることが出来る。この問題を $a_i,a_{i+1}$ の間にこの 2 要素の大小関係によって + や - が置かれており、+ - となっている完全マッチングを作る問題と捉える。そして、 $x$ が最適でない解は +,- を 1 個ずつ同じ場所に追加することを繰り返してから完全マッチングを作っていると考えると [a,b],[b+1,c] を [a,c] とマッチさせることを繰り返して $x$ を達成する解を構築できる。また、この操作によって $y$ は減っても高々 $1$ である。よって上記の構築は最適解を与える。

E が簡単枠と渡されたので考えてみると、long double で二分探索してから $\lfloor \frac{a}{x} \rfloor,\lfloor \frac{b}{x} \rfloor,\lfloor \frac{c}{x} \rfloor$ を計算すれば最適な $x$ の値が有理数表示で得られる。少しだけ怖かったが AC。(0:38)

H の考察を kemuniku から受け取る。常に左上のマスが属するコの字の位置が決まるというのは正しそうなので実装をして AC。(0:45)

J の考察を harurun から受け取る。かなり面倒そうだったが気を付けながら実装して AC。(1:00)

A の考察を harurun から受け取る。下界が達成できるらしいので書いてみると WA。コードを印刷してもらうと考察ミスと実装ミスが両方あったらしいので直して AC。(1:19(+1))

考察ストックがなくなってしまったので G を考えてみる。条件としては最大値が次に大きい値+1 以下であることと、最大値が一意ならそれより奥に最大値-1 があることと予想出来る。実際に正しそうなので 2 乗を書いてみると合わない。困ってしまった。その間に harurun から I が区間に分割して区間の端によって alice 有利や bob 有利や引き分けなどがありその総和を取るなどで解けたと言われたので書いてみると WA。

結構色々なバグを含んでいたが、ここでランテスを書かずにぺナが多数出てしまった。ゲーム問題はすぐランテスが書けるので 1 ぺナが出たら書いてしまってもいいかもしれない。

G で上手い言いかえが思いつかずに FPS で処理してしまった。簡単に記しておくと、とりあえず頻出する以下の問題の答えを $f(n,m,k)$ を置く。

長さ $n$ の整数列で全要素が $0$ 以上 $m$ 以下の数列のうち、総和が $k$ のものの個数 $= \lbrack x^k \rbrack \left(\frac{1-x^{m+1}}{1-x}\right)^n$

包除原理を用いて $\mathrm{O}(\frac{k}{m})$ で解くことが出来る。とりあえず余事象を考えることにする。最大値が次に大きい値 + 2 以上であるケースは最大値 $a$ 全探索で $\mathrm{O}(\sum \frac{K}{a}) = \mathrm{O}(K \log K)$ で処理できる。

最大値が一意かつ最大値 - 1 が全て最大値より左にあるケースを考える。最大値 $a$ と $a-1$ の個数 $b$ を考えると $\sum_{a=1}^{M-1} \sum_{b=1}^{N-1} \binom{n}{b+1} f(N-b-1,a-2,K-(a-1)(b+1)-1)$ となる。 $a-1$ を $a$ で置き換え、 $b+1$ を $b$ で置き換え、 $b=0,1$ は個別に取り除くことにすると $\sum_{a=0}^{M-2} \sum_{b=0}^{N} \binom{n}{b} f(N-b,a-1,K-1-ab)$ となる。b の sum を取り出すと $\sum_{b=0}^{N} \binom{n}{b} \lbrack x^{K-1-ab} \rbrack \left(\frac{1-x^{a}}{1-x}\right)^{N-b}$ となり、二項展開を考えると $\lbrack x^{K-1} \rbrack \left(x^a + \frac{1-x^{a}}{1-x}\right)^N = \left( \frac{1-x^{a+1}}{1-x}\right)^N$ となる。ここまで来たら後は調和級数で $\mathrm{O}(K \log K)$ で求まる。

いま改めて考えてみると最大値を 1 減らすと簡単な全単射が作れるという話を FPS で無駄に長々と処理してしまったように見える。ただ機械的な処理で問題が解けるというのは FPS の良いところが出たとも思う。

G を通して I もランテスを書いて通した。(2:33,2:45(+3)) 6 完まではかなり早かったが中盤の処理にもたついてしまい 8 完ペナルティーで strong zero に負けてしまっていた。

残った問題を開くとなかなかに絶望する。しかも 2:59 時点で strong zero が L を通したため +2 完が必要になってしまった。L を harurun に完全に任せて残った問題の中ではまともそうな B に取り組んでみる。kemuniku とのコミュニケーションエラーで消していい箇所が 1 箇所だけと暫く思い込んでいたが、なんとか気づいて修正する。

解の構造を考えると前から順に以下のようになっている。

全て 0 になっている部分( $\lbrack 1,m \rbrack$ 要素目)
全体から定数が引かれている区間( $\lbrack m+1,k \rbrack$ 要素目)
0 にした要素 1 個( $k+1$ 要素目)
完全に残っている部分( $\lbrack k+2,n \rbrack$ 要素目)

$m$ 番目の要素までを全て 0 になっている部分にするとき、何回の操作に耐えられるか？を考えてみる。ここで、0 にした要素で区間を分割し、ある区間に注目した際最小値が最も前にないならばその要素を 0 にすることでより良い解を得られる。これを繰り返すと残す区間は単調増加であることを要求出来て、その場合長さ 3 以上の区間を残すのは無意味であることが分かる。よって線形時間で何回の操作に耐えられるかはわかる。この値を $x_m$ と置いておく。

ここまでは割とすんなり分かったがこの後で困ってしまう。 $\lbrack m+1,k \rbrack$ に 0 があってはならないため、残りの操作回数に応じて $k$ として選べる要素の範囲が決まってしまう。monge なども疑ったがよく分からないしそもそもスライドアクセスすら出来る気がしない。

ふとして、k 番目までで操作が止まっているならばこの間に 0 が発生しても操作回数 $\times (k-m)$ をコストとして引いてもいいことに気付く。なぜならばこのようにしても評価関数が悪化しているだけであり、かつ最適解においてはそのような 0 は発生しない(もしするならばそのうちもっとも手前の要素を予め 0 にしておくのがより良い解を生じさせる。)

肝心な k 番目までで操作が止まっているならば、については $a_{m+1}$ が 0 になっていなければ満たせている。更に、もし 0 になってしまったとしてもその場合は $m$ を $1$ 増やせばいいため $a_{m+1}$ が 0 になっていないを条件につけても最適解は悪化しない。

これで k を固定したときに CHT を使うと $\mathrm{O}(\log N)$ で計算できるようになった。(正確には CHT に i = n,n-1,... の順で直線を追加していき、i = k まで追加した時に欲しいクエリを呼ぶことになる。)ただまだ k の候補が $\mathrm{O}(N)$ 通りあるため困ってしまった。

ここ $k$ は耐えられる回数が操作回数以下である限り出来るだけ大きく取った方がいいという予想が浮かんだ。もし $k \le d$ が許されるとする。まず、 $x_{d-2} + a_{d-1} \le x_d$ が成り立つ。つまり、 $k = d-2$ と取っても $a_{d-1}$ は 0 になるということである。よって、 $k = d-2$ と取るくらいなら $k = d-1$ と取ってしまってよい。 $d-3$ 以下についても同様にして $k$ の候補を $d,d-1$ に絞り込める。本番はここまで詰め切っていた訳ではないが、同じようなことを感じて $k = d,d-1$ のみを試す愚直を投げてみると TLE と言われたため CHT を書いてみる。すると AC を取る。これで逆転の道が開けた。(4:28(+2))

ほぼ同時期に L に sample が一致したため投げてみるも WA。幾何が出来ないため K を考えつつも harurun に全てを託したが残念ながらコンテスト終了まで通ることはなかった。惜しい。

結果的に strong zero は 2:59 の AC 以降何も通していないようで惜しくも 1 位を逃してしまった。序盤の速度がかなり速かったらしく、中盤がぐだっていなければペナルティータイムで勝つことも可能だっただけに無念。

表彰台で英語でのコメントを要求されてしまい困ってしまった。結果的に kemuniku に全てを任せた。その後の懇親会でも色々な人と話せて楽しかった。台湾の方にクッキーのお土産をいただいた。

懇親会のあとに Rinshan Solution + sounansya + Nachia + mitani + ponjuice + rice_tawara という面子でラウンドワンに遊びに行っていた。楽しかったが ICPC が終わったあとに行く場所ではない。体が持たない。

結局優勝は出来なかっため playoff で WF の権利を賭けて争う必要が出来てしまった。今回は US キーボード + 英語ときて次回は環境自体も海外。頑張ります。