Zenn
📑

ABC 183 | E - Queen on Grid

2020/11/16に公開
競プロ
累積和
動的計画法
tech

問題

https://atcoder.jp/contests/abc183/tasks/abc183_e

考えたこと

典型的なDPかと思ったが、クイーンが次のマスを超えて壁まで飛んでる。よって2 \leq H,W \leq 2000の条件だとO(n^3)になってTLEしてしまう。

まずdp[i][j]をi,jマスに移動する方法とし、障害物のない4マスx4マスの以下の場合を考えてみる。

dp[3][3]を求めるには以下である。

\begin{aligned} dp[3][3] = & \ dp[2][3] + dp[1][3] + dp[0][3] \\\\ & + dp[2][2] + dp[1][1] + dp[0][0] \\\\ & + dp[3][2] + dp[3][1] + dp[3][0] \end{aligned}

縦・横・斜めにおいてそれぞれの、累積和が使えそうである。
dpx[i][j]を(i-1,j)までの縦方向の累積和、dpy[i][j]を(i,j-1)までの横方向の累積和、dpz[i][j]を(i-1, j-1)までの累積和とすると以下のように変形できる。

\begin{aligned} dp[3][3] = & \ dpx[3][3] + dpy[3][3] + dpz[3][3] \end{aligned}

よって各(i,j)においてブロックでない場合に以下を順に計算すればよい。

\begin{aligned} dpx[i][j] = dp[i-1][j] + dpx[i-1][j]; dpy[i][j] = dp[i][j-1] + dpy[i][j-1]; dpz[i][j] = dp[i-1][j-1] + dpz[i-1][j-1]; dp[i][j] = dpx[i][j] + dpy[i][j] + dpz[i][j]; \end{aligned}

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

using mint = modint1000000007;

int main() {
  ll h, w;
  cin >> h >> w;
  vector<vector<char>> s(h + 1, vector<char>(w + 1));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> s[i][j];
    }
  }
  vector<vector<mint>> dp(h, vector<mint>(w));
  vector<vector<mint>> dpx(h, vector<mint>(w));  // down
  vector<vector<mint>> dpy(h, vector<mint>(w));  // right
  vector<vector<mint>> dpz(h, vector<mint>(w));  // right down
  dp[0][0] = 1;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i == 0 && j == 0) {
        continue;
      }
      if (s[i][j] == '#') {
        continue;
      }
      if (i > 0) {
        dpx[i][j] = dp[i - 1][j] + dpx[i - 1][j];
      }
      if (j > 0) {
        dpy[i][j] = dp[i][j - 1] + dpy[i][j - 1];
      }
      if (i > 0 && j > 0) {
        dpz[i][j] = dp[i - 1][j - 1] + dpz[i - 1][j - 1];
      }
      dp[i][j] = dpx[i][j] + dpy[i][j] + dpz[i][j];
    }
  }
  cout << dp[h - 1][w - 1].val() << endl;
}

参考

公式動画もあわせて見ると理解しやすい。

Discussion