AtCoder Beginner Contest 007

更新日時:

AtCoder Beginner Contest 007

ソースコード

解法のメモ

D - 禁止された数字

方針

禁止された数字のことを禁止数と呼ぶ。この問題は、

$cnt(X) = X$ 以下の禁止数の個数

を $10^{-1}$ sec 以下のオーダーで求められれば、答えは $cnt(B) - cnt(A - 1)$ で求まる。そこで $cnt$ を桁 DP で実装する。

桁 DP の方法

まず $X$ を string $S$ にしておく。 leading zeros をつけて 20 桁にしておく。

ll DP[21][2][2]; を定義し、以下のように意味付ける。

$DP[i][equal?][forbid?] =$ 上から $i$ 桁目まで見て行った時の場合の数。ただし $equal? = 1$ ならばそれまで $X$ と同じ数で遷移してきており、 $0$ ならば $X$ 以下が確定している。 $forbid? = 1$ ならばすでに $4$ or $9$ を使用しており、 $0$ ならば使用していない。

  • 初期状態: $DP[0][1][0] = 1$ 、それ以外は $0$ 。
  • 答え: $DP[20][1][1] + DP[20][0][1]$ 。

遷移は結構複雑だが、丁寧に場合分けすれば、非自明な場所はない。 $i = 1, \dots, 20$ に対し、以下行う。

equal から equal への遷移

$S[i - 1] = 4, 9$ の場合は、 \[ \begin{align} DP[i][1][1] & += DP[i - 1][1][1], \\\ DP[i][1][1] & += DP[i - 1][1][0]. \end{align} \] そうでない場合は、 \[ \begin{align} DP[i][1][1] & += DP[i - 1][1][1], \\\ DP[i][1][0] & += DP[i - 1][1][0]. \end{align} \]

equal から not equal への遷移

$j = 0, \dots, S[i - 1] - 1$ を入れるということだから、 $j = 4, 9$ の場合は \[ \begin{align} DP[i][0][1] & += DP[i - 1][1][1], \\\ DP[i][0][1] & += DP[i - 1][1][0]. \end{align} \] そうでない場合は、 \[ \begin{align} DP[i][0][1] & += DP[i - 1][1][1], \\\ DP[i][0][0] & += DP[i - 1][1][0]. \end{align} \]

not equal から not equal への遷移

not forbid の場合は、 $4, 9$ を入れると forbid になるし、そうでないなら not forbid のままである。つまり、 \[ \begin{align} DP[i][0][1] & += 8 DP[i - 1][0][0], \\\ DP[i][0][0] & += 2 DP[i - 1][0][0]. \end{align} \] 既に forbid の場合はどれを入れても同じである。 \[ DP[i][0][1] += 10 DP[i - 1][0][1]. \]

ポイント

以下の問題も同じ方法で解ける。とは言っても、想定解は候補全列挙だが。

その他

コメントする