Yandex Cup参加記、書いてます。本当です。現在1万字強。

12/02(月)

12/03(火)

12/04(水)

12/05(木)

12/06(金)

午後3時過ぎに自宅到着。MHC Tシャツが届いていた。

pic.twitter.com/jwKnxWYwJW
— こたつがめ (@kotatsugame_t) 2024年12月6日

機内で横になれたからか思ったより眠くない。手っ取り早く荷解きを済ませ、シャワーを浴びて洗濯まで行った。自宅最寄り駅から濡れた落ち葉でいっぱいの路面を転がしてきたスーツケースの車輪が大変なことになっており、その掃除が一番大変だった。

家族LINEに帰宅報告をし、流れで少し旅行の話をしたり写真を送ったりしつつ日記を書いていた。午後11時半就寝。

12/07(土)

午前10時前に目を覚まして2時間弱なろうを読んでいた。そこから少し二度寝して、午後2時からUniversal Cup。今日は20回目でKunmingセット。

https://qoj.ac/contest/1871

書く

起きた直後はなんだか頭が痛い気がしたし、コンテスト序盤はまともに頭が回っていなかったが、5hを走り終えた今は全くの快調。単に寝すぎだったらしい。

午後9時からABC383。

Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383） - AtCoder

Aはちょっと面倒。Bはかなり面倒。Cは多始点BFS。Dは $p^8$ と $p^2q^2$ しかない。Eは軽い辺から順に使いつつ、連結成分内でできる限りマッチングさせる。Fは色ごとに $2(X+1)$ 状態のdpをする。

Gは大変。分割統治を考えるとmax-plus畳み込みが高速にできればよいが、これは列が上に凸なら線形時間になる。上に凸であることは意味的に成立しそう。しかし今回はさらに端を $O(K^2)$ 通り考える必要があり、マージの度畳み込みが $O(K^3)$ 回発生。つまり列の長さが $O(N/K)$ であることを踏まえて $O(K^2 N\log N)$ になる。

Concave Max Plus Convolution | Library

ところが動かしてみると全然間に合わない。そこで自明な $O(N^2/K)$ のdpを書いてみた。ベクトル化が効きやすい形を意識して書いてみて、QCFium法を適用すると、 $K=4,5$ では何とか間に合うようになった。さらに先ほどの畳み込みも高速になって、 $K=1,2,3$ では間に合うようになった。組み合わせてAC。

75分で全完して8位。自分が窃盗してきた畳み込みライブラリは列の片方が上に凸なら動くもので、高度なことをしている。両方上に凸なら差分の列をマージするだけでよく、定数倍がかなり違うらしい。想定解はそれを用いた $O(K^2 N\log N)$ で、自分で書いて出してみると632msと確かに爆速だった。

www.youtube.com

現在開催中のAHC040に提出しようとしたが、考え込んでいるうちに強い眠気が襲ってきた。午前3時就寝。

12/08(日)

午前11時起床。昨晩のMHC Final Roundの結果を見た。今年は日本人少なめ、というか昨年が異常だっただけか。異常でない回でも決勝進出できるようになりたい。

Meta Hacker Cup - 2024 - Final Round

AHC040に提出した。

HACK TO THE FUTURE 2025 (AtCoder Heuristic Contest 040) - AtCoder

夜まで遊びに行きたいけどその前にシャワーを浴びなきゃな、など考えながらグダグダしているうち、部屋の寒さに耐えかねて布団に入ってしまい、二度寝した。3時間ほど経って起きたら午後7時になっていた。

食事してシャワーを浴び、午後9時からARC189。正確にはARC189 div.2である。

AtCoder Regular Contest 189 (Div. 2) - AtCoder

Aは $A$ の連結成分ごとに独立に考えられる。条件としては両端の数字が合っている必要があり、操作列の長さと場合の数は小さいケースを手で解けば法則が見えた。Bは差分を取ると一つ置きのswapだとわかる。後から考えてみると、図形的にイメージすれば一発だったのかもしれない。ともかく残りのパートは簡単で、差分の列を交互に取ってソートすればよい。

Cは赤のみ・青のみの場合最適な操作列がすぐわかる。順列から作ったサイクルグラフの上でボールをどんどん進めていくとよい。そしてこの操作列は途中に $i\ne X$ での操作をいくら追加しても破壊されないから、二つの操作列を同時に部分列として含むように操作すれば目標を達成できる。最短にするには二つの列のLCSが求まればよく、それぞれの列で要素の重複がないので $O(N\log N)$ で解ける。

DはCFで見覚えがある。今の大きさでマージできる範囲を調べマージする、ということを2回繰り返すと大きさが倍になるので、 $O(\log\max A)$ 回の反復で終了するというもの。マージできる範囲を調べるのはセグ木上の二分探索で $O(\log N)$ になる。よって全体で $O(N\log N\log\max A)$ 。

Eは大変。実験により6頂点で最大値3の解が見つかり、手でお絵かきして次のような構造を見出した：6頂点を3頂点ずつ $U$ 、 $V$ に分割する。また $u\in U$ 、 $v\in V$ を固定する。このとき $U-U$ 、 $V-V$ を番号1、 $U\setminus\{u\}-V\setminus\{v\}$ 、 $u-v$ を番号2、 $U\setminus\{u\}-v$ 、 $u-V\setminus\{v\}$ を番号3とする。

この一般化として、 $U$ 、 $V$ をそれぞれ $N/2$ 頂点ずつの分割とすることが考えられる。そして試してみると実際validだった。これで4以上の偶数 $N$ に対して最大値3の解が構築できた。最大値2は……無理だろう。これで偶数については解決。

奇数については、 $N=5$ で最大値4なので、それ以降も最大値4だろうと予想した。 $N-1$ 頂点の解を適当に拡張すると構築できたので、これで完璧だろうと思って提出すると、WA。ちょうど7個WAが出たので、 $N=7,9,11,13,15,17,19$ が間違っているものと思われる。すなわち、これらに対して最大値3が達成できるらしい！

もうちょっとガチャガチャして、次のような構築を考えた：奇数 $N$ に対し、頂点の分割 $U$ 、 $V$ を $|U|=|V|+1$ となるように取る。そして上で使った $u$ の代わりに $u_1,u_2\in U$ を固定する。あとはほぼ同様。

なぜこれで良い完全グラフになっているのか、詳しいところはわからないが、どうやら $|U\setminus\{u_1,u_2\}|=|V\setminus\{v\}|\ge 2$ となっているのが重要らしい。 $N=5$ はこれを満たせないので、最大値4となってしまったということ。ともかく $N\ge 7$ で最大値3が達成できたので改めて提出し、無事通った。

100分1ペナで全完し、なんと優勝。ABC以外では初めて。

www.youtube.com

振り返りをギリギリで終わらせ、午後11時半からCF #992 div.2。

Dashboard - Codeforces Round 992 (Div. 2) - Codeforces

Aは全探索。Bは $k$ 手で長さ $n$ まで埋められるなら $k+1$ 手では $2(n+1)$ まで伸ばせる。Cは $\{1,\dots,n-1\}$ を二つに分割して $n$ の左右に並べた $p$ のみ考えることになり、先頭から決めていける。

Dは木を二部グラフと見て、偶数のうち小さいものと大きなものに分割するのが基本方針。一か所だけ差が2になり得るので、そこを気合いで処理した。後から葉を一つ特別扱いすれば楽だと気付いた。Eはある頂点でランダムに動いた場合、次数を $d$ として上に行くまでの期待値が $2d-1$ となる。これが大きい頂点でコインを使うとよい。

Fはバーンサイドの補題。3次元にそれぞれ $(x,y,z)$ だけシフトしたとき固定されるパターンの数え上げに失敗し続けていた。シフト操作で移りあうマスのグループのサイズ $g$ は、 $gx\equiv 0\pmod{a}$ 、 $gy\equiv 0\pmod{b}$ 、 $gz\equiv 0\pmod{c}$ を満たす最小の正整数だから、LCMで計算できる。数え上げには $g$ だけあればよいから、同じ $g$ になる $(x,y,z)$ をまとめて処理する。すると $g$ の種類は $abc$ の約数の個数だけしかないので、毎回 $O(k)$ かけても間に合う。