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

hamayanhamayan's blog

Day of the Mountain [yukicoder No.611]

https://yukicoder.me/problems/no/611

解法

https://yukicoder.me/submissions/224681

公式解説この記事が圧倒的に分かりやすいので、以下の文章を読む前に、これらの記事を読むことをおすすめする。

幅を活用した動的計画法をする。
「4HW≦1211」といういかにもな制約がある。
このような制約が幅を活用した動的計画法ではないかなというヒントになる。
 
まずはTを一般的な動的計画法で特定していこう。
dp[y][x] := (y,x)までのパスでの最小の歩きにくさの総和
これは遷移先をminで更新していく一般的な動的計画法で行ける。
 
数え上げが難しい。
ここで幅を活用した動的計画法というのをする。
これは縦横どちらかの数が小さくなるので、ある一辺についてbitで状態を管理でき、状態をまとめ上げられる手法。
下のコードではW≦Hとなるように最初に変形をしてある。
dp2[id][msk] := 座標id(=W*y+x)までのパスで、直前のW個のマスについて最小値で来ているかのマスク
dp更新の際にupokとleokを用意する。
upok := 上のマスが最小値で来ているか
leok := 左のマスが最小値で来ているか
これをmskとdpを見ながら判定していく。
あとは、idのマスが'?'なら最小値か最小値じゃないで分岐していく。

#define INF INT_MAX/2
int H, W;
string A[1010];
int B[1010][1010];
int dp[1010][1010];
mint dp2[400][1 << 18];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> A[y];
    if (W <= H) {
        rep(y, 0, H) rep(x, 0, W) if (A[y][x] != '?') B[y][x] = A[y][x] - '0';
    } else {
        rep(y, 0, H) rep(x, 0, W) if (A[y][x] != '?') B[x][y] = A[y][x] - '0';
        swap(W, H);
    }

    rep(y, 0, H) rep(x, 0, W) dp[y][x] = INF;

    if (A[0][0] == '?') dp[0][0] = 1;
    else dp[0][0] = B[0][0];

    rep(y, 0, H) rep(x, 0, W) {
        if (B[y + 1][x] == 0) dp[y + 1][x] = min(dp[y + 1][x], dp[y][x] + 1);
        else dp[y + 1][x] = min(dp[y + 1][x], dp[y][x] + B[y + 1][x]);

        if (B[y][x + 1] == 0) dp[y][x + 1] = min(dp[y][x + 1], dp[y][x] + 1);
        else dp[y][x + 1] = min(dp[y][x + 1], dp[y][x] + B[y][x + 1]);
    }

    int T = dp[H - 1][W - 1];
    printf("%d\n", T);

    dp2[0][0] = 1;

    rep(y, 0, H) rep(x, 0, W) rep(msk, 0, 1 << W) {
        int id = y * W + x;

        int upok = 0;
        if (y) {
            if(msk & (1 << x)) upok = 1;
            if (B[y][x] == 0) {
                if (dp[y - 1][x] + 1 != dp[y][x]) upok = 0;
            } else {
                if (dp[y - 1][x] + B[y][x] != dp[y][x]) upok = 0;
            }
        }
        else {
            if(x == 0) upok = 1;
        }

        int leok = 0;
        if (x) {
            if (msk & (1 << (x - 1))) leok = 1;
            if (B[y][x] == 0) {
                if (dp[y][x - 1] + 1 != dp[y][x]) leok = 0;
            }
            else {
                if (dp[y][x - 1] + B[y][x] != dp[y][x]) leok = 0;
            }
        }
        

        if (upok or leok) {
            int nmsk = msk | (1 << x);
            dp2[id + 1][nmsk] += dp2[id][msk];
        }

        if (!upok and !leok) {
            int nmsk = msk & (~(1 << x));

            if (B[y][x] == 0) dp2[id + 1][nmsk] += dp2[id][msk] * 9;
            else dp2[id + 1][nmsk] += dp2[id][msk];
        }
        else {
            if (B[y][x] == 0) {
                int nmsk = msk & (~(1 << x));
                dp2[id + 1][nmsk] += dp2[id][msk] * 8;
            }
        }
    }

    mint ans = 0;
    rep(msk, 0, 1 << W) if (msk & (1 << (W - 1))) ans += dp2[H * W][msk];
    printf("%d\n", ans.get());
}