[AtCoder] Educational DP Contest E – Knapsack 2
商品の重さの最大値が \( 10^9\) なので、添え字で重さを管理して考えるのはメモリ的にきついので、別の方法を考えます。価値を添え字で管理することを考えます。\( d(i, j)\) を商品 \( i \) まで調べたとき ...
[AtCoder] Educational DP Contest D – Knapsack 1
いわゆるナップザック問題ですね。
\( d(i, j) \) を品物 \( i \) まで調べたとき、重さの総和が \( j \) であるときの価値の総和の最大値とします。初期値は、\( d(0, 0) = 0 \ ...
[AtCoder] Educational DP Contest C – Vacation
前日とは同じ行動を取ることができないことに注意して考えます。\( i \) 日目に行動 \( j = \{A, B, C\}\) を取った時の最大値を \( d(i, j) \) とします。このときの遷移式は、
[AtCoder] ABC 144 E – Gluttony
証明ができなかったので、予想を立てて考えます。おそらく、修行前の最適なコストは、次のようになります。配列 \( A, F\) を
\
\
と整列させます。このときのコストを ...
[AtCoder] ABC 144 D – Water Bottle
水筒を傾けた時に入る水の最大値を考えます。傾けた時の角度を \( \theta \) とします。このときの水筒の容量を \( V (\theta)\) とします。そして、\( V (\theta) = x \) を満たす \( ...
[AtCoder] ABC 144 C – Walk on Multiplication Table
C – Walk on Multiplication Table
方針\( N = x \times y \) を満たす正の整数 \( x, y\ (x \leq y) \) がマスの候補となるので、\( ...
[AtCoder] ABC 143 D – Triangles
全てのパターンについて調べると計算量が \( O(N^3) \) となるので間に合いません。なので、\( 2 \) 本を固定して考えます。
二分探索\( a \leq b \leq c \) として、\( b, c ...
[AtCoder] ABC 143 C – Slimes
文字列を先頭から調べていきます。連続する文字を一つとしてカウントするので、\( c = S_0\) として、\( c \) と異なる文字が出現したときカウンタを回し、文字を更新します。
コード#include <b ...
[AtCoder] AGC 039 A – Connection and Disconnection
長さが \( n \) の単一の文字からなる文字列をどの隣り合う \( 2 \) 文字を相異なる文字列にするために必要なコストは、
\
となります。例えば、\( n = ...
[AtCoder] ABC 142 E – Get Everything
鍵 \( i \) は \( b_i\) 種類の宝箱を開けることができるので、鍵は鍵束であると見ることができます。全ての宝箱を開けられないときは、全ての鍵の集合に対して対応できない宝箱があるということなので、先にそれのチェ ...