桁DP に関するカテゴリーです。
[AtCoder] ABC 029 D – 1
問題方針
桁 DP を用いて考えます。\( d(i, j, k) \) を \( i \) 桁目まで調べた時、\( 1 \) の数が \( j \) であり、未満フラグが \( k \) であるものの数とします。\( k = 0 \) ...
[AtCoder] ABC 155 E – Payment
問題方針
\( N \) を数値として扱うと制約が大きすぎるので、桁DPを行います。上位 \( i \) 桁目までの数字に対して、\( d(i, 0) \) を \( i \) 桁目の数字の分だけお札を使ったときの最小値とし、\( d( ...
[AtCoder] ABC 154 E – Almost Everywhere Zero
問題方針
見るからに桁DPの問題なので動的計画法を行います。
\( d(i, j, 0) \) を \( N \) の上位 \( i \) 桁目まで一致する数字で、\( 0 \) でない数字の個数が \( j \) 個である ...
[AtCoder] ABC 007 D – 禁止された数字
問題方針桁DP
\( n \) 以下の数字の中で \( 4 \) または \( 9 \) を含まない数の個数を求めます。\( d_{i, 0} \) を上位 \( i \) 桁目まで調べたとき、\( 4 \) または \( 9 \) を ...