【ABC183】E - Queen on Grid

atcoder.jp

解法

問題を見てすぐに下のようなDPが思い浮かんだ。
dp[i][j] ← (i, j)へ行く場合の数
ただ、愚直に遷移しようとすると1つのマスにつき、H+W回ぐらいの遷移が必要になるのでこれでは間に合わない。

手を動かして、DPテーブルがどのような値をとるかを確認してみると次のことに気づいた。
縦方向の累積和をrui_h, 横方向の累積和をrui_w, 斜め方向の累積和をrui_dとすると、
dp[i][j] ← rui_h[i-1][j] + rui_w[i][j-1] + rui_d[i-1][j-1]

累積和を使えば、O(1)で遷移することができた。

学んだこと

累積和を使ってDPを高速化する問題は頻出なので、覚えておこうと思う。
斜め方向に累積和をとるという発想は初めてだった。

あと、最初はBFSをする感じでDPの遷移をしようとしていたが、それだとまだ累積和が求まってない場所に遷移する可能性があるため、うまくいかなかった。
(i, j)にアクセスする時には、既に(i-1, j)、(i, j-1)、(i-1, j-1)の累積和は求まっているので、二重ループで遷移できることがわかった。

実装

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    REP (i, H) cin >> S[i];

    // 累積和
    vector<vector<mint>> rui_h(H+1, vector<mint>(W+1, 0)),
    rui_w(H+1, vector<mint>(W+1, 0)),
    rui_d(H+1, vector<mint>(W+1, 0)); // 縦,横,斜め

    vector<vector<mint>> dp(H, vector<mint>(W, 0));
    dp[0][0] = 1;
    
    REP (i, H) {
        REP (j, W) {
            if (S[i][j] == '#') continue;

            if (i-1 >= 0) {
                dp[i][j] += rui_h[i-1][j];
                rui_h[i][j] = rui_h[i-1][j];
            }
            if (j-1 >= 0) {
                dp[i][j] += rui_w[i][j-1];
                rui_w[i][j] = rui_w[i][j-1];
            }
            if (i-1 >= 0 && j-1 >= 0) {
                dp[i][j] += rui_d[i-1][j-1];
                rui_d[i][j] = rui_d[i-1][j-1];
            }

            rui_h[i][j] += dp[i][j];
            rui_w[i][j] += dp[i][j];
            rui_d[i][j] += dp[i][j];
        }
    }

    c(dp[H-1][W-1])


    return 0;
}