[AtCoder] ABC 153 F – Silver Fox vs Monster
モンスターの順序は問題に影響を与えないので、モンスターの座標について昇順に並び替えて考えます。
最適な攻撃方法最適な攻撃方法は、モンスターの先頭から爆弾を使っていくやり方です。爆弾の位置は、爆弾の範囲の最も左を今注 ...
[AOJ] No. 0261 マヤの大予言
時刻の変換と同じように、いったん最小単位に変換してから計算を行います。西暦からマヤ歴への変換は、2012年12月21日からどれだけの日数が経過したかどうかを計算します。このときうるう日に気を付けます。マヤ歴から西暦への変換は、 ...
[AtCoder] ABC 149 E – Handshake
一般ゲストの並びを変えても影響がないので、降順に並び替えます。つまり、\( A_{i}\geq A_{i + 1} \ (0 \leq i \leq N – 2)\) を満たすとします。
最終的な幸福度が最大 ...
[yukicoder] No. 0944 煎っぞ!
コーヒー豆のおいしさ度の候補は、累積和の数だけあるので、\( N \) 通りあることがわかります。ここで、累積和を
\
とします。おいしさ度を \( s_i \) と固定したとき、条件を満たすような分割 ...
[AtCoder] ABC 146 C – Buy an Integer
\( f(N) = AN + Bd(N)\) とすると、\( f(N) \) は増加関数なので、二分探索を行います。整数の桁数は、対数を使うよりも、数値を文字列に変換してから長さを得る方が良いと思います。
コード#inc ...
[AtCoder] ABC 144 E – Gluttony
証明ができなかったので、予想を立てて考えます。おそらく、修行前の最適なコストは、次のようになります。配列 \( A, F\) を
\
\
と整列させます。このときのコストを ...
[AtCoder] ABC 143 D – Triangles
全てのパターンについて調べると計算量が \( O(N^3) \) となるので間に合いません。なので、\( 2 \) 本を固定して考えます。
二分探索\( a \leq b \leq c \) として、\( b, c ...
[AtCoder] ABC 138 E – Strings of Impurity
\( t \) に含まれる文字が \( s \) に存在しなければ、条件を満たす整数は存在しません。そうではないとき、\( t \) の \( i \) 文字目 \( t_i \) について、\( s̵ ...
[AtCoder] ABC 134 E – Sequence Decomposing
\( A_1 \geq A_2 \geq \cdots \geq A_i \) となるような広義単調減少列に対して、\( i \) 個の色が必要であることが分かります。これは、連続しない部分列に対しても言える ...
[AOJ] DPL 1 D 最長増加部分列
LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。
動的計画法と二分探索参考を参照してください。 ...