[AtCoder] ABC 154 D – Dice in Line
サイコロの出る目が \( a \) まであるとき、このサイコロの出る目の期待値は、
\
となります。したがって、累積和などを用いて最大となる値を全探索します。
コード#include <bi ...
[AtCoder] ABC 149 E – Handshake
一般ゲストの並びを変えても影響がないので、降順に並び替えます。つまり、\( A_{i}\geq A_{i + 1} \ (0 \leq i \leq N – 2)\) を満たすとします。
最終的な幸福度が最大 ...
[yukicoder] No. 0944 煎っぞ!
コーヒー豆のおいしさ度の候補は、累積和の数だけあるので、\( N \) 通りあることがわかります。ここで、累積和を
\
とします。おいしさ度を \( s_i \) と固定したとき、条件を満たすような分割 ...
[AOJ] No. 0411 矢印
空白のマスを〇で表すとします。”→←〇〇” という状態で ”〇→←〇” と矢印を動かしても点数に変化はありません。また、”→→←〇〇” という状態では、”〇→→←〇” と動かすと点数が \( 1 \) 増えます。
...
[AtCoder] ABC 147 D – Xor Sum 4
整数 \( A, B\) を \( 2 \) 進数表記で下位から \( i\) ビット目を \( a_i, \ b_i \) と表します。例えば、\( A = a_1a_2a_3 \) , \( B = b_ ...
[AtCoder] GigaCode 2019 D – 家の建設
二次元の累積和を利用して解きます。二次元の累積和を利用することで長方形の領域で表される土地の地価の和を \( O(1) \) で計算することができます。よって、全てのマスを全探索して求めます。計算量は、\( O(H^2W^2) ...
[AOJ] No. 0621 ロシアの旗 (Russian Flag)
‘W’, ‘B’, ‘R’ についてそれぞれ列ごとに累積和を取っていきます。ある列を塗り替えるコストは、\( M \) からその色の個数を引いた値な ...
[AOJ] No. 0633 ぬいぐるみの整理 (Plush Toys)
素直に浮かぶ方針は、並び方を全通り試すという方法ですが、このときの場合の数は、\( M!\) となるので、計算量が多すぎます。ここで、次のことに着目します。ぬいぐるみを \( k \) 種類整列済みであるとき、\( k + 1 ...
[yukicoder] No. 837 Noelちゃんと星々2
配列 \(a \) に対して、次の関数を最小化することを考えます。
\
答えから言うと、\( x \) が \( a \) の中央値のとき最小となります。証明は下のサイトから参照で ...
[AtCoder] CODE THANKS FESTIVAL 2018 C – Pair Distance
交流コストを \( c \) と置くと、
\
となります。このシグマの計算回数は、\( \dfrac{N(N – 1)}{2}\) となり、\( N \) 人から \( 2 \) ...