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

AtCoder, 動的計画法

問題方針

文字列 \( S \) の部分文字列に、それぞれの隣接する部分文字列が異なるように分割したときの最大値を求めます。このとき、部分文字列は最長でも \( 2 \) であることが分かります。例えば、\(S = aaaa \) のと ...

AtCoder, 動的計画法

問題方針動的計画法

\( d(i, j) \) を \( i \) 桁目までの調べた時、余りが \( j \) となるものの個数とします。初期値として、\( d(0, 0) = 1 \) とします。

\( S_i = ?\) のと ...

AtCoder, 二分探索, 動的計画法, 探索

問題方針広義単調減少部分列

\( A_1 \geq A_2 \geq \cdots \geq A_i \) となるような広義単調減少列に対して、\( i \) 個の色が必要であることが分かります。これは、連続しない部分列に対しても言える ...

AOJ, 二分探索, 動的計画法, 探索

問題方針

LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。

動的計画法 と 二分探索コード

&n

AtCoder, 動的計画法, 桁DP

問題方針桁DP

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

AOJ, bitDP, 動的計画法, 累積和

問題方針

素直に浮かぶ方針は、並び方を全通り試すという方法ですが、このときの場合の数は、\( M!\) となるので、計算量が多すぎます。ここで、次のことに着目します。ぬいぐるみを \( k \) 種類整列済みであるとき、\( k + 1 ...

bitDP, yukicoder, 動的計画法

問題方針

\( k \) 個商品を購入したとき、\( k + 1 \) 個目の商品を購入するときの割引は、\( k \) 個商品を購入したときの順番に依存しません。この考えをもとにして、bitDP を行います。

bitDP

\ ...

yukicoder, 動的計画法, 数学

問題方針

\( Y \) を昇順にソートさせてから考えます。

コストの計算

\( N = 2 \) のときは、どちらの高さに揃えてもコストは変わりません。\( N = 3 \) のときは、\( Y_2 \) に揃えることが最適 ...

AtCoder, 動的計画法

問題方針動的計画法

今の状態が次の状態に影響するような問題は、動的計画法を使って解くことができます。

\( d_i \) を \( i \) 段目までの移動方法とします。初期値として、\( d_0 = 1 \) とします。ま ...

AtCoder, 動的計画法

問題方針どのような文字列を除くか

どのような部分文字列を取り除くかを考えます。

長さが \( 3 \) の文字列では、”AGC”, “ACG”, “GAC̶ ...