D - 禁止された数字 AtCoder Beginner Contest 007
問題概略
A~Bの中で4か9が含まれる物の個数を答えよ。
制約
A,B <=10^18
解法
4か9が一つでも含まれてればいいなら包除原理使うか!と思ったけど、大変そうなので桁DPで解いた。
まとめ上げるのに必要な条件は
何桁目を見ているか
数が上限ギリギリかどうか
すでに4,9を使っているか
の3つとしてメモ化再帰で解いた。
public static void solve() throws Exception { //longを忘れるなオーバーフローするぞ A = nl(); B = nl(); System.out.println(task(B) - task(A - 1)); } public static long rec(int k, int ti, int bad) { if (k == N) { if (bad == 1) return 1; else return 0; } else if (dp[k][ti][bad] != -1) { return dp[k][ti][bad]; } long sum = 0; int maxn = ti == 1 ? v[k] : 9; for (int i = 0; i <= maxn; i++) { int t = i == maxn ? ti : 0; int b = i == 4 || i == 9 ? 1 : bad; sum += rec(k + 1, t, b); } return dp[k][ti][bad] = sum; } public static long task(long n) { N = keta(n); v = toIntArray(n); dp = new long[N + 1][2][2]; fill(dp, -1); return rec(0, 1, 0); }