動的計画法に関するカテゴリーです。

AtCoder, 動的計画法

問題方針

ナップサック問題なので動的計画法で解きます。\( d(i, j, k) \) を スクリーンショット \( i \) まで見た時、\( j \) 枚貼り付けて幅が \( k \) であるときの重要度の合計の最大値とします。遷移 ...

AtCoder, 動的計画法, 累積和, 遅延評価セグメント木

問題方針遅延評価セグメント木

動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( \) から整数を選 ...

AtCoder, 全探索, 動的計画法

問題方針

ショートカットは冗長に選んだとしても \( 4^4 \) 通りなので、全てのショートカットの組み合わせに対して必要なボタンの入力回数を求めます。ここで、\( d(i, 0) \) を \( i \) 文字をショートカットを使わ ...

Codeforces, 動的計画法

問題方針

友人の行動は、ボスを倒すまたはボスをスキップすることができます。また、自分と友人は最低でも \( 1 \) 体のボスに対応しなければならなく、\( 1 \) 回のセッションで最大で \( 2 \) 体のボスを倒すことができます ...

AtCoder, 動的計画法

問題方針

マス \( (i, j)\) にあるアイテムの価値を \( g(i, j) \) とします。アイテムがない場合は \( 0 \) とします。次に、マス \( (i, j)\) において \( i \) 行目のアイテムを \( ...

AtCoder, 動的計画法, 累積和

問題方針

大まかな方針は、下の問題と同じです。

\( P = 2 \) または \( P = 5 \) のとき

\( S = s_N s_{N-1} \cdots s_1 \) とします。

このとき、\( s_i ...

AtCoder, 動的計画法, 累積和

問題方針

\( 12114 \) は \( 12114 = 2019 \times 6 \) なので \( 2019 \) の倍数です。次に、\( 1211472\) という文字列を考えると、\( 12114 \) という文字列があるの ...

AtCoder, 桁DP

問題方針

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

AtCoder, 動的計画法, 桁DP

問題方針

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

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

AtCoder, 動的計画法

問題方針

商品を無数に選ぶことができるナップザック問題なので、動的計画法を使って解きます。\( d(i) \) をモンスターに \( i \) ダメージ与えれるために必要な魔力とします。初期値は、\( d(0) = 0 \) であり、\ ...