Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@hibit(hibit at)

桁DP絶対一行で遷移するマン

Last updated at Posted at 2025-01-07

　桁 DP のややこしい点は、遷移の上限を場合分けしなければいけない点だと思います。具体的には、以下のような分岐を辿ります。（その桁の上限の数を $A_i$ とします）

  • 余裕がある　→　$0\sim9$ まで遷移可能
  • 余裕がない　→　$0\sim A_i$ まで遷移可能
    • 次の遷移は $A_i$ 未満か？　→　余裕ができる
    • 次の遷移は $A_i$ か？　→　余裕がないまま

　なので、コードの可読性を重視すると以下のような感じになると思います。

　説明のためのシンプルな例として、「$N$ 以下の数を桁DPで求める」というコードを書きます。

   vector<vector<ll>> dp(71,vector<ll>(2));
   dp[0][0] = 1;
   rep(i, 70)
   {
       rep(next, 10)
       {
           dp[i + 1][1] += dp[i][1];
       }
       rep(next, a[i] + 1)
       {
           if (next < a[i])
           {
               dp[i + 1][1] += dp[i][0];
           }
           else
           {
               dp[i + 1][0] += dp[i][0];
           }
       }
   }

　しかし、できれば、

    rep(...) // 何らかのループ
    {
        rep(...) // 何らかのループ
        {
            // 何らかの一行の処理
        }
    }

　という形で書けた方が助かる。なぜなら、何か変更があった時に、手を加えるところがひとつで済むからです。それに、ループの範囲自体が変わるよりも、ループは同じだけど、適用される操作によって違いが出ると考えた方が、見通しがいい。

基本形

　結論として、以下のように書けます。

   rep(i,70){
       rep(small,2){
           rep(next,10){
               dp[i+1][small||(next<a[i])] += dp[i][small]*(small||(next<=a[i]));
           }
       }
   }
  • i どの桁まで見たか
  • small 余裕があるか

　式の左に出てくる不等号が <、式の右に出てくる不等号が <= であることに注意です。

　これが基本形になります。

　後はこの式に付加情報を足すだけで、基本的な桁 DP を一行で解くことができます。

ABC-C 007

    rep(i, 70)
    {
        rep(contains, 2)
        {
            rep(small, 2)
            {
                rep(next, 10)
                {
                    dp[i + 1][contains || next == 4 || next == 9][small || (next < a[i])] += dp[i][contains][small] * (small || (next <= a[i]));
                }
            }
        }
    }
  • i どの桁まで見たか
  • contains $4$ か $9$ のいずれかを少なくともひとつ含むか
  • small 余裕があるか

ナベアツ数

　みんな大好きナベアツ数も一行で遷移することができます。

    rep(i, 70)
    {
        rep(mod, 3)
        {
            rep(contains, 2)
            {
                rep(small, 2)
                {
                    rep(next, 10)
                    {
                        dp[i + 1][(mod + next) % 3][(next == 3) || contains][small || (next < a[i])] += dp[i][mod][contains][small] * (small || (next <= a[i]));
                    }
                }
            }
        }
    }
  • i どの桁まで見たか
  • mod $3$ で割ったあまり
  • contains $3$ を少なくともひとつ含むか
  • small 余裕があるか

Leading Zero

　桁 DP では、leading zero を単位元として 扱ってはいけない 場合は対策をする必要があります。つまり、「$321$」を「$...000321$」として扱うとバグが出てしまうような場合です。

　具体的にはこういう問題など。

　さて、この場合の基本的な遷移はどうなるか。

  • 余裕がある　→　$0\sim9$ まで遷移可能
  • 余裕がない　→　$0\sim A_i$ まで遷移可能
    • 次の遷移は $A_i$ 未満か？　→　余裕ができる
      • 次の遷移は $0$ か？　→　leading zero 継続
      • 次の遷移は $0$ 超過か？　→　leading zero 離脱
    • 次の遷移は $A_i$ か？　→　余裕がないまま
      • 次の遷移は $0$ か？　→　leading zero 継続
      • 次の遷移は $0$ 超過か？　→　leading zero 離脱

　こうなります。皆様はすんなり理解できますか？　私はできません。

　結論から言うと、「leading zero から遷移する数を始めから計上しておく」ことが対策になります。通常の桁 dp だと、dp[0]...[0] = 1 という「種」から増殖していくのが、先に dp の各表にそういう 1 が増えるので、個人的な感覚ですが「複数の種を先に撒いておく」というイメージがあります。

　つまり、dp テーブルに対して、先に以下のような種を撒いておきます。

    rep(i,m){
        if(i==0){
            for(int j=1;j<=a[0];j++){ // 1 始まりである点に注意
                dp[1][j<a[0]]++;    
            }
        }else{
            for(int j=1;j<=9;j++){
                dp[i+1][1]++;
            }
        }
    }

　これは、以下のような一行遷移でまとめることができます。

    rep(i,m){
        for(int j=1;j<10;j++){
            dp[i+1][i||(j<a[0])] += i||(j<=a[0]);
        }
    }

実装例

チートシート

　せっかくなのでチートシートを公開します。リーディングゼロ対応です。決め打ちにぶたんで小さい方から $K$ 番目の数を答える形にしています。初期状態だとただ自分の数を数えるだけですが、各自改造してください。

公開用：マクロなし
long long solve() {
    long long k;
    std::cin >> k;
    long long ng = 0;
    long long ok = 1e18; // 10^18

    // バイナリサーチで条件を満たす最小の値を探索
    while (abs(ng - ok) > 1) {
        long long mid = (ng + ok) / 2;

        // midを桁ごとに分解してvectorに格納
        std::vector<long long> a(20);
        long long copy = mid;
        for (int i = 0; i < 20; i++) {
            a[i] = copy % 10;
            copy /= 10;
        }
        // 末尾の0を削除
        while (!a.empty() && a.back() == 0) {
            a.pop_back();
        }
        // 桁を逆順に（自然な数値の並びにする）
        std::reverse(a.begin(), a.end());
        int m = a.size();

        // DPテーブルを定義
        using VI = std::vector<long long>;
        using VVI = std::vector<VI>;
        using VVVI = std::vector<VVI>;
        VVVI dp(m + 1, VVI(10, VI(2, 0))); // dp[桁][現在の数][smallerフラグ]

        // 初期条件：1桁目
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < 10; j++) {
                dp[i + 1][j][i || (j < a[0])] += i || (j <= a[0]);
            }
            // 遷移
            for (int now = 0; now < 10; now++) {
                for (int small = 0; small < 2; small++) {
                    for (int next = 0; next < 10; next++) {
                        dp[i + 1][next][small || (next < a[i])] += 
                            dp[i][now][small] * (small || next <= a[i]);
                    }
                }
            }
        }

        // 合計を計算
        long long tmp = 0;
        for (int j = 0; j < 10; j++) {
            for (int small = 0; small < 2; small++) {
                tmp += dp[m][j][small];
            }
        }

        // バイナリサーチの更新
        if (tmp >= k) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}
自分用（マクロ有）
ll solve(){
    ll k;
    cin >> k;
    ll ng = 0;
    ll ok = 1e18;
    while(abs(ng-ok)>1){
        ll mid = ng+ok;
        mid /= 2;
        vector<ll> a(20);
        ll copy = mid;
        rep(i,20){
            a[i] = copy%10;
            copy /= 10;
        }
        while(a.back()==0){
            a.pop_back();
        }
        reverse(all(a));
        int m = a.size();
        using VI = vector<ll>;
        using VVI = vector<VI>;
        using VVVI = vector<VVI>;
        using VVVVI = vector<VVVI>;
        using VVVVVI = vector<VVVVI>;
        VVVI dp(m+1,VVI(10,VI(2)));
        rep(i,m){
            for(int j=1;j<10;j++){
                dp[i+1][j][i||(j<a[0])] += i||(j<=a[0]);
            }
            rep(now,10){
                rep(small,2){
                    rep(next,10){
                        dp[i+1][next][small||(next<a[i])] += dp[i][now][small]*(small||next<=a[i]);
                    }
                }
            }
        }
        ll tmp = 0;
        rep(j,10){
            rep(small,2){
                tmp += dp[m][j][small];
            }
        }
        if(tmp>=k){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    return ok;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?