ei1333の日記

ぺこい

桁DP　上から？下から？

どちらから見ればいいという主張はないので好きなから見てください。

アルゴリズムの説明はしません（え？）が、読めば何をしているかがわかると思います（わかってくれ〜

問題

{N} 以下の整数のうち特定の条件を満たす非負整数の個数を数えてください。

上から見る

アルゴリズム

  • dp[i][smaller]
    • {0, 1, \cdots, i-1} 桁目が確定 → これを {T} とする
    • smaller = 1 のとき {T \lt N[0, i)}、0 のとき {T = N[0, i)}

配るDPを考えます。 {i} を {0} から {|N|-1} に回します。

  • 遷移元: dp[i][0]
    • 遷移: {i} 桁目の数字を {j} とする
      • {j \lt N[i]} → dp[i + 1][1]
      • {j = N[i]} → dp[i + 1][0]
      • {j \gt N[i]} → 不可
  • 遷移元: dp[i][1]
    • 遷移: {i} 桁目の数字を {j} とする
      • {j} → dp[i + 1][1]

初期値 dp[0][0] = 1 として、dp[|N|][0] + dp[|N|][1] が答えです。

実装

dp[0][0] = 1;
for(int i = 0; i < (int) N.size(); i++) {
  for(int smaller = 0; smaller < 2; smaller++) {
    for(int j = 0; j <= (smaller ? 9 : N[i]); j++) {
      dp[i + 1][smaller | (j < N[i])] += dp1[i][smaller];
    }
  }
}
return dp[N.size()][0] + dp[N.size()][1];

下から見る

アルゴリズム

  • dp[i][smaller]
    • {i, i+1, \cdots, |N| - 1} 桁目が確定 → これを {T} とする
    • smaller = 1 のとき {T \le N[i, |N|)}、0 のとき {T \gt N[i, |N|)}

配るDPを考えます。 {i} を {|N| - 1} から {0} に回します。

  • 遷移元: dp[i+1][0]
    • 遷移: {i} 桁目の数字を {j} とする
      • {j \ge N[i]} → dp[i][0]
      • {j \lt N[i]} → dp[i][1]
  • 遷移元: dp[i+1][1]
    • 遷移: {i} 桁目の数字を {j} とする
      • {j \gt N[i]} → dp[i][0]
      • {j \le N[i]} → dp[i][1]

初期値 dp[|N|][1] = 1 として、dp[0][1] が答えです。

実装

dp[N.size()][1] = 1;
for(int i = (int) N.size() - 1; i >= 0; i--) {
  for(int smaller = 0; smaller < 2; smaller++) {
    for(int j = 0; j <= 9; j++) {
      dp[i][j == N[i] ? smaller : (j < N[i])] += dp1[i + 1][smaller];
    }
  }
}
return dp[0][1];

問題例

TDPC E - 数

atcoder.jp

問題概要

{N} 以下かつ {D} の倍数の正整数の個数を求めてください。

解法0（追記）

{N} 以下かつ各桁の和の和が {D} の倍数です。（問題概要が間違っています）

解法1

上からみる

#include<bits/stdc++.h>

using namespace std;

const int mod = (int)(1e9 + 7);

int main() {
  int D;
  string N;
  cin >> D >> N;
  for(auto& c : N) c -= '0';
  vector dp1(2, vector< int >(D));
  dp1[0][0] = 1;
  for (int i = 0; i < (int) N.size(); i++) {
    vector dp2(2, vector< int >(D));
    for (int smaller = 0; smaller < 2; smaller++) {
      for (int j = 0; j <= (smaller ? 9 : N[i]); j++) {
        for(int k = 0; k < D; k++) {
          (dp2[smaller | (j < N[i])][(j + k) % D] += dp1[smaller][k]) %= mod;
        }
      }
    }
    dp1 = dp2;
  }
  (dp1[0][0] += dp1[1][0]) %= mod;
  (dp1[0][0] += mod - 1) %= mod;
  cout << dp1[0][0] << endl;
}

解法2

下からみる

#include<bits/stdc++.h>

using namespace std;

const int mod = (int)(1e9 + 7);

int main() {
  int D;
  string N;
  cin >> D >> N;
  for(auto& c : N) c -= '0';
  vector dp1(2, vector< int >(D));
  dp1[1][0] = 1;
  for(int i = (int) N.size() - 1; i >= 0; i--) {
    vector dp2(2, vector< int >(D));
    for(int smaller = 0; smaller < 2; smaller++) {
      for(int j = 0; j <= 9; j++) {
        for(int k = 0; k < D; k++) {
          (dp2[j == N[i] ? smaller : (j < N[i])][(j + k) % D] += dp1[smaller][k]) %= mod;
        }
      }
    }
    dp1 = dp2;
  }
  (dp1[1][0] += mod - 1) %= mod;
  cout << dp1[1][0] << endl;
}

余談

上/下から見るのDPの定義のまま下/上から見るのに書き換えることもたぶんできると思います（ただし、非直感的？）。