D - Minimize Inversion 解説
by 
potato167
\(f(P)\) について以下が成り立ちます。
\(L_{P_{i}}\) を \(j < i\) かつ、\(P_{j} < P_{i}\) を満たす \(j\) の数とする。 \(R_{P_{j}}\) を \(i > j\) かつ、\(P_{j} < P_{i}\) を満たす \(j\) の数とする。 このとき、\(f(P) = \sum_{i = 1}^{N} \min(L_{i}, R_{i})\)
これは、\(A_{i} < A_{j}\) が成り立つか否かには、\(P_{i} < P_{j}\) ならば、\(A_{j}\) の正負のみで決まり、\(P_{i} > P_{j}\) ならば、\(A_{i}\) の正負のみで決まることから示せます。
\(X[i][j]\) を \(P_{K} = i\) を満たす全ての \(P\) に対する、\(\min(L_{j}, R_{j})\) の総和とします。
すると、答えは \(\sum X[a][j]\) とあらわせます。
全ての \(X[a][j]\) を求めたいです。
\(a > j\) のとき
\(0\) 以上 \(j\) 未満の任意の整数 \(b\) に対して、以下が成り立ちます。
- \(L_{j} = b\) かつ \(P_{K} = a\) を満たす順列 \(P\) の場合の数は \(\dfrac{(N - 1)!}{j}\)
よって、\(X[a][j] = \displaystyle\dfrac{(N - 1)!}{j}\sum_{b = 0}^{j - 1}\min(b, j - 1 - b)\) となります。この値は、階乗や逆数を前計算していれば \(O(1)\) で求まります。
\(a = j\) のとき
\(L_{j}, R_{j}\) を固定したとき、\(P\) が何通りあるかは以下の式で表せます。
\[\binom{K - 1}{L}\cdot \binom{N - K}{R}\cdot(j - 1)!\cdot(N - j)!\]
よって、任意の \(L, R\) について、\(\binom{K - 1}{L}\cdot \binom{N - K}{R}\cdot\min(L, R)\) の総和を求めれば良いです。
愚直に計算すると \(O(j)\) で \(X[j][j]\) は求められますが、全ての \(j\) に対して \(X[j][j]\) を愚直に求めると TLE してしまいます。よって、全ての \(j\) に対する \(X[j][j]\) を畳み込みを用いて同時に求めます。
\(L< R\) かつ \(L + R + 1 = j\) を満たす整数の \(L, R\) に対する \(\binom{K - 1}{L}\cdot \binom{N - K}{R}\cdot\min(L, R)\) の総和を \(Y_{j}\) とします。
多項式 \(f(x), g(x)\) を以下が成り立つように定義します。
- \([x^{l}]f(x) = \binom{K - 1}{l}\cdot l\)
- \([x^{r}]g(x) = \binom{N - K}{r}\)
すると、\(Y_{j}\) に対して以下の式が成り立ちます。
\[Y_{j} = \sum_{L + R = j - 1, L < R}[x^{l}]f(x)\cdot[x^{r}]g(x)\]
\(L < R\) という条件がなければ畳み込みを \(1\) 回すれば任意の \(j\) に対して \(Y_{j}\) が求めれられます。
\(L < R\) という条件があっても、分割統治と畳み込みを用いれば時間計算量 \(O(N\log^{2}(N))\) で求められます。
以上で \(L < R\) の場合の \(X[j][j]\) に対する寄与が求められました。\(L\geq R\) の場合も同様にして求められます。
\(a < j\) のとき
\(a > j\) のときと同様の考えで \(\displaystyle\sum_{k = 1}^{N}X[k][j] = \dfrac{N!}{j}\sum_{b = 0}^{j - 1}\min(b, j - 1 - b)\) が成り立ちます。
また、\(k < j\) を満たす任意の \(X[k][j]\) について値が変わらないことと、\(k > j\) を満たす任意の \(X[k][j]\) について値が変わらないことと、\(X[j][j]\) の値が上で計算できていることから \(X[a][j]\) は \(O(1)\) で計算できます。
任意の \(i, j\) に対して \(X[i][j]\) が求められたので、元の問題も適切に差分更新することで答えが求められます。
具体的には、上記の情報をもとに \(\sum X[1][j]\) を求めた後、\(\sum X[a + 1][j] - \sum X[a][j] = X[a + 1][a + 1] - X[a][a] + X[a + 1][a] - X[a][a + 1]\) が成り立つことを用いて、\(a = 2, 3, \dots, N\) の順に \(\sum X[a][j]\) を求めれば良いです。
\(a = j\) のときの \(X[a][j]\) を求める部分がボトルネックとなって、時間計算量は \(O(N\log^{2}{N})\) です。
追記
この問題が \(O(N)\) で解けることがコンテスト中に発覚しました。解法については、i_am_noob さんによる以下の解説を参照してください。
投稿日時:
最終更新: