ferinの競プロ帳

競プロについてのメモ

桁DPの実装

競技プログラミング

桁に着目して状態をまとめてDPするテク
取り扱える条件の代表的な例としては N 以下の数，桁和，倍数 などである
桁DP自体の解説は以下のサイトなどがわかりやすい
Digit DP 入門 by とーらすさん
桁 DP の思想 〜 K 以下の整数を走査するとはどういうことか 〜 by drkenさん

解くのにかかる時間，思考パートを減らすために自分が実装をどうやるかまとめておく．

実装

上の桁から順に見ていく方法と下の桁から順に見ていく方法が存在している．N以下について取り扱う場合は上から，繰り上がりなどを扱う場合は下から見る方法がよさそう．
自分は上から見る実装が好きなので主にそっちについて書きます．

10進法で条件(3の倍数)を満たすs以下の数の個数を数えるコードが以下のものである．この形が基本で問題の条件に合わせて書き換えていく．

string s; cin >> s;  
ll n = s.size();  
  
// dp[i桁目][以下が確定したか][mod 3]  
dp[0][0][0] = 1;  
REP(i, n) REP(j, 3) REP(k, 2) {  
    ll lim = k==0 ? s[i]-'0' : 9;  
    REP(d, lim+1) {  
        ll nj = (j+d) % 3, nk = k || d<lim;  
        dp[i+1][nj][nk] += dp[i][j][k];  
    }  
}  
cout << dp[n][0][0] + dp[n][1][0] << endl;

問題に応じて考えるやつ

  • 条件をDPのkeyにどうやってもたせるか？
    以下が確定したか，桁和，今までに現れた数 など問題に合わせてDPテーブルのkeyを考える
  • 条件を満たす数の個数以外を求める場合
    \text{dp} \lbrack i+1 \rbrack \lbrack nj \rbrack \lbrack nk \rbrack ← \text{dp} \lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack へどのように遷移するのか変える

考える要素がほとんど無でできるやつ

  • B(\neq 10)進法以外を扱う
    limの設定をB-1に合わせる
  • \lbrack L, R \rbrack で条件を満たす数の個数を数える
    \lbrack 0, X \rbrack を数える関数 \text{solve} をつくって \text{solve}(r) - \text{solve}(l-1) とする (l=0には注意)
  • \lbrack 1, N \rbrack で条件を満たす数の個数を数える
    桁DPは基本的に \lbrack 0, N \rbrack を数えるので-1する
  • s以上について取り扱う
    d \lt \text{lim} を d \gt \text{lim} に変えればよい

問題例

以上の実装にしたがって問題を解いていく．競技プログラミングにおける桁DP問題まとめ by hamayanhamayanさん を主に解いています．

禁止された数字

「今までに4か9が現れたか？」という条件をもてばよい．

auto solve = [&](string s) {  
    const ll n = s.size();  
    memset(dp, 0, sizeof(dp));  
    dp[0][0][0] = 1;  
    REP(i, n) REP(j, 2) REP(k, 2) {  
        ll lim = j==0 ? s[i]-'0' : 9;  
        REP(d, lim+1) {  
            ll nj = j || d<lim, nk = k || d==4 || d==9;  
            dp[i+1][nj][nk] += dp[i][j][k];  
        }  
    }  
    return dp[n][0][1] + dp[n][1][1];  
};  
cout << solve(to_string(b)) - solve(to_string(a-1)) << endl;

TDPC 数

Xの倍数 \iff \text{mod}\ X で 0 と言い換えると見通しがよくなるパターンが多い．「桁和 mod D」という条件をもてばよい．

dp[0][0][0] = 1;  
REP(i, n) REP(j, x) REP(k, 2) {  
    ll lim = k==0 ? s[i]-'0' : 9;  
    REP(d, lim+1) {  
        ll nj = (j+d) % x, nk = k || d<lim;  
        dp[i+1][nj][nk] += dp[i][j][k];  
    }  
}  
cout << dp[n][0][0] + dp[n][0][1] - 1 << endl;

ごちうさ数

「前4桁がなにか」「51?3がすでに現れたか」という条件を持てばよい．

dp[0][0][0][0] = 1;  
REP(i, n) REP(j, 10000) REP(k, 2) REP(l, 2) {  
    ll lim = k==0 ? s[i]-'0' : 9;  
    REP(d, lim+1) {  
        ll nj = (j*10 + d) % 10000, nk = k || d<lim, nl = l;  
        if(nj/100 == 51 && nj%10 == 3) nl |= 1;  
        dp[i+1][nj][nk][nl] += dp[i][j][k][l];  
    }  
}  
ll ret = 0;  
REP(i, 10000) REP(j, 2) ret += dp[n][i][j][1];  
cout << ret << endl;

1

今見ている i 桁目が d=1 となる数の個数について考える．これは (i桁目までの個数) \times (i+1桁目以降の個数) となる．i桁目までの個数 は \text{dp} \lbrack i \rbrack \lbrack j \rbrack で数えている．i+1桁目以降の個数は

  • d=lim (以下が確定しない)
    sのi+1桁目以降のsuffix
  • d \lt lim (以下が確定する)
    10^{n-1-i}

となる．

p10[0] = 1;  
FOR(i, 1, 11) p10[i] = p10[i-1] * 10;  
for(ll i=n-1; i>=0; --i) suf[i] = suf[i+1] + p10[n-1-i] * (s[i]-'0');  
  
ll ret = 0;  
dp[0][0] = 1;  
REP(i, n) REP(j, 2) {  
    ll lim = j==0 ? s[i]-'0' : 9;  
    REP(d, lim+1) {  
        ll nj = j || d<lim;  
        dp[i+1][nj] += dp[i][j];  
        if(d==1) {  
            ll num = d==lim ? suf[i+1]+1 : p10[n-1-i];  
            ret += dp[i][j] * num;  
        }  
    }  
}  
cout << ret << endl;

壊れた電卓

A以下/A以上で達成できる最小の差をそれぞれ求める．
「現れた数字の集合」をbit演算を用いて，leading-zeroの0を現れた数字に含めてはいけないので「leading-zeroか」を DPのkeyに持つ．
i 桁目に d が現れるとき，それによって A との差がどれだけ変わるか？に沿ってDPの遷移をする．

p10[0] = 1;  
FOR(i, 1, 20) p10[i] = p10[i-1] * 10;  
  
ll ret = INF;  
// s以下  
{  
    REP(i, 20) REP(j, 1LL<<11) REP(k, 2) REP(l, 2) dp[i][j][k][l] = INF;  
    dp[0][0][0][0] = stol(s);  
    REP(i, n) REP(j, 1LL<<11) REP(k, 2) REP(l, 2) {  
        ll lim = k==0 ? s[i]-'0' : 9;  
        REP(d, lim+1) {  
            ll nj = j, nk = k || d<lim, nl = l || d!=0;  
            if(nl==1) nj |= 1LL<<d;  
            chmin(dp[i+1][nj][nk][nl], dp[i][j][k][l] - p10[n-1-i] * d);  
        }  
    }  
    REP(i, 1LL<<11) REP(j, 2) REP(k, 2) {  
        if(__builtin_popcount(i) > x) continue;   
        chmin(ret, dp[n][i][j][k]);  
    }  
}  
// s以上  
{  
    REP(i, 20) REP(j, 1LL<<11) REP(k, 2) REP(l, 2) dp[i][j][k][l] = INF;  
    dp[0][0][0][0] = -stol(s);  
    REP(i, n) REP(j, 1LL<<11) REP(k, 2) REP(l, 2) {  
        ll lim = k==0 ? s[i]-'0' : 0;  
        FOR(d, lim, 10) {  
            ll nj = j, nk = k || d>lim, nl = l || d!=0;  
            if(nl==1) nj |= 1LL<<d;  
            chmin(dp[i+1][nj][nk][nl], dp[i][j][k][l] + p10[n-1-i] * d);  
        }  
    }  
    REP(i, 1LL<<11) REP(j, 2) REP(k, 2) {  
        if(__builtin_popcount(i) > x) continue;  
        chmin(ret, dp[n][i][j][k]);  
    }  
}  
cout << ret << endl;

ジグザグ数

「mod m」「前の桁の数」「leading-zero，leading-zeroの次の桁，増加，減少」をDPのkeyにもてばよい．leading-zeroの部分については前の桁と比べて増加も減少もしない．したがって増加/減少だけでなくleading-zeroか？をkeyにもつ必要がある．

auto solve = [&](string s) {  
    const ll n = s.size();  
    REP(i, 505) REP(j, 500) REP(k, 10) REP(l, 4) dp[i][j][k][l][0] = dp[i][j][k][l][1] = 0;  
    dp[0][0][0][0][0] = 1;  
    REP(i, n) REP(j, m) REP(k, 10) REP(l, 4) REP(lt, 2) {  
        if(dp[i][j][k][l][lt]==0) continue;  
        ll lim = lt==0 ? s[i]-'0' : 9;  
        REP(d, lim+1) {  
            ll nj = (j*10+d) % m, nk = d, nl, nlt = lt || d<lim;  
            if(l==0) {  
                if(d!=0) nl = 1;  
                else nl = 0;  
            } else {  
                if(k<d && l==2) continue;  
                if(k>d && l==3) continue;  
                if(k==d) continue;  
                nl = k < d ? 2 : 3;  
            }  
            dp[i+1][nj][nk][nl][nlt] += dp[i][j][k][l][lt];  
        }  
    }  
    mint ret = 0;  
    REP(i, 10) REP(j, 4) REP(k, 2) ret += dp[n][0][i][j][k];  
    return ret;  
};  
  
for(ll i=a.size(); i>=0; --i) {  
    if(a[i]>'0') {  
        a[i]--;  
        if(a.size()>2 && i==0 && a[i]=='0') a.erase(a.begin());  
        break;  
    }  
    a[i] = '9';  
}  
cout << solve(b) - solve(a) << endl;

ABC117 D - XXOR

上から貪欲に決めていく方法でもできますが，桁DPでやってみます．
2進数であっても10進数と同様に桁DPを考えられる．\text{dp} \lbrack i桁目 \rbrack \lbrack 以下が確定したか？ \rbrack = i桁目までで可能な最大のf(X) というDPを行えばよい．

REP(i, 41) REP(j, 2) dp[i][j] = -INF;  
dp[0][0] = 0;  
REP(i, 40) REP(j, 2) {  
    ll lim = j==0 ? !!(m&1LL<<(39-i)) : 1;  
    REP(d, lim+1) {  
        ll add = 0;  
        REP(k, n) {  
            ll ta = !!(a[k]&1LL<<(39-i));   
            if(d^ta) add += 1LL<<(39-i);  
        }  
  
        ll nj = j || d<lim;  
        chmax(dp[i+1][nj], dp[i][j] + add);  
    }  
}  
cout << max(dp[40][0], dp[40][1]) << endl;

Sum Equals Xor

数のペアなどについて数え上げるときも同様に桁DPを適用することができる．\text{dp} \lbrack 上からi桁目 \rbrack \lbrack a+b\leq Lが確定したか \rbrack というDPをする．
a+b = a \text{ XOR } b の制約から (aのi桁目，bのi桁目) \neq (1,1) である．i 桁目を (0,0),(0,1),(1,0) にすることに対応させたDPの遷移を行う．

  • dp[i+1][j] += dp[i][j]*2
    (0,1) (1,0) に対応
    すでに a+b \leq L が確定 or s[i]='1' ならば可能
  • dp[i+1][j || s[i]=='1'] += dp[i][j]
    (0,0) に対応
dp[0][0] = 1;  
REP(i, n) REP(j, 2) {  
    // (aのi桁目, bのi桁目) が (0,1) (1,0)  
    if(j == 1 || s[i]=='1') dp[i+1][j] += dp[i][j] * 2;  
    // (0,0)  
    dp[i+1][j || s[i]=='1'] += dp[i][j];  
}  
cout << dp[n][0] + dp[n][1] << endl;

yukicoder No.685 Logical Operations

and, xor, orの値がどのようになっているかを以下に示す．

x y x and y x xor y x or y
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 0 1

上の桁から見ていって (0,1),(1,0) のいずれかが現れた後に (1,1) が現れれば条件を満たすことがわかる．よって「これらのペアが現れたか？」をkeyとすればよい．
x \leq y \leq N を満たすためには「x\leq y が確定したか？」「y \leq N が確定したか？」をkeyとすればよい．
\text{dp} \lbrack i桁目 \rbrack \lbrack 各ペアが現れたか? \rbrack \lbrack x\leq y が確定したか？ \rbrack \lbrack y \leq Nが確定したか？ \rbrack というDP をすればよい．

mint dp[65][3][2][2];  
int main(void) {  
    ll m;  
    cin >> m;  
    string s = "";  
    while(m > 0) {  
        s += m%2 + '0';  
        m /= 2;  
    }  
    reverse(ALL(s));  
    const ll n = s.size();  
  
    // [i桁目][ペアが現れたか][x<=yが確定したか][y<=mが確定したか]  
    dp[0][0][0][0] = 1;  
    REP(i, n) REP(j, 3) REP(k, 2) REP(l, 2) {  
        ll lim = l || s[i]=='1';  
        // (0,0)  
        ll nj = j, nk = k, nl = lim;  
        dp[i+1][nj][nk][nl] += dp[i][j][k][l];  
        // (0,1)  
        if(lim==1) {   
            nj = j==0 ? 1 : j, nk = 1, nl = l;  
            dp[i+1][nj][nk][nl] += dp[i][j][k][l];  
        }  
        // (1,0)  
        if(k==1) {  
            nj = j==0 ? 1 : j, nk = k, nl = lim;  
            dp[i+1][nj][nk][nl] += dp[i][j][k][l];  
        }  
        // (1,1)  
        if(j>=1 && lim==1) {  
            nj = j==1 ? 2 : j, nk = k, nl = l;  
            dp[i+1][nj][nk][nl] += dp[i][j][k][l];  
        }  
    }  
  
    mint ret = 0;  
    REP(i, 2) REP(j, 2) ret += dp[n][2][i][j];  
    cout << ret << endl;  
  
    return 0;  
}

ABC138 F - Coincidence

y \text{ mod } x と x \text{ xor } y が一致する \iff x と y の最上位bitが一致 かつ (xのi桁目,yのi桁目)=(1,0) が存在しない と言い換えられる．
\text{dp} \lbrack i桁目 \rbrack \lbrack L\leq xが確定 \rbrack \lbrack y\leq Rが確定 \rbrack \lbrack (1,1)がすでに現れたか \rbrack としてDPをすればよい．

dp[0][0][0][0] = 1;  
REP(i, 60) REP(j, 2) REP(k, 2) REP(l, 2) {  
    ll tl = !!(L&1LL<<(59-i)), tr = !!(R&1LL<<(59-i));  
    // (1,1) y<=R のみできる  
    if(k==1||tr==1) {  
        ll nj = j || tl<1, nk = k || 1<tr;  
        dp[i+1][nj][nk][1] += dp[i][j][k][l];  
    }  
    // (0,0) L<=x のみできる  
    if(j==1||tl==0) {  
        ll nj = j || tl<0, nk = k || 0<tr;  
        dp[i+1][nj][nk][l] += dp[i][j][k][l];  
    }  
    // (0,1) L<=x && y<=R && l=1 のみできる  
    if((j==1||tl==0) && (k==1||tr==1) && l==1) {  
        ll nj = j || tl<0, nk = k || 1<tr;  
        dp[i+1][nj][nk][l] += dp[i][j][k][l];  
    }  
}  
  
mint ret = 0;  
REP(i, 2) REP(j, 2) REP(k, 2) ret += dp[60][i][j][k];  
cout << ret << endl;

ARC066 D - Xor Sum

i 桁目について (u,v) が (0,0),(1,1),(0,1),(1,0) のパターンを取ることができるのか？を考える．

  • (u,v)=(0,0)
    (a,b)=(0,0) とすればよい
  • (u,v)=(1,1)
    (a,b)=(0,1) とすればよい
  • (u,v)=(0,1)
    (a,b)=(0,0) で下の桁で繰り上がりがある
  • (u,v)=(1,0)
    (a,b)=(0,1) で下の桁で繰り上がりがある && 上の桁に繰り上がる

0 \leq u,v \leq n の条件と下の桁で繰り上がりがあるか？を管理できればよい．\text{dp} \lbrack i桁目 \rbrack \lbrack u\leq Nが確定 \rbrack \lbrack v\leq Nが確定 \rbrack \lbrack 下の桁で繰り上がりが起きるのが確定 \rbrack = 可能なパターン数 というDPをすればよい．

dp[0][0][0][0] = 1;  
REP(i, 60) REP(j, 2) REP(k, 2) REP(l, 2) {  
    ll d = !!(n&1LL<<(59-i));  
    // (0,0)  
    dp[i+1][j||0<d][k||0<d][0] += dp[i][j][k][l];  
    // (1,1)  
    if((j==1||d==1) && (k==1||d==1) && l==0) {  
        dp[i+1][j||1<d][k||1<d][0] += dp[i][j][k][l];  
    }  
    // (1,0)  
    if((j==1||d==1) && l==1) {  
        dp[i+1][j||1<d][k||0<d][1] += dp[i][j][k][l];  
    }  
    // (0,1)  
    if(k==1||d==1) {  
        dp[i+1][j||0<d][k||1<d][1] += dp[i][j][k][l];  
    }  
}  
  
mint ret = 0;  
REP(i, 2) REP(j, 2) ret += dp[60][i][j][0];  
cout << ret << endl;

レシート

繰り下がりがあるか？をDPのkeyに持つ．下の桁から見ていくと繰り下がりがあったかどうかを持ちながらDPするのが楽．

東京工業大学プログラミングコンテスト2015 F - レシート - ferinの競プロ帳

Manthan, Codefest 17 Salazar Slytherin's Locket

「奇数回現れた数」をDPのkeyに持ち， \text{dp} \lbrack i桁 \rbrack \lbrack 奇数回現れた数の集合 \rbrack \lbrack leading-zeroか \rbrack \lbrack 以下が確定 \rbrack というDPテーブルを埋めていくことで各クエリに対して答えを求めることができる．しかし，このDPテーブルの要素数は 60 \times 2^{11} \times 2 \approx 200000 であり，q 回この桁DPを行うのはTLEしてしまう．
そこで各クエリにおいて重複して計算している部分を減らしたい．「以下が確定した」場合，クエリの l,r 等によってDPの遷移が変化することはなくなり，クエリが異なる場合でも求めるべき値が一致する．\text{dp} \lbrack b進法 \rbrack \lbrack 残りi桁 \rbrack \lbrack 奇数回現れた集合はS \rbrack \lbrack leading-zeroか \rbrack としたDPテーブルを持ちメモ化再帰することで，各クエリで計算する必要がある量を減らすことができる．

提出
最初に書いたのとだいぶ違う実装になったけど