yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

H - Grid 1 / Educational DP Contest

EDPC AtCoder C++ Educational DP Contest DP 数え上げ 再帰 競技プログラミング

問題

縦 h 行、横 w 列のグリッドがあり、上から i 行目、左から j 列目のマスを (i, \, j) で表す。

各 i, \, j について、マス (i, \, j) の情報が文字 {a}_{i, \, j} によって与えられ、 {a}_{i, \, j} が . ならばマス (i, \, j) は空マスであり、# ならば壁のマスである。 また、マス (1, \, 1), \, (h, \, w) は空マスであることが保証される。

ここで、マス (1, \, 1) から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス (h, \, w) まで辿り着こうとするとき、経路は全部で何通りあるか。 経路の総数を {10}^{9} + 7 で割った余りを出力せよ。

入力

まず最初の1行目に整数 h, \, w が与えられる。

次の h 行のうち i 行目には、文字列 {a}_{i, \, 1} \, {a}_{i, \, 2} \, \cdots \, {a}_{i, \, w} が与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 2 \leq h, \, w \leq 1000
  • {a}_{i, \, j} = . または #
    • {a}_{1, \, 1}, \, {a}_{h, \, w} は . である。

出力

経路の総数を {10}^{9} + 7 で割った余りを1行で出力すること。

解法

右または下に隣り合うマスへの移動のみが認められているので、マス (i, \, j) に辿り着くには、下図のように直前にマス (i - 1, \, j) またはマス (i, \, j - 1) に辿り着かなくてはなりません。

従って、 \mathrm{dp}_{i, \, j} を、マス (1, \, 1) からマス (i, \, j) に辿り着く経路の総数として定義すると、 \begin{align} \mathrm{dp}_{i, \, j} = \mathrm{dp}_{i - 1, \, j} + \mathrm{dp}_{i, \, j - 1} \end{align} が成立します。

ただし、「 1 \leq i \leq h かつ 1 \leq j \leq w 」が成立しないときは、そのような場所にはマスはないので \mathrm{dp}_{i, \, j} = 0 とします。 また、マス (i, \, j) が空マスでないときも、そのマスには辿り着くことができないので、 \mathrm{dp}_{i, \, j} = 0 とします。

さらに、マス (1, \, 1) については、スタート地点がこのマスになることから、経路としては1通りが存在すると言えるので、 \mathrm{dp}_{1, \, 1} = 1 として考えます。

このように \mathrm{dp} を定義して、 i = 1, 2, \cdots , h の順番に、 j = 1, 2, \cdots , w のそれぞれについて \mathrm{dp}_{i, \, j} の値を計算していくことにより、すべてのマスに対しての経路の総数が求まります。

求めるものは、マス (h, \, w) への経路の総数なので、 \mathrm{dp}_{h, \, w} の値を出力すれば、この問題が解けることとなります。

ただし、経路の総数を {10}^{9} + 7 で割った余りを出力しなければならないので、コード上では各 \mathrm{dp}_{i, \, j} が求まるたびに、 \mathrm{mod} \; ({10}^{9} + 7) での値に変換する必要があります。

また、この方法では、全てのマスについて順に調べているため、 O(hw) の計算量が必要となりますが、 h, \, w \leq 1000 であるので、実行時間制限にも十分間に合うと考えられます。

ソースコード

main() 関数の中に、答えを出力する部分を直接実装しました。

const ll MOD = 1e9 + 7;

int h, w;
char a[1005][1005];

ll dp[1005][1005];

int main() {
   // 値の入力
  cin >> h >> w;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> a[i][j];
    }
  }

  // i = 1, ..., h のそれぞれについて、 j = 1, ..., w での dp[i][j] の値を更新していく
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      if (i == 1 && j == 1) {
        dp[1][1] = 1; // dp[1][1] = 1 であることを宣言する
        continue;
      }

      if (a[i][j] == '.') { // マス (i, j) が空マスの場合のみ、dp の値は更新される
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD; // 10^9 + 7 で割ったときの余りの値にして更新する
      }
    }
  }

  cout << dp[h][w] << endl; // 答えの出力

  return 0;
}

再帰を用いたソースコード

実装時に煩雑になるので特に行う必要もないと思いますが、再帰の考え方を用いた実装も考えました。 具体的には、 solve(i, j) という関数によって、「マス (i, \, j) の経路の総数を {10}^{9} + 7 で割ったときの余り」が返されるという状態になるように、 solve() 関数を以下のように実装しました。

int h, w;
char a[1005][1005];
ll dp[1005][1005];
bool visited[1005][1005]; // すでに (i, j) において solve() が計算されたかを管理する

ll solve(int i, int j) {
  if (!(1 <= i && i <= h && 1 <= j && j <= w)) {
    return 0; // (i, j) が与えられた盤面から逸脱していたら、 0 を返して終了する
  }

  if (visited[i][j]) {
    return dp[i][j]; // すでに solve(i, j) が計算されていたら、そのまま dp[i][j] の値を返して終了する
  }

  visited[i][j] = true; // solve(i, j) が計算されたことにする
  if (a[i][j] != '.') {
    return dp[i][j] = 0; // (i, j) が空マスでないならば、dp[i][j] = 0 として、 0 を返して終了する
  }

  ll ans = solve(i - 1, j) + solve(i, j - 1); // (i - 1, j), (i, j - 1) の2通りの場合について経路の計算を行わせる
  return dp[i][j] = ans % MOD; // 得られた総数を 10^9 + 7 で割ったときの余りを dp[i][j] として記録し、その値を返す
}

この solve() 関数が実装された状態で、 main() 関数に答えを出力する部分を直接実装すると、以下のようになります。

int h, w;
char a[1005][1005];
ll dp[1005][1005];
bool visited[1005][1005];

int main() {
  // 値の入力
  cin >> h >> w;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> a[i][j];
    }
  }

  // dp[1][1] = 1 と定義し、(1, 1) については既に探索済みとして記録する
  dp[1][1] = 1;
  visited[1][1] = true;

  // 答えの出力
  cout << solve(h, w) << endl;

  return 0;
}

この方法でも特に計算量も変わりませんが、ソースコードとして書かれるforループの数が減らせるのは利点なのかなと思います。

ただ、再帰を用いての実装は煩雑になりやすいので、この問題がコンテストに出た場合はこの方針では実装しないと思います。

感想

EDPCについては、前回の G問題 の記事が3年前になってしまっていたので、ここから気が向いたら逐一更新していこうと考えています。