E - Reverse and Inversion Editorial by PCTprobability
\(2\) つの解法があるため、両方を解説します。
1.操作の特徴によって得られる \(\mathrm{O}(N\log M)\) 解法：本解説
2.dp を高速化することによって得られる \(\mathrm{O}(N\log M)\) 解法：https://atcoder.jp/contests/arc154/editorial/5565
\(2\) 個の解説の前半パートは全く同じものです。
\(f(P)\) は、\(\sum_{i=1}^{N} (j<i,P_j > P_i\) を満たす \(j\) の個数\()\times i -\sum_{i=1}^{N} (i<j,P_i > P_j\) を満たす \(j\) の個数\()\times i\) と等しいです。
以降、\(g(i):=「(j<i,P_j>P_i\) を満たす \(j\) の個数\()-(i<j,P_i>P_j\) を満たす \(j\) の個数\()\)」 とします。また、\(\mathrm{inv}(i) := 「P_j = i\) を満たす整数 \(j\) 」とします。
すると、\(g(i) = i - P_i\) が成り立ちます。
証明
$P=(1,2,\dots,N)$ のとき、$P_x=x$ であるため「$g(x)=x-x(=0)$」が成り立ちます。 ここで、$x$ の左にある要素を $1$ 個選び $x$ の右に移動させます。すると、その要素と $x$ の大小関係によらず $g(\mathrm{inv}(x))$ は $1$ 減ります。$x$ の右にある要素を左に移動させたときも同様に $1$ 増えます。 よって、$g(i)=i-P_i$ が成り立ちます。よって、\(f(P) = \sum_{i=1}^{N} i(i-P_i)\) が成り立ちます。なので、\(1 \le i \le N\) を満たす整数 \(i\) に対し、\(M\) 回の操作後に \(P_i\) のある位置の index の期待値を求められれば良いです。
重要な性質として、以下が成り立ちます。
- \(1\) 回でも操作によって反転させられた要素は、最終的な位置分布が左右対称になる。
証明
まず、$i$ 番目の要素が、操作によって反転する対象になって $j$ 番目に移動するような通り数は、$\min(i,N-i+1,j,N-j+1)$ 通りです。
ある要素に対して、その要素が反転する対象になった最後の操作に注目します。 その要素が、その操作を行う直前に $i$ 番目にあったとします。この要素が $j$ 番目に移動するような通り数と、$N-j+1$ 番目に移動するような通り数は上記より等しいです。 よって、全ての $i$ に対して総和を取った場合もこの要素の最終的な位置の分布は左右対称です。操作に \(1\) 回でも関わる確率は簡単に \(\mathrm{O}(\log M)\) で求めることが出来ます。この場合、最終的な位置の index の期待値は \(\frac{N+1}{2}\) です。そうでない場合の期待値は元の場所と同じです。
よって、この問題を \(\mathrm{O}(N\log M)\) で解くことが出来ました。
posted:
last update: