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

AtCoder,区間系,累積和

問題方針

プライムの加入が最適である期間は、期間内で利用するサービスの料金が \( C \) 円を超えるときです。なので、プライムに加入するかどうかを決める時点は \( a_i, b_i \) の値だけを考えれば良いです。

...

Codeforces,全探索,累積和

問題方針

高さが \( k \) の木を作れるかどうかは、連続する ‘*’ の数が分かればいいので、連続する ‘*’ を累積和を用いて数えます。あるマスから下に向かって順番に高さ \( k ...

AtCoder,動的計画法,累積和

問題方針

まず、壁がない場合を考えます。

\( d(i, j) \) をマス \( (1, 1)\) から マス \( (i, j) \) への移動方法の数とします。\( d(i, j) \) は、\( n = \min ( ...

AtCoder,いもす法

問題方針

ある時間において使用される水の最大値が \( W \) を超えなければ良いので、いもす法を使います。

コード#include <bits/stdc++.h>using namespace std;typedef l ...

AtCoder,全探索,数学,累積和

問題方針

\( A \) の累積和を \( b \) とし、\( b \) の累積和を \( c \) とすると、

\begin{eqnarray}
b_i &=& A_1 + A_2 + \cdot ...

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

問題方針

\( H, W \) を昇順に並び替えても一般性は失われないので、昇順に並び替えます。例えば、\( 2n \) 人の児童の最適なペアは

\

であると考えられます。これを問題に当てはめて考えると、\( N ...

Codeforces,動的計画法,累積和

問題

数字列 \( n \) の部分列を取り除いて得られる整数の総和と求めます。

方針部分列について

自然数 \( l \) を \( l = |n| \) とします。ここで、総和に対する \( i \) 文字目の整数 \( ...

Codeforces,数え上げ,累積和,貪欲法

問題方針

AGC 023 A – Zero-Sum Ranges と似ている問題です。\( s \) を \( a \) の累積和として、

\

とします。また、\( s_0 = 0 \) です。ある部 ...

AtCoder,全探索,累積和

問題方針

長方形の和は二次元の累積和を使うことで高速に求めることができるので、全ての長方形のパターンを計算し、\( i \) 個のたこ焼きを焼くときの最大値 \( d(i) \) を求めます。\( d(j) > d(i) \ (j ...

AtCoder,動的計画法,累積和,遅延評価セグメント木

問題方針遅延評価セグメント木

動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( \) から整数を選 ...