累積和に関するカテゴリーです。

AtCoder, 二分探索, 累積和

問題方針

机 \( A \) の本を \( i \) 冊読んだとき、机 \( B \) の本を最大でいくつ読むことができるかを考えます。机 \( A \) の本を \( i \) 冊読むのにかかる時間は、累積和で求めることができます。残 ...

AtCoder, 累積和

問題方針

まず初めに、\( S_i \neq S_j \wedge S_i \neq S_k \wedge S_j \neq S_j \) を満たす組の数を求めます。これは、\( i, j \) について、\( S_i \neq S_j ...

AtCoder, 数学, 累積和

問題方針

サイコロの出る目が \( a \) まであるとき、このサイコロの出る目の期待値は、

\

となります。したがって、累積和などを用いて最大となる値を全探索します。

コード

 

AtCoder, 二分探索, 探索, 累積和, 貪欲法

問題方針

一般ゲストの並びを変えても影響がないので、降順に並び替えます。つまり、\( A_{i}\geq A_{i + 1} \ (0 \leq i \leq N – 2)\) を満たすとします。

最終的な幸福度が最大 ...

yukicoder, 二分探索, 探索, 累積和

問題方針

コーヒー豆のおいしさ度の候補は、累積和の数だけあるので、\( N \) 通りあることがわかります。ここで、累積和を

\

とします。おいしさ度を \( s_i \) と固定したとき、条件を満たすような分割 ...

AOJ, 整列, 累積和

問題方針

空白のマスを〇で表すとします。”→←〇〇” という状態で ”〇→←〇” と矢印を動かしても点数に変化はありません。また、”→→←〇〇” という状態では、”〇→→←〇” と動かすと点数が \( 1 \) 増えます。

...

AtCoder, 累積和

問題方針各ビットごとに着目

整数 \( A, B\) を \( 2 \) 進数表記で下位から \( i\) ビット目を \( a_i, \ b_i \) と表します。例えば、\( A = a_1a_2a_3 \) , \( B = b_ ...

AtCoder, 累積和

問題方針

二次元の累積和を利用して解きます。二次元の累積和を利用することで長方形の領域で表される土地の地価の和を \( O(1) \) で計算することができます。よって、全てのマスを全探索して求めます。計算量は、\( O(H^2W^2) ...

AOJ, 全探索, 探索, 累積和

問題方針累積和

‘W’, ‘B’, ‘R’ についてそれぞれ列ごとに累積和を取っていきます。ある列を塗り替えるコストは、\( M \) からその色の個数を引いた値な ...

AOJ, bitDP, 動的計画法, 累積和

問題方針

素直に浮かぶ方針は、並び方を全通り試すという方法ですが、このときの場合の数は、\( M!\) となるので、計算量が多すぎます。ここで、次のことに着目します。ぬいぐるみを \( k \) 種類整列済みであるとき、\( k + 1 ...