2020-12-22

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;
}