C - YY Square Editorial by ygussany
\(\mathrm{str}(P)\) 中の各 YY のスコアへの寄与を，前から順に \(1, 3, 5, \ldots\) であると見なすことにします．
実際，\(\mathrm{str}(P)\) 中に YY が \(k\) 回出現する場合，スコアは \(k^2\) であり，
\[1 + 3 + 5 + \cdots + (2k - 1) = \sum_{i = 1}^k (2i - 1) = k^2\]
が成り立つため，このように見なして構いません．
マス目上で Y 同士が隣り合う各箇所について，あり得る経路を全て考えたときの寄与の総和を計算できれば，その合計が答えとなります．
\(1 \le i < H,\ 1 \le j \le W\) として，\((i, j), (i + 1, j)\) の両方に Y が書かれているとします．
このとき，この部分の YY の寄与の総和は，
- \((i, j) \to (i + 1, j)\) の移動を含む経路の総数を \(a\)，
- そのような経路において，\((i, j)\) に至るまでに隣り合う
Yのマス間を移動した回数の総和を \(b\)，
とすると，\(a + 2b\) と表せます． ここで，
\[a = \binom{i+j-2}{i-1} \times \binom{H+W-i-j-1}{H-i-1}\]
です．
また，「 \((1, 1)\) から \((i, j)\) に至るまでの経路で隣り合う Y のマス間を移動した回数の総和」を \(\mathrm{dp}(i, j)\) として，これを素朴な動的計画法 (DP) で前計算しておけば，
\[b = \mathrm{dp}(i, j) \times \binom{H+W-i-j-1}{H-i-1}\]
と計算できます．
$\mathrm{dp}(i, j)$ の計算
$\mathrm{dp}(1, 1) = 0$ として，素朴に左と上から貰う DP を考えて，途中でYY があれば以下の値をさらに足します．
$1 < i \le H,\ 1 \le j \le W$ かつ $S_{i-1, j} = S_{i, j} = {}$Y のとき，$(i-1, j)$ に至る経路と同じ数だけ $(i-1, j) \to (i, j)$ の移動を経て $(i, j)$ に至る経路が存在するので，この分として $\mathrm{dp}(i, j)$ に $\displaystyle\binom{i+j-3}{i-2}$ を足します．
$1 \le i \le H,\ 1 < j \le W$ かつ $S_{i, j-1} = S_{i, j} = {}$Y のとき，$(i, j-1)$ に至る経路と同じ数だけ $(i, j-1) \to (i, j)$ の移動を経て $(i, j)$ に至る経路が存在するので，この分として $\mathrm{dp}(i, j)$ に $\displaystyle\binom{i+j-3}{i-1}$ を足します．
\(1 \le i \le H,\ 1 \le j < W\) として，\((i, j), (i, j + 1)\) の両方に Y が書かれている場合も同様にして計算できます．
前計算の DP も寄与の総和の計算も合計 \(\mathrm{O}(HW)\) 時間でできるので，この計算量で答えが求まります．
posted:
last update: