けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 予選 2010 E - 通勤経路 (AOJ 0547, 難易度 6)

JOI 難易度 6 の中では難しい方だと思った!

問題概要

 H \times W のグリッドの左下マス  (1, 1) から右上マス  (H, W) へと至る最短経路 (上または右にのみ移動可能) のうち、以下の条件を満たすものの個数を 100000 で割ったあまりを求めよ。

  • 曲がってから、そこから 2 マス進まないと曲がることができない

制約

  •  1 \le H, W \le 100

解法 (1):DP

移動量は上方向に  H-1 マス、右方向に  W-1 マスなので、あらかじめ --H, --W; としておく。これによって、移動量ベースで考えられるようになる。またスタート地点の座標を  (0, 0) とする。

さて、意外と情報の持たせ方が難しい。曲がってもよいかどうかを判定するために、次のように情報を持たせよう。

  • dp[i][j][k][l] ← 座標  (i, j) へと移動する方法のうち、前回の移動方向が指定の方向 ( k = 0 のとき  (i-1, j) から、 k = 1 のとき  (i, j-1) から) であり、現在直進可能かどうか ( l = 0 のとき曲がれない、 l = 1 のとき曲がれる) を指定したときの、場合の数

4 変数あってややこしいが、ここまで情報を持たせれば遷移をちゃんと作ることができる。計算量は  O(HW) となる。

コード

#include <bits/stdc++.h>
using namespace std;

const int MOD = 100000;
void add(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
};

// 第三引数: 0 前回が上から、1 前回が左から
// 第四引数: 曲がることが可能かどうか
int dp[110][110][2][2]; 
int main() {
    int H, W;
    cin >> H >> W;
    --H, --W;

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= H; ++i) dp[i][0][0][1] = 1;
    for (int j = 1; j <= W; ++j) dp[0][j][1][1] = 1;
    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            // 直進
            for (int l = 0; l < 2; ++l) {
                add(dp[i][j][0][1], dp[i-1][j][0][l]);
                add(dp[i][j][1][1], dp[i][j-1][1][l]);
            }

            // 曲がる
            add(dp[i][j][0][0], dp[i-1][j][1][1]);
            add(dp[i][j][1][0], dp[i][j-1][0][1]);
        }
    }
    int res = 0;
    for (int k = 0; k < 2; ++k) 
        for (int l = 0; l < 2; ++l)
            add(res, dp[H][W][k][l]);
    cout << res << endl;
}

解法 (2):二項係数

 H, W \le 10^{5} であっても解ける解法も考えてみよう (ただし mod の値が素数でないので実際に  H, W \le 10^{5} という制約だとちょっと面倒)。

まず、以下の 4 パターンに分けて考えることにする。

  • 最初の移動が上方向で、最後の移動が上方向
  • 最初の移動が上方向で、最後の移動が右方向
  • 最初の移動が右方向で、最後の移動が上方向
  • 最初の移動が右方向で、最後の移動が右方向

ここではまず、最初と最後の移動がともに上方向である場合を考える。このとき、(上方向の連続移動の回数, 右方向の連続移動の回数) は  (a+1, a) と表せる (上方向の連続移動が、右方向の連続移動より 1 回多くなる)。

このとき、 i 回目の上方向の連続移動で移動する分量を  x_{i} i 回目の右方向の連続移動で移動する分量を  y_{i} とすると、

  •  x_{1} + x_{2} + \dots + x_{a+1} = H
  •  y_{1} + y_{2} + \dots + y_{a} = W
  •  x_{1} \ge 1
  •  x_{a+1} \ge 1
  •  x_{2}, \dots, x_{a} \ge 2
  •  y_{1}, \dots, y_{a} \ge 2

を満たす整数  (x_{1}, \dots, x_{a+1}, y_{1}, \dots, y_{a} の個数を求める問題ということになる。これは

  •  x_{1} + x_{2} + \dots + x_{a+1} = H - a + 1
  •  y_{1} + y_{2} + \dots + y_{a} = W - a
  •  x_{1}, x_{2}, \dots, x_{a+1} \ge 1
  •  y_{1}, y_{2}, \dots, y_{a} \ge 1

を満たす整数  (x_{1}, \dots, x_{a}, y_{1}, \dots, y_{b} の個数に等しい。そしてこれは重複組合せを考えることで、

 {}_{H-a}{\rm C}_{a} \times {}_{W-a-1}{\rm C}_{a-1} 通り

と求められる。

最初が上方向、最後が右方向

上方向連続移動を  a 回、右方向連続移動を  a 回として

 {}_{H-a}{\rm C}_{a-1} \times {}_{W-a}{\rm C}_{a-1} 通り

と求められる。

最初が右方向、最後が上方向

上方向連続移動を  a 回、右方向連続移動を  a 回として

 {}_{H-a}{\rm C}_{a-1} \times {}_{W-a}{\rm C}_{a-1} 通り

と求められる。

最初が右方向、最後が右方向

上方向連続移動を  a 回、右方向連続移動を  a+1 回として

 {}_{H-a-1}{\rm C}_{a-1} \times {}_{W-a}{\rm C}_{a} 通り

と求められる。

コード

計算量は、mod が素数の場合、 O(H+W) となる。

ここでは二項係数計算を漸化式に基づいて実装しているため、計算量は結局  O(HW) となっている。

#include <bits/stdc++.h>
using namespace std;

const int MAX = 310;
const int MOD = 100000;
long long Com[MAX][MAX];
void calc_com() {
    memset(Com, 0, sizeof(Com));
    Com[0][0] = 1;
    for (int i = 1; i < MAX; ++i) {
        Com[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            Com[i][j] = Com[i-1][j-1] + Com[i-1][j];
            if (Com[i][j] >= MOD) Com[i][j] -= MOD;
        }
    }
}

long long com(int n, int r) {
    if (n < 0 || r < 0 || r > n) return 0;
    return Com[n][r];
}

int main() {
    int H, W;
    cin >> H >> W;
    --H, --W;

    long long res = 0;
    calc_com();

    // (上, 上)
    for (int a = 1; a <= max(H, W); ++a) {
        res = (res + com(H-a, a) * com(W-a-1, a-1)) % MOD;
    }
    // (上, 右), (右, 上)
    for (int a = 1; a <= max(H, W); ++a) {
        res = (res + com(H-a, a-1) * com(W-a, a-1) * 2) % MOD;
    }
    // (右, 右)
    for (int a = 1; a <= max(H, W); ++a) {
        res = (res + com(H-a-1, a-1) * com(W-a, a)) % MOD;
    }
    cout << res << endl;
}