No.319

桁 DP を使う.

まず $n$ 以下の数値の中に含まれる 12 の数を求める.

これはキーとして, 何桁目まで見たか, 最大値か, 最後は 1 か, 見つけた 12 の数を使い, 値として見つかった数値の数を使って DP を行う.

次に2つの数値に渡って 12 が出現する数を求める. 2 で始まって 2 で終わる数とその直前の数をつなげたときに 12 が出現するので, この数値の数を求める.

これはキーとして, 何桁目まで見たか, 最大値か, 最初から 0 が続いているか, 0 以外の最初の数値は 2 か, 最後は 2 かを使い, 値として見つかった数値の数を使って DP を行う.

$n$ 以下の 12 の数を $F(n)$ とすると, 求める答えは $F(B) - F(A-1)$ である.

ただし, コーナーケースとして $A$ が 1 や 2 の場合や, 2 で始まって 2 で終わる数の場合などがありかなり面倒くさい. おかげで WA を積み上げてしまった.