AtCoder Regular Contest 157 C - YY Square
メモ
グリッド上を通った経路について、スコアがあるものの^2で定まる時
そのスコアの合計を求めろという問題
スコアの計算がそのままでは複雑で、dpで漸化的に扱いにくい。
合計の合計という形にできれば、寄与について考えられる
解法1
n^2 = 1+3+5+ ... + 2n-1
で書けるので
各辺を使ったときに自分の前までに何回yyがあったかによって
その辺の寄与が分かる。
また、自分の前までのyyの回数の合計について
自分の全体での寄与が分かる形なので計算できる
解法2
dp[i][j] を1,1からi,jまでの問題とみなした時の答え
として、漸化的に^2のスコアを求める方法
各dp[i][j]まで持たれているパスの状態について、
sigma(x^2)とした時
次の遷移でsigma((x+c)^2)という形になっているため、
x^0, x^1, x^2をそれぞれ計算しておけば遷移できる。
あるいは、積の和典型で
今までのyyに印1, 印2を押す場合の数を考えるとすると
新しくyyが増えた時に、今までのに(0,1,2)回押していて、あたらしく増えた
yyに何回押すかという風に考えると
x^2というのが自然に複数の物の合計として扱えて遷移できる
