AOJ, 動的計画法

問題方針

\( i \) 日目に着ることができる服の派手さの最小値を \( v_i \), 最大値を \( w_i \) とします。各日において派手さの最小値または最大値を持つ服を選ぶことが最適なので、次の動的計画法を行います。証明はし ...

AtCoder, 実装, 文字列

問題方針

制約が緩いので愚直に文字列を走査していきます。

古い看板から作ることができる看板の例を考えます。例えば、お店の名前の文字列の長さが \( 3 \) であり、古い看板の文字列の長さが \( 7 \) のとき、文字列の ...

AOJ, 動的計画法

問題方針

前日と今日のスケジュールの状態を考えれば良いので、動的計画法を行います。便宜上、与えられた文字列の先頭に ‘J’ を挿入します。ここで、\( d(i, j) \) を \( i \) 日目の参加者の状態 ...

AOJ, 数学

問題方針

東南方向の斜めの道が無ければ、\( 2 \) 点間の最短距離は、

\

となります。

南西方向

観光スポットが南西方向にある場合、東南方向の道を通る必要がないので、最短距離は、

\

AtCoder, 数え上げ, 文字列

問題方針

条件を満たす整数列を作ります。まず初めに、\( a_i = 0 \ ( 1 \leq i \leq N) \) とします。次に、文字列の先頭から末尾に向かって、\( S_i = \) ‘<‘ なら ...

AtCoder, グラフ理論, 数学

問題方針

一見難しそうに見えますが、\( 300 \) 点の問題なので解法は簡単であることが予想できます。

実現不可能な整数列頂点 \( 1 \) からの距離について

頂点 \( 1 \) からの距離が与えられるので、 ...

AOJ, 動的計画法

問題方針最小値を固定

水ようかんを切り分けた時の長さの値は、切る箇所を任意の \( 2 \) 点選ぶことを考えると、最大でも

\

あることが分かります。したがって、最小値を固定したときの、最大値を変数とみて、最大 ...

AOJ, 動的計画法

問題方針

都市 \( i \ (1 \leq i \leq N)\) に到達して滞在する可能性のある日 \( j \) の範囲は、\( i \leq j \leq M – N + i\) となります。ここで、次の配列を考えま ...

AtCoder, 動的計画法

問題方針

商品の重さの最大値が \( 10^9\) なので、添え字で重さを管理して考えるのはメモリ的にきついので、別の方法を考えます。価値を添え字で管理することを考えます。\( d(i, j)\) を商品 \( i \) まで調べたとき ...

AtCoder, 動的計画法

問題方針

いわゆるナップザック問題ですね。

\( d(i, j) \) を品物 \( i \) まで調べたとき、重さの総和が \( j \) であるときの価値の総和の最大値とします。初期値は、\( d(0, 0) = 0 \ ...