桁DPの基本形 auto digit = [](long long n, int x) { while (x - 1) n /= 10, x--; return n % 10; }; dp[0][0][0] = 1; rep(i, 20) rep(j, 2) rep(k, 2) rep(d, 10) { if (j == 0 && d > digit(N, 20 - i)) continue; int _i = i + 1; int _j = j == 0 && …

問題を作った 1以上N未満の整数のうち、数字が昇順になっているものはいくつあるか。たとえば159, 1124457889, 5などがこれに該当する。制約は1 <= N <= 10^18。 解説 遷移は以下の図。 状態数は10。遷移は、現在の状態の数字よりも選択した数字のほうが小さ…

オートマトンと桁DP 桁DPは以下の図でだいたい説明できる。 0埋めDP（今命名）は以下の図。 この2つのDPの状態は独立しているので積が取れる（以下の表のNは上限）。 桁DP 0埋めDP 意味 0 0 N = 0のときの0 0 1 N > 0のときのN 1 0 N > 0のときの0 1 1 0 < D …