今日の精進 - 桁DP （AtCoder EDPC-S, ABC336-E）

AtCoder ABC336のE問題で桁DPの問題が出題されました。問題を読んで「桁DPだな」ということはわかったのですが、実装はできずACできませんでした。そこで、桁DPの復習しました。

まずは桁DPの基本的な問題（EDPC-S）を挑戦

ABC336-Eは私には難しかったので、より基本的な桁DPの問題を探したら、EDPC(Education DP Contest)のS問題が見つかったのでそれをACしてみます。

S - Digit Sum

ポイント

• （あんまりよくないかもですが…）桁DPっぽいなぁと思ったら下記の型で考え、各状態について、次の桁の数を10通り試す。
  $${\mathrm{dp}[i][j][k] =}$$ 個数
  $${\quad i}$$ : $${i}$$ 桁目まで確定している
  $${\quad j}$$ : 状態
  $${\quad k}$$ : ある数以下か否か

• 上記の問題の場合は、以下の型で各状態について次の桁の数を10通り試す。
  $${\mathrm{dp}[i][j][k] =}$$ 個数
  $${\quad i}$$ : $${i}$$ 桁目まで確定している
  $${\quad j}$$ : 各桁の数字の総和 $${\mathrm{mod} \, \mathrm{D}}$$
  $${\quad k}$$ : $${\mathrm{K}}$$以下か否か

• 答えは dp[n][0][0] + dp[n][0][1] - 1。
  0 が含まれるので1引く。

実装のポイント

ループも上の型に合わした感じに実装できる。

mint dp[10009][109][2];

...[中略]...

rep(ci, n) {
  rep(cj, D) {
    rep(ck, 2) {
　　　　　　　　　// 対象の桁の値
      int c = K[ci] - '0';
      rep(nxt, 10) {
        // 配り先の状態などなどを作る
        int ni = ci + 1;
        int nj = (cj + nxt) % D;
        int nk = ck;
        // K以下か否かを判定
        if (ck == 0) {
          if (c < nxt) { continue; }
          if (nxt < c) { nk = 1; }
        }
        dp[ni][nj][nk] += dp[ci][cj][ck];
      }
    }
  }
}

ACしたコード

提出 #49371918 - Educational DP Contest / DP まとめコンテスト

ABC336-Eを挑戦する

問題はこちら。

E - Digit Sum Divisible

ポイント

• EDPC-Sの場合は $${\mathrm{D}}$$ が入力1つだけでしたが、ABC336-Eは、$${n}$$ が $${1 \sim 126 \, (=9 \times 14)}$$ まであって、それを全部試す感じの問題。

• 上記の問題の場合は、以下の型で各状態について次の桁の数を10通り試す。
  $${\mathrm{dp}[i][j][k][l] =}$$ 個数
  $${\quad i}$$ : $${i}$$ 桁目まで確定している
  $${\quad j}$$ : 各桁の和
  $${\quad k}$$ : 各桁の和 $${\mathrm{mod} \, \mathrm{n}}$$
  $${\quad l}$$ : $${\mathrm{n}}$$以下か否か

イメージとしては、

for(int k = 1; k < 127; k++) {
  EDCP-S のコード
}

という感じ。毎回桁DPするイメージ。

ACしたコード

提出 #49360033 - AtCoder Beginner Contest 336

DPしているところはEDPC-Sとさほど変わらない感じでACできました。少し桁DPがわかったような気がします。

次回もがんばります。