C - YY Square Editorial
by 
maspy
[1] 解説で用いる記号
- 文字列 \(P\) と文字 \(x\) の結合を \(Px\) と書くことにします．
- 文字列 \(P\) に対して，\(P\) が含む
YYの個数を \(f(P)\) で表すことにします． - \(\mathcal{P}_{i,j}\) で \((1,1)\) から \((i,j)\) に至る経路のなす文字列全体の多重集合を表すものとします．
本問題の答は \(\sum_{P\in \mathcal{P}_{H,W}} f(P)^2\) ということになります．
[2] 上手くいかない解法
本問に対する自然な発想のひとつは，各 \((i,j)\) に対して \(\mathrm{dp}[i][j]\) を
\[\mathrm{dp}[i][j] = \sum_{P\in \mathcal{P}_{i,j}} f(P)^2\]
によって定め，これを順に計算していくものです．つまり \((i,j)\) に書かれている文字を \(x\) とするとき
\[\mathcal{P}_{i,j} = \{Px\mid P\in \mathcal{P}_{i-1,j}\} \cup \{Px\mid P\in \mathcal{P}_{i,j-1}\}\]
が成り立つことを利用して，\(\mathrm{dp}[i][j]\) を \(\mathrm{dp}[i-1][j]\), \(\mathrm{dp}[i][j-1]\) から計算しようというものです．しかし，これは上手くいきません．例えばマス \((i-1,j)\) とマス \((i,j)\) の文字がともに Y である場合に，
\[\sum_{P\in \mathcal{P}_{i-1,j}} f(Px)^2 = \sum_{P\in \mathcal{P}_{i-1,j}} \bigl(f(P)+1\bigr)^2\]
は \(\sum_{P\in \mathcal{P}_{i-1,j}} f(P)^2\) から は計算できないためです．
[3] 解法
上で述べた問題は，dp に持たせる情報を増やすことで解決できます．次のように \(\mathrm{dp}[i][j]\) を定めます：
\[\mathrm{dp}[i][j] = \biggl(\sum_{P\in \mathcal{P}_{i,j}} f(P)^0,\sum_{P\in \mathcal{P}_{i,j}} f(P)^1,\sum_{P\in \mathcal{P}_{i,j}} f(P)^2\biggr)\]
つまり，最終的に興味があるものは \(2\) 乗和ですが，その計算の補助として \(0\) 乗和，\(1\) 乗和も dp に持たせることにします．
dp の遷移の計算は，本質的には次の計算に帰着されます：
\(S\) を多重集合とし，
\[a_0 = \sum_{x\in S}x^0,\qquad a_1 = \sum_{x\in S}x^1,\qquad a_2 = \sum_{x\in S}x^2\]
が与えられているとする．\(c\) を定数とするとき，
\[b_0 = \sum_{x\in S}(x+c)^0,\qquad b_1 = \sum_{x\in S}(x+c)^1,\qquad b_2 = \sum_{x\in S}(x+c)^2\]
を求めよ．
\(b_2 = \sum_{x\in S}(x^2+2cx+c^2) = a_2+2ca_1+c^2a_0\) などから，この答は \(b_0 = a_0, b_1 = a_1 + ca_0, b_2 = a_2 + 2ca_1 + c^2a_0^2\) となります．
【解答例】https://atcoder.jp/contests/arc157/submissions/39151958
[4] 参考：「積の和典型」の考え方
次のように考えることでも全く同じ解法に至ることができます．まず，問題文のスコアを次のように解釈します．
\(P\) のスコアとは，\(P\) 中の
YYのうちひとつに印 1、ひとつに印 2 をつける方法の個数である．（印は重複可能）
この問題は次によって定まる \(\mathrm{dp}[i][j][k]\) を順に計算することで解くことができます．
- \((i,j)\) に至る経路および，\(1\) から \(k\) までの印のついた経路上の
YYを定める方法の個数
新たに YY が生じたときに，その YY にいくつの印をつけるかを考えると dp の遷移が記述できます．
この \(\mathrm{dp}[i][j][k]\) やその遷移式は，実ははじめに述べた解法における \(\sum f(P)^k\) と同一です．なのでこの言い換えは特に新しい手法をもたらすものではないのですが，人によっては文字式の計算を考えるよりも，印をつける方法を数え上げる方が思考しやすくようです（例えば \(k=0,1\) の状態を dp に持たせる方針に気づきやすくなるということだと思います）．
今回は「\(2\) 乗の総和」でしたが，より一般に「総積の総和」というような状況で，総積を「ひとつずつ印をつける方法の数え上げ」と言い換えて考察する考え方は，日本の競技プログラミング界隈では「積の和典型」という愛称のもと，特に 2021 年頃から普及しています．
posted:
last update: