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

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

問題方針累積和

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

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

問題方針

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

yukicoder, 数学, 累積和

問題方針絶対値の和の最小化問題

配列 \(a \) に対して、次の関数を最小化することを考えます。

\

答えから言うと、\( x \) が \( a \) の中央値のとき最小となります。証明は下のサイトから参照で ...

AtCoder, 数学, 累積和

問題方針交流コスト

交流コストを \( c \) と置くと、

\

となります。このシグマの計算回数は、\( \dfrac{N(N – 1)}{2}\) となり、\( N \) 人から \( 2 \) ...

AtCoder, いもす法, 累積和

問題方針\( 1 \) 枚のカードで全てのゲートを通過できるとは?

\( 1 \) 枚のカードで全てのゲートを通過できるとはどいうことかを考えます。ID が \( a \) のカードが全てのゲートを通過できるとき、全てのゲート \( i ...

AtCoder, 数学, 累積和

問題方針最大公約数の性質

関数 \( f(\cdot) \) を最大公約数を求める関数とします。ここで、\(f(x, y)\) は \( x, y \) の最大公約数とし、\( f(x, y, z) \) は \( x, y, z\) ...

AtCoder, 累積和

問題方針最終的な形を考える

\( K \) 回までの指示をした時の文字列において、最大何個の 1 が連続して並んでいるかを問われているので、指示の順番を考慮する必要がないことが分かります。つまり、最終的な形がどのようになるかを考えればよ ...