ABC235F Variety of Digits - geam1113’s diary

自力AC(一度TLEになったので、解法を見て、合っているか確認した)

条件を満たす桁に関する問題
$N$ 以下の整数全てに関する問題

という条件から、桁DPが有力候補となります。
桁DPに関する情報はネット上に多くあるため、ここでは割愛しますが、大雑把に説明します。

桁DPでは上位桁より考慮していきます。
$N$ の上から $i$ 桁目を $d_i$ とし、 $K$ を $N$ 以下にしたいとします。

$K$ の上から $i-1$ 桁目までが、 $N$ と同じだったとします。すると、 $K$ の $i$ 桁目を $d_i$ より大きくすると、 $K$ は $N$ を超えます。よって、 $K$ の $i$ 桁目は $d_i$ 以下にする必要があります。

次に、 $i-1$ 桁目までで、既に $N$ の桁より小さい桁が存在する(すなわち、 $K$ は $N$ 未満となっていることが確定している)とします。
この場合、 $K$ の $i$ 桁目は0〜9までなんでも良いです。

以上から、 $K$ の $i$ 桁目を決定するときに、 $i-1$ 桁目までが $N$ と同じなのか、もしくは既に $N$ 未満なのか、という情報が必要になることがわかります。
桁DPでは、これを未満フラグとして管理し、

未満フラグが0なら、ここまでの桁が $N$ と同一
未満フラグが1なら、既に $N$ 未満であることが確定している

とします。
桁DPについては以上です。

最悪となる全状態数と遷移にかかる時間を見積ります。
$N$ の各桁に対応して、以下の2つを管理する必要があります。

0〜9のどの整数が出現したか
未満フラグ

1については、冪集合 $k$ で管理するので、 $2^{10}$ 通りあります。
$3072 \rightarrow S=\{0,0,1,0,0,0,1,1,0,1\}$

従って、状態数の最悪は
$10^4\times 2^{10}\times 2\simeq 2\times 10^7$
となります。

最悪計算量については、 $i-1$ 桁目の全状態に対して、 $i$ 桁目に0〜9を付加することを考えると、状態数の10倍の時間がかかるので、 $2\times 10^8$ くらいとなって、なんとか大丈夫です。

実際のDPを考えます。
$dp[i][j][k]:=$ 上から $i$ 番目の桁までを考えたきに、未満フラグが $j$ であって、整数の出現状態が $k$ であるものの総和
以下の例で遷移を考えてみます。

例えば、N = 99999として、{1,2}が出現していて、上から3桁目を7にするとします(未満フラグを1で確定している状況)。
$12??? \rightarrow 127??$
$21??? \rightarrow 217??$
この場合、7の付け方は上記の2通りが存在します。

DP遷移で考えてみます。
$dp[3][1][\{0,1,0,0,0,0,0,1,1,0\}] \leftarrow (12700 + 21700)$
$= dp[3][1][\{0,1,0,0,0,0,0,1,1,0\}] \leftarrow (12000 + 21000) + 700 + 700$
$= dp[3][1][\{0,1,0,0,0,0,0,1,1,0\}] \leftarrow (12000 + 21000) + 2\times 7\times 10^{2}$
$= dp[3][1][\{0,1,0,0,0,0,0,1,1,0\}] \leftarrow dp[2][1][\{0,0,0,0,0,0,0,1,1,0\}] + 2\times 7\times 10^{2}$

ここで問題となるのが、和を計算する時に、700が2個発生しています。なぜ2個発生したかというと、2桁目までで{1,2}が出現したもの(すなわち、 $dp[2][1][\{0,0,0,0,0,0,0,1,1,0\}\$ という状態であるもの)が2個存在していたからです。
このことから、和を計算するときには、同時に状態の個数が必要となります。よって、以下の2つのDPを考えます。

$dp_0 [i][j][k]:=$ 上から $i$ 番目の桁までを考えたきに、未満フラグが $j$ であって、整数の出現状態が $k$ であるものの個数
$dp_1 [i][j][k]:=$ 上から $i$ 番目の桁までを考えたきに、未満フラグが $j$ であって、整数の出現状態が $k$ であるものの総和

遷移式は、 $N$ の桁数を $n$ 、 $i+1$ 桁目を $d_i$ とし、 $i+1$ 桁目を $l$ にしたとすると、 $dp_0 [i+1][j \vee l \lt d_i ][k\ or\ (1\lt \lt l ) ] \leftarrow dp_0 [i][j][k]$
$dp_1 [i+1][j \vee l \lt d_i ][k\ or\ (1\lt \lt l ) ] \leftarrow dp_1 [i][j][k] + dp_0 [i][j][k]\times 10^{n-i}$
となります。但し、 $or$ はビット毎のOR演算で、 $\lt \lt$ は左ビットシフト演算です。
初期値は、 $dp_0 [0][0][1] \leftarrow 1$ で、あとは全て0です。

左辺の詳細はネット上にもありますが、 $j \vee l \lt d_i$ というのは、遷移後に未満フラグが1となるのは、すでに未満フラグが1の時か、または、考慮する桁の数 $l$ が $N$ の $i$ 桁目未満だった時であるため、このような表現になります(trueを1、falseを0としています)。

なお、このまま実装するとダメな部分があります。

leading 0を省く処理

実装上、0のみ出現している状態({0,0,0,0,0,0,0,0,0,0,1})が常に1つあることにしておいた方が楽です。しかし、そのままだと0が既に出現していると誤判定してしまいます。そこで、0しか出現していない状態から遷移するときには0が出現していないことにする処理を加えて対処しました。
例
$000?? \rightarrow 0002?$ にする。
出現状態は普通にすると
$\{0,0,0,0,0,0,0,0,0,1\} \rightarrow \{0,0,0,0,0,0,0,0,1,0,1\}$
という遷移になってしまうので、0bit目を0にする。 $\{0,0,0,0,0,0,0,0,0,\color{red}1\} \rightarrow \{0,0,0,0,0,0,0,0,1,0,\color{red}0\}$