DP雑記②

問題を作った

1以上N未満の整数のうち、数字が昇順になっているものはいくつあるか。たとえば159, 1124457889, 5などがこれに該当する。制約は1 <= N <= 10^18。

解説

遷移は以下の図。

状態数は10。遷移は、現在の状態の数字よりも選択した数字のほうが小さければ遷移せず、それ以外なら選択した数字に対応する状態に遷移する。つまり次のようなコードになる。

rep(l, 10) rep(d, 10) {
  if (l > d) continue;
  int _l = d;
  dp[_l] += dp[l];
}

このコードと桁DPのコードをマージすることでコードは完成する。

dp[0][0][0][0] = 1;
rep(i, 20) rep(j, 2) rep(k, 2) rep(l, 10) rep(d, 10) {
  if (j == 0 && d > digit(N, 20 - i)) continue;
  if (l > d) continue;

  int _i = i + 1;
  int _j = j == 0 && d == digit(N, 20 - i) ? 0 : 1;
  int _k = k == 0 && d == 0 ? 0 : 1;
  int _l = d;

  dp[_i][_j][_k][_l] += dp[i][j][k][l];
}

N = 10^18のときは4686824個ある。