【AtCoder】C - YY Square / AtCoder Regular Contest 157 - あめんばーどのバーチャル日記

久々のマイ解法記事。

atcoder.jp

解けたんですがTLで見た解法や解説の解法と違ってて「？？？」となっていたのでとりあえず自分の解法をまとめます。 maspyさんの書かれた解説とほぼ同じな気がしますので見方のひとつくらいに思ってください。

考えたのは全体的に数値の遷移は二次式になるよなぁ、と思ったこと。二乗の値は $x$ が $1$ 増えると $x^{2}$ は $2x+1$ 増えるし1次とか０次とかの情報あると嬉しいよなぁ、といろいろ書き下して思いました。

じゃあ二次式として3つの値を持たせたdpにすればよさそうね。というわけで

$\displaystyle dp[i][j]=(i,j)まで移動した時の二次式の和$

dp[0][0]は二乗した結果が $0$ になってほしいので $x$ になんかを代入したら $0$ になる平方の二次式が良いでしょう。

$\displaystyle dp[0][0]=x^2$

これを用意して最後に $x=0$ を代入します。別に $x^{2}-2x+1$ とかにして最後に $1$ 代入でも同じになると思いますたぶん。言うなればこの二次式は「 $(0,0)$ までYYを通った回数を代入した時のスコア」なので

ではサンプルのこいつで考えてみましょう

2 2
YY
XY

dp[0][0]はさっきも定義した通り $x^{2}$
dp[1][0]はY->Xに辿るのでxが増えたりしません。 $x^{2}$
dp[0][1]はY->Yで辿るのでxがx+1になってくれますね。 $x^{2}+2x+1$
dp[1][1]は左からは $x^{2}$ がそのまま来ます。上からはY->Yなのでさらにxにx+1が代入され $x^{2}+4x+4$ になります。合計で $2x^{2}+4x+4$ 。

というわけで答えは最後に $x=0$ をぶちこんだ定数項の $4$ と出力。

一般化するならば遷移元の二次式が $ax^{2}+bx+c$ として

Y→Yならxにx+1を代入した $ax^{2}+(2a+b)x+(a+b+c)$ を遷移先に加算
それ以外なら $ax^{2}+bx+c$ をそのまま加算

となる。

と、ここまで書いたら $a$ には最終的にスタートからゴールまでのルートの個数が入るし、 $b$ にはY->Yを通った回数の総和×2が入りそうな上にそれはY->Yになっている場所を探してコンビネーションを求めれば普通に求まりそうだからそういう方法を使ってるのかなーと思いました。

int main() {
  ll h, w;
  cin >> h >> w;
  auto s = read<string>(h);
  vector dp(h, vector(w, vector<mint2>(3, 0)));
  dp[0][0][2] = 1;
  REP(i, h) {
    REP(j, w) {
      if (i < h - 1) {
        if (s[i][j] == 'Y' && s[i + 1][j] == 'Y') {
          dp[i + 1][j][2] += dp[i][j][2];
          dp[i + 1][j][1] += dp[i][j][2] * 2 + dp[i][j][1];
          dp[i + 1][j][0] += dp[i][j][2] + dp[i][j][0] + dp[i][j][1];
        }
        else {
          REP(k, 3)
            dp[i + 1][j][k] += dp[i][j][k];
        }
      }
      if (j < w - 1) {
        if (s[i][j] == 'Y' && s[i][j + 1] == 'Y') {
          dp[i][j + 1][2] += dp[i][j][2];
          dp[i][j + 1][1] += dp[i][j][2] * 2 + dp[i][j][1];
          dp[i][j + 1][0] += dp[i][j][2] + dp[i][j][0] + dp[i][j][1];
        }
        else {
          REP(k, 3)
            dp[i][j + 1][k] += dp[i][j][k];
        }

      }
    }
  }
  cout << dp.back().back()[0].val();
  return 0;
}

atcoder.jp