桁DP (Digit DP)

お得？

  • 桁DPは「知らなきゃ解けないけど、知っていればやるだけ」らしい
  • 習得しておきたい

問題「D - 禁止された数字」

解法

// i : keta
// j : smaller flag
// k : bad flag 
ll dp[25][2][2];
  • とおいて桁DP

code 抜粋

// four or nine
bool fn(ll v){
  if(v==4 || v==9){
    return true;
  }else{
    return false;
  }
}

int main(){
  // ひとけため
  ll v = ctoi(s[0]);
  rep(i, v+1){  // vまで選べる
   
    // fixed
    if(i==v){
      if(fn(i)){
        dp[0][0][1] += 1;
      }else{
        dp[0][0][0] += 1;
      }
    }
    // smaller
    else{
      if(fn(i)){
        dp[0][1][1] += 1;
      }else{
        dp[0][1][0] += 1;
      }
    }
  }

  FOR(i, 1, L){
    ll v = ctoi(s[i]);

    // fixed to fixed (0->0)
    if(fn(v)){
      // どちらもbadに流す
      dp[i][0][1] += dp[i-1][0][0];
      dp[i][0][1] += dp[i-1][0][1];
    }else{
      // 良い数字は良い数字のまま
      // 悪い数字は悪い数字のまま流す
      dp[i][0][0] += dp[i-1][0][0];
      dp[i][0][1] += dp[i-1][0][1];  
    }

    // fixed to smaller (0->1)
    // v未満の値であるjを選んだとする
    rep(j, v){
      if(fn(j)){
        // どちらもbadに流す
        dp[i][1][1] += dp[i-1][0][0]; 
        dp[i][1][1] += dp[i-1][0][1];
      }else{
        dp[i][1][0] += dp[i-1][0][0];
        dp[i][1][1] += dp[i-1][0][1];
      }
    }

    // smaller to smaller (1->1)
    rep(j, 10){
      if(fn(j)){
        // どちらもbadに流す
        dp[i][1][1] += dp[i-1][1][0];
        dp[i][1][1] += dp[i-1][1][1];
      }else{
        dp[i][1][0] += dp[i-1][1][0];
        dp[i][1][1] += dp[i-1][1][1];
      }
    }    
  }
}
  • ポイントは、添字を間違えないこと
    • fixed to fixed (0->0)
    • fixed to smaller (0->1)
    • smaller to smaller (1->1)
  • の3分岐あるが、添字もそれに対応するので確認はしやすい

別解

// i桁まで見て
// j : smaller flag
// 禁止されていない数を作れる個数
ll dp[20][2];

桁DPの他の問題

桁DPの知見

  • 10000桁などの数値Kが与えれることが多いが、Kが小さいものならlong longに収まってナイーブ解法が書きやすい問題が多い
  • サンプルが合ったけど提出してWAだった時は、ナイーブ解法.cppを作って正しいテストケースを作ればデバッグしやすい

問題集 (cf)

LOOSE, TIGHT

えびちゃん@rsk0315_h4x. 

桁 DP は 0 とか 1 とかでアクセスしてると
意味不明になるので、
名前（loose/tight とか）をつけてやるのがおすすめ
const int TIGHT=0;
const int LOOSE=1;