はまやんはまやんはまやん

hamayanhamayan's blog

Grid 2 [Educational DP Contest / DP まとめコンテスト Y]

https://atcoder.jp/contests/dp/tasks/dp_y

前提知識

解説

https://atcoder.jp/contests/dp/submissions/3956127

同様の包除原理問題を見たことがあったから、包除原理で解くと分かったので、考察過程は無いです。
わかりやすさのために段階的に解説する。
あと、mod10^9+7上でのC(a,b)は計算できるものとして進める。
C(a,b)は二項定理。
 
dp[i][ng] := i番目の壁のマスにいて、(1,1)から壁のマスをng回以上訪れている組み合わせ
0番目の壁のマスを(1,1)として、N+1番目の壁としてマス(H,W)を用意して、壁を1つ追加しておく。
つまり、N++をした状態で以降は解説する。
すると、
dp[i][ng]からの遷移はdp[i+1][ng+1], dp[i+2][ng+1], ..., dp[N][ng+1]となる。
dp[i][ng]からdp[j][ng+1]への遷移は
dx = X[j]-X[i], dy = Y[j]-Y[i]とすると、C(dx+dy, dx)通りの移動方法がある。
この移動方法の中で壁がある可能性があるため、状態はng回以上訪れているとなっている。
注意点があるが、壁を処理する順番はa<bで壁aから壁bに到達可能ならばX[a]≦X[b]かつY[a]≦Y[b]となるように事前にソートしておく必要がある。
これで状態O(N^2)、遷移O(N)でO(N^3)となる。
 
ここから答えを出すときは、包除原理を適用する。
ans = dp[N][1] - dp[N][2] + dp[N][3] - dp[N][4] + ...
ngが奇数のときが正になっているのは、ゴールを壁としたため実際に訪れた壁+1がngとなっているためである。
 
これを高速化するが、答えの求め方を見ると、奇数で正、偶数で負となっているだけで、何個通ったかは実際はあまり問題ではない。
よって、ngの偶奇だけ保持することにする。
dp[i][m] := i番目の壁のマスにいて、(1,1)から壁のマスをng回訪れている組み合わせ(ただしm=ng mod 2)
これで答えはdp[N][1]-dp[N][0]となる。
状態O(N),遷移O(N)なので、O(N^2)で間に合う。

int H, W, N, Y[3010], X[3010];
mint dp[3010][2];
Comb<mint, 201010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> N;
    rep(i, 1, N + 1) cin >> Y[i] >> X[i];
    N++;
    Y[0] = 1, X[0] = 1;
    Y[N] = H, X[N] = W;
 
    vector<int> ord;
    rep(i, 0, N + 1) ord.push_back(i);
    sort(all(ord), [&](int a, int b) {
        if (X[a] != X[b]) return X[a] < X[b];
        return Y[a] < Y[b];
    });
 
    dp[0][0] = 1;
    rep(i, 0, N) rep(m, 0, 2) {
        int a = ord[i];
        rep(j, i + 1, N + 1) if (X[a] <= X[ord[j]] and Y[a] <= Y[ord[j]]) {
            int dx = X[ord[j]] - X[a];
            int dy = Y[ord[j]] - Y[a];
            dp[j][1 - m] += dp[i][m] * com.aCb(dx + dy, dx);
        }
    }
    
    mint ans = dp[N][1] - dp[N][0];
    cout << ans << endl;
}