メモ

yukicoderでゆるふわgolf

ABC249Ex解説の解説

公式解説の読解に5000兆年かかったので、記号や論理の展開の仕方を全て俺好みに書き換えたものを記す。
オリジナル：Editorial - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）


数列 A に対して、終了条件を満たすまでの操作回数の期待値を E(A) とおく。
数列 A が1回の操作で数列 A' に変化する確率を P(A,A') とおく。
数列 A と整数 v に対して、f(A,v)=|\{i \mid A_i=v\}| とおく。
もし ある関数 E':\mathbb{N}\to\mathbb{R} と定数 C であって、
★ \sum_{v=1}^{N}E'(f(A,v))=E(A)+C
を満たすものが存在し、E',C を求めることができれば元の問題には答えられる。（f(A,v) を全ての v について求めるのは O(N) でできるので）

・そもそもそんな E' は存在するのか
E' が満たすべき必要十分条件を考える。
E は定義から、関数等式 E(A)=1+\sum_{A'} P(A,A')E(A') を満たす。
逆にこの性質を持つ関数 g であって、終了条件を満たす全ての A で g(A)=0 を満たすならば g=E である。
この関数等式に E',f と E の関係式★をぶち込むと
\begin{eqnarray*} -C+\sum_{v=1}^{N}E'(f(A,v))&=&E(A)\\ &=&1+\sum_{A'} P(A,A')E(A')\\ &=&1+\sum_{A'} P(A,A')(-C+\sum_{v=1}^{N}E'(f(A',v))) \end{eqnarray*}
となり、整理することで
① 任意の A で \sum_{v=1}^{N}E'(f(A,v))=1+\sum_{A'} P(A,A')\sum_{v=1}^{N}E'(f(A',v))
という、E' が満たすべき関数等式を得る。さらに境界条件 「A が終了条件を満たすならば g(A)=0」から、C は C=E'(N)+(N-1)E'(0) を満たすよう取れば良い。
よって①を満たすことが必要十分。
この条件をさらに厳しくし、
①' 任意の A,v で E'(f(A,v))=\frac{1}{N}+\sum_{A'} P(A,A')E'(f(A',v))
を満たすものについて考えることにする。

ここで、\sum_{A'} P(A,A')E'(f(A',v)) を \sum_{y}E'(y)\sum_{f(A',v)=y} P(A,A') と書き換える。
\sum_{f(A',v)=y} P(A,A')、すなわち「A に対して1回操作を行った数列を A'とするとき、f(A',v)=y となる確率」は、操作を具体的に考察することで(←adhocポイント) f(A,v) のみに依存していることがわかるため、Q(f(A,v),y) と書ける。したがって①'は
①'' 任意の x で E'(x)=\frac{1}{N}+\sum_{y}E'(y)Q(x,y)
に置き換えられる。両辺 N 倍することで、E' は明らかに、ある吸収マルコフ連鎖における各状態から終端状態に到るまでのステップ数の期待値を表す関数として実現可能であることがわかる。以上により存在が示せた。

・E' を計算できるか
実際にE' を吸収マルコフ連鎖の期待値の関数だと思って計算したい気持ちになるので、やってみる。
全ての Q(x,y) がわかっているとする。
遷移行列をごちゃごちゃ計算すると O(N^3) で解けるがそれでは間に合わない。
操作を具体的に考察することで(←adhocポイント)、k>1 のとき Q(x,x+k)=0 となることがわかるので、遷移行列はほぼ三角行列になっている。
①''をぐっと睨むと E' に定数足したものも E' が満たすべき関数等式①''を満たすので、E'(0)の値を適当に決め打ちしてから、小さい方から順に求めていくことで O(N^2) で求められることがわかる。

・Q を計算できるか
できます。頑張れ