[AtCoder] M-SOLUTIONS プロコンオープン 2020 D – Road to Millionaire
\( i \) 日目に株を買えるだけ買うか、全て売るかどうかを考えます。\( i \) 日目の現金を \( m_i \) とします。
\( A_i < A_{i+1} \) のときこのとき、\( 1 \ ...
[AtCoder] ABC 173 D – Chat in a Circle
証明をしないとダメだと思いますが、貪欲法で考えます。\( 2 \) 人目以降の到着で心地よさが増えることと、心地よさの増分は一人分だけであることを考慮して、その時々で心地よさを最大化します。まず初めに、配列を降順に並び替え、\ ...
[AtCoder] キーエンス プログラミング コンテスト 2020 B – Robot Arms
ロボット \( i \) は、区間 \( (X_i – L_i, X_i + L_i) \) に存在しています。\( X_i + L_i \) について昇順に並び替え、先頭から順番に配置していきます。
[AOJ] No. 0260 パイプつなぎ職人の給料
ジョイントの使う順番は給料に影響を与えないので、ジョイントを使うときは最大のものから使うべきです。したがって、ジョイントを降順に並べ、全探索を行います。ジョイントを使う度にパイプの本数が減る一方で、ジョイント分の長さが加算され ...
[AtCoder] ABC 149 E – Handshake
一般ゲストの並びを変えても影響がないので、降順に並び替えます。つまり、\( A_{i}\geq A_{i + 1} \ (0 \leq i \leq N – 2)\) を満たすとします。
最終的な幸福度が最大 ...
[AOJ] No. 0387 タクシー
\( i \) 番目のタクシーは、\( i + 1 \) 番目以降のタクシー乗り場に行くことができるので、\( N \) 番目のタクシーから考えていきます。\( N \) 番目のタクシーは、\( s_N \) の最大値を取るこ ...
[AtCoder] ABC 148 D – Brick Break
どのようにブロックを叩いても不可能な数列は、数列の要素に \( 1 \) が無い場合です。それ以外の数列は、少なくとも \( N – 1 \) 個のレンガを壊すことで条件を満たします。最終的に条件を満たす数列は、\ ...
[AtCoder] ABC 141 D – Powerful Discount Tickets
チケットを一度に複数枚使うことと一枚ずつ使うことが同じであることを確認します。\( 2 \) の指数を用いて整数を表現することを考えます。例えば、\( 31 \) は、
\
と表現できま ...
[AtCoder] ABC 135 C – City Savers
\( i \) 番目の勇者が \( i \) 番目のモンスターを可能な限り倒し、\( i + 1 \) 番目のモンスターを可能な限り倒します。これを \( 1 \) 番目の勇者から順番にシミュレーションします。
コード# ...
[Codeforces] Educational Codeforces Round 69 (Div. 2) C. Array Splitting
\( a \) が昇順に整列されていることが重要です。
偏差に着目する\( e_i = a_{i + 1} – a_{i} \) とすると、\( l < r \) として、
\ ...