AtCoder Beginner Contest 007
Updated:
Source codes
Solutions
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].
\]
ポイント
以下の問題も同じ方法で解ける。とは言っても、想定解は候補全列挙だが。