動的計画法

問題方針

最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。

まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( ...

問題方針

動的計画法を使って考えます。\( A_i \) の平均が \( K \) 以上ということは、\( A_i – K \) の総和が \( 0 \) 以上ということなので、\( d(i, j) \) を \( i \) ...

問題方針

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

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

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

問題方針

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

問題方針

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

問題方針

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

問題方針

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

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

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

このとき、\( s_i ...

問題方針

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

問題方針

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