桁DP に関するカテゴリーです。

AtCoder,桁DP

問題方針

桁 DP を用いて考えます。\( d(i, j, k) \) を \( i \) 桁目まで調べた時、\( 1 \) の数が \( j \) であり、未満フラグが \( k \) であるものの数とします。\( k = 0 \) ...

AtCoder,桁DP

問題方針

\( N \) を数値として扱うと制約が大きすぎるので、桁DPを行います。上位 \( i \) 桁目までの数字に対して、\( d(i, 0) \) を \( i \) 桁目の数字の分だけお札を使ったときの最小値とし、\( d( ...

AtCoder,動的計画法,桁DP

問題方針

見るからに桁DPの問題なので動的計画法を行います。

\( d(i, j, 0) \) を \( N \) の上位 \( i \) 桁目まで一致する数字で、\( 0 \) でない数字の個数が \( j \) 個である ...

AtCoder,動的計画法,桁DP

問題方針桁DP

\( n \) 以下の数字の中で \( 4 \) または \( 9 \) を含まない数の個数を求めます。\( d_{i, 0} \) を上位 \( i \) 桁目まで調べたとき、\( 4 \) または \( 9 \) を ...