AtCoder, データ構造, 整列, 貪欲法

問題方針チケットの使い方

チケットを一度に複数枚使うことと一枚ずつ使うことが同じであることを確認します。\( 2 \) の指数を用いて整数を表現することを考えます。例えば、\( 31 \) は、

\

と表現できま ...

AtCoder, 貪欲法

問題方針

\( i \) 番目の勇者が \( i \) 番目のモンスターを可能な限り倒し、\( i + 1 \) 番目のモンスターを可能な限り倒します。これを \( 1 \) 番目の勇者から順番にシミュレーションします。

コード

Codeforces, 貪欲法

問題方針

\( a \) が昇順に整列されていることが重要です。

偏差に着目する

\( e_i = a_{i + 1} – a_{i} \) とすると、\( l < r \) として、

\ ...

AtCoder, 貪欲法

問題方針

締め切り時刻である \( B \) の値が小さいものから仕事を終わらせていくシミュレーションを行います。ある仕事が終わった時の時刻を \( t \) とすると、次に取り掛かる仕事 \( i \) が、\( t + A_i \l ...

yukicoder, 探索, 貪欲法

問題方針

\( 2^{k} \leq 10^{18}\) を満たす正の整数 \( k \) は \( 60 \) 個程度なので、この組み合わせを全探索します。あらかじめ \( 2^k \) の配列を作成し、二重ループで探索すれば十分です ...

AtCoder, 貪欲法

問題方針

実際にカードを書き換えていく方法は計算量が多くなるので、最終的なカードの値を考えていきます。

ある操作でカードを書き換えるのではなく、カードが増えたとして、上から \( N \) 枚選び、その和が答えになります。こ ...

AtCoder, 貪欲法

問題方針最適な水やりの方法

水やりの操作回数を最小化するには、連続した区間 \( \) が大きくなるように水をやる必要があります。つまり、連続して水やりをできる区間は一回の操作で高さを \( 1 \) 上げるというようにします。 ...