AGC 046 B. Extension - okura diary

水diffだが解けなかったので自戒の意を込めて記録。

制約から2乗のDPかと思い考えたがうまく重複せずに数えられずDPでない方針を考えた。その結果いろいろと言い換えはできた(各ブロックは下か左のどちらかから見え、どちらからも見えるものはない等)が、うまく数え上げられず解説を見た。

この問題を解く上で大切な意識は「一つの状態を作るための操作列は様々ありうるが、一つの状態を一つの操作列に1対1に対応させる」ということだった。

今回の場合、一番上の行に黒マスが1つしかないならば最後の操作は行の追加、そうでないならば最後の列の操作である、としてよいことが鍵となる。あとは素直にDPできる。

void solve() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  auto dp = vect(C + 1, vect(D + 1, vect(3, mint(0))));
  dp[A][B][0] = mint(1);
  for (int i = A; i <= C; i++) {
    for (int j = B; j <= D; j++) {
      if (i == A && j == B) continue;
      if (i > A) {
        dp[i][j][0] = dp[i][j - 1][0] * mint(i - 1);
        dp[i][j][1] =
            (dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]) * mint(j);
        dp[i][j][2] = dp[i][j - 1][1] + dp[i][j - 1][2] * mint(i);
      } else {
        dp[i][j][0] = dp[i][j - 1][0] * mint(i - 1);
        dp[i][j][1] = dp[i][j - 1][0] + dp[i][j - 1][1] * mint(i - 1);
        dp[i][j][2] = dp[i][j - 1][1] + dp[i][j - 1][2] * mint(i);
      }
    }
  }
  cout << dp[C][D][0] + dp[C][D][1] + dp[C][D][2] << endl;
  return;
}