D - Add to Square Editorial
by 
maspy
[1] 操作後のマス目の状態の特徴付け
操作前のマス目を \(A\)、操作後のマス目を \(B\) と書くことにします。
各行・各列に対して、書かれている数の交代和が操作不変量となります。つまり、次が成り立ちます：
- 任意の \(i\) に対して、\(\sum_{j=1}^W A_{ij} (-1)^{i+j} = \sum_{j=1}^W B_{ij} (-1)^{i+j}\)
- 任意の \(j\) に対して、\(\sum_{i=1}^H A_{ij} (-1)^{i+j} = \sum_{i=1}^H B_{ij} (-1)^{i+j}\)
したがってこれら \(H+W\) 個の式が成り立つことが、\(B\) が操作によって得られることの必要条件となります。
この必要条件が、\(B\) が操作によって得られるための十分条件でもあることを確かめましょう。
\(i, j\) について昇順に、正方形\(A_{i,j}, A_{i,j+1}, A_{i+1,j}, A_{i+1,j+1}\) に対する操作で\(A_{i,j}\) を \(B_{i,j}\) に一致させると、\(1\leq i < H\) かつ \(1\leq j < W\) に対して \(A_{i,j}\) を \(B_{i,j}\) に一致させることができます。
- 行ごと、列ごとの交代和が等しい
- \(1\leq i < H\), \(1\leq j < W\) に対してマス \((i,j)\) の値が等しい
とき、すべてのマスの値が等しいので、必要条件を満たすとき上の手順で \(A\) を \(B\) に一致させることが可能です。
[2] 問題の言い換え
交代和の扱いを簡単にするため、マス \((i,j)\) の値を \((-1)^{i+j}\) 倍して考えることにすると、本問は次のように言い換えることが出来ます。
マス目の状態 \(A\) が与えられる。 マス目の状態 \(B\) であって、各行・各列の和が \(A\) と等しいものに対して、\(\sum |B_{ij}|\) を最小にせよ。
\(A\) の各行・各列の和を \(x_i, y_j\) などと書くことで、さらに次のように言い換えておきます。
\(\sum x_i = \sum y_j\) を満たす数列 \((x_1, \ldots, x_H)\) および \((y_1, \ldots, y_W)\) が与えられる。 マス目の状態 \(B\) であって、各行・各列の和が \(x_i\), \(y_j\) に等しいものに対して、\(\sum |B_{ij}|\) を最小にせよ。
さらに \(B_{i,j} = 0\) からはじめて、\(B_{i,j} = b\) に変化させる操作を行いながら、各行の和と \(x_i\)・各列の和と \(y_j\) の差を変化させていくことを考えると、次のように言い換えられます。
\(\sum x_i = \sum y_j\) を満たす数列 \((x_1, \ldots, x_H)\) および \((y_1, \ldots, y_W)\) が与えられる。次の操作によって、最小コストですべての \(x_i, y_j\) が \(0\) であるようにせよ。
操作 \((i, j, b)\)：\(x_i\) と \(y_j\) に \(-b\) を加える。この操作にはコスト \(|b|\) かかる。
[3] 最適解の構築
\(X = \sum |x_i|\), \(Y = \sum |y_j|\) とします。操作 \((i,j,b)\) によって \(X, Y\) は高々 \(|b|\) しか変化しません。よって、次が成り立ちます：
- \(最小コスト \geq \max\{X, Y\}\)
この不等式において、等号が成り立つことを示します。実際、次の操作列によって最小コストが実現できます。
- \(x_i < 0\) かつ \(y_j < 0\) となる \((i,j)\) があるならば、操作 \((i,j,-1)\) を行う。これを可能な限り繰り返す。
- \(x_i > 0\) かつ \(y_j > 0\) となる \((i,j)\) があるならば、操作 \((i,j,+1)\) を行う。これを可能な限り繰り返す。
- \(x_{i_1} > 0\) かつ \(x_{i_2} < 0\) となる \((i_1,i_2)\) があるならば、操作 \((i_1, 1, 1)\) と操作 \((i_2,1,-1)\) を行う。これを可能な限り繰り返す。
- \(y_{j_1} > 0\) かつ \(y_{j_2} < 0\) となる \((j_1,j_2)\) があるならば、操作 \((1,j_1, 1)\) と操作 \((1,j_2,-1)\) を行う。これを可能な限り繰り返す。
実際、
- 操作の過程で常に \(\max\{\sum |x_i|,\sum |y_j|\}\) が操作コストと等しい分だけ減少すること
- 最終的に \(\sum |x_i| = \sum |y_j| = 0\) に到達すること
を確かめればよいですが、このことは、
- 操作の過程で常に \(\sum x_i = \sum y_j\) が成り立つこと
- したがって、操作 1, 2 を可能な限り行ったとき、\(\sum |x_i|=0\) または \( \sum |y_j| =0\) が成り立つこと
などに注目すると証明できます。
この証明は最適解の構築方法も与えており、以上をまとめると本問題は\(\Theta(HW)\) 時間で解くことができます。
[4] 参考：操作不変量と多項式
[1] の結論は、多項式を用いた議論で導くこともできます。
マス目の状態 \(A\) に \(2\) 変数多項式 \(\sum_{i,j} A_{i,j} x^iy^j\) を対応させると、本問題の操作は \((1+x)(1+y) \mid P\) となる多項式 \(P\) を加えることと解釈できます。
多項式環 \(\mathbb{Z}[x,y]\) は一意分解整域であり、既約多項式 \(f, g\) （\(f\neq \pm g\)）と多項式 \(P\) に対して \(fg\mid P \iff f\mid P \text{かつ} g\mid P\) が成り立つので、
\[(1+x)(1+y)\mid P(x,y) \iff 1+x\mid P(x,y) \text{かつ} 1+y\mid P(x,y) \iff P(-1,y) = P(x,-1) = 0\]
が成り立ちます。ここから各行・各列の交代和による特徴づけが得られます。
posted:
last update: