桁dp

[tipstar0125]

参考：https://drken1215.hatenablog.com/entry/2019/02/04/013700 問題まとめ：https://blog.hamayanhamayan.com/entry/2017/04/23/212728

[tipstar0125]

• dp[桁数][条件][smaller]
• まとめて計算するより、以下の3条件に分けて考えた方が最初のうちは見通しが良い
  • smaller -> smaller: 0-9まで使用可
  • not smaller -> smaller: 0からその桁の数よりも小さい数まで使用可
  • not smaller -> not smaller: その桁の数のみ使用

[tipstar0125]

条件に当てはまる数を数える系の例

• 初期設定: dp[0][0][0]=1、それ以外0

https://atcoder.jp/contests/abc007/tasks/abc007_4 N以下の4 or 9を用いた数字の数を求める

long long dpA[60][2][2];
string SA = to_string(A);
int LA = SA.length();

dpA[0][0][0] = 1;
for (int i = 1; i <= LA; i++)
{
    int n = SA[i - 1] - '0';
    // smaller -> smaller
    for (int j = 0; j < 10; j++)
    {
        dpA[i][1][1] += dpA[i - 1][1][1];
        if (j == 4 || j == 9)
        {
            dpA[i][1][1] += dpA[i - 1][0][1];
        }
        else
        {
            dpA[i][0][1] += dpA[i - 1][0][1];
        }
    }
    // not smaller -> smaller
    for (int j = 0; j < n; j++)
    {
        dpA[i][1][1] += dpA[i - 1][1][0];
        if (j == 4 || j == 9)
        {
            dpA[i][1][1] += dpA[i - 1][0][0];
        }
        else
        {
            dpA[i][0][1] += dpA[i - 1][0][0];
        }
    }
    // not smaller -> not smaller
    dpA[i][1][0] += dpA[i - 1][1][0];
    if (n == 4 || n == 9)
    {
        dpA[i][1][0] += dpA[i - 1][0][0];
    }
    else
    {
        dpA[i][0][0] += dpA[i - 1][0][0];
    }
}

[tipstar0125]

条件に当てはまる最大を求める系の例

• 初期設定: dp[0][0]=0, それ以外-1
• dp[i-1][smaller]が-1のときは、そのからの遷移はない

https://atcoder.jp/contests/abc301/tasks/abc301_d N以下で、?(0 or 1)を含む2進数文字列を満たす最大の値

input! {
    S: Chars,
    N: usize
}

let mut S: VecDeque<_> = S.into_iter().collect();
let L = 60;
while S.len() < L {
    S.push_front('0');
}

let mut dp = vec![vec![-1; 2]; L + 1];
dp[0][0] = 0;
for i in 1..=L {
    let s = S[i - 1];
    let n = (N >> (L - i)) & 1;
    let add = 1_isize << (L - i);

    if dp[i - 1][1] != -1 {
        // smaller -> smaller
        if s == '?' || s == '1' {
            dp[i][1] = max!(dp[i][1], dp[i - 1][1] + add);
        } else {
            dp[i][1] = max!(dp[i][1], dp[i - 1][1]);
        }
    }
    if dp[i - 1][0] != -1 {
        // not smaller -> smaller
        if n == 1 && (s == '?' || s == '0') {
            dp[i][1] = max!(dp[i][1], dp[i - 1][0]);
        }
        // not smaller -> not smaller
        if n == 1 && (s == '?' || s == '1') {
            dp[i][0] = max!(dp[i][0], dp[i - 1][0] + add);
        } else if n == 0 && (s == '?' || s == '0') {
            dp[i][0] = max!(dp[i][0], dp[i - 1][0]);
        }
    }
}
let ans = max!(dp[L][0], dp[L][1]);
println!("{}", ans);

[tipstar0125]

2数で桁dp 問題：https://mojacoder.app/users/shinnshinn/problems/xor-comb 解答：https://mojacoder.app/users/shinnshinn/problems/xor-comb/submissions/ba84358a-f89f-4889-88c1-ec2da821f363

T=int(input())
for _ in range(T):
    A,B,C=map(int,input().split())
    dp=[[0 for _ in range(2)] for _ in range(2)]
    dp[0][0]=1
    for i in range(60,-1,-1):
        ndp=[[0 for _ in range(2)] for _ in range(2)]
        for j in range(2):
            for k in range(2):
                a=(A>>i)&1
                b=(B>>i)&1
                c=(C>>i)&1
                if j^k!=c:continue
                # A: smaller->smaller, B: smaller->smaller
                ndp[1][1]+=dp[1][1]
                # A: not smaller->smaller, B: smaller->smaller
                if j<a:ndp[1][1]+=dp[0][1]
                # A: smaller->smaller, B: not smaller->smaller
                if k<b:ndp[1][1]+=dp[1][0]
                # A: not smaller->not smaller, B: smaller->smaller
                if j==a:ndp[0][1]+=dp[0][1]
                # A: smaller->smaller, B: not smaller->not smaller
                if k==b:ndp[1][0]+=dp[1][0]
                # A: not smaller->not smaller, B: not smaller->not smaller
                if j==a and k==b:ndp[0][0]+=dp[0][0]
                # A: not smaller->smaller, B: not smaller->not smaller
                if j<a and k==b:ndp[1][0]+=dp[0][0]
                # A: not smaller->not smaller, B: not smaller->smaller
                if j==a and k<b:ndp[0][1]+=dp[0][0]
                # A: not smaller->smaller, B: not smaller->smaller
                if j<a and k<b:ndp[1][1]+=dp[0][0]
        dp=ndp
    ans=sum(dp[0])+sum(dp[1])
    print(ans)