#はじめに
累積和に感動したので累積和を使う問題をまとめます。
詳細な解説もそのうち・・・
累積和そのものの解説についてはけんちょん先生の記事が最強なので、まずは熟読すると良いと思います。
僕のコードもけんちょん先生の流儀をリスペクトした形で書くつもりです。
累積"和"に限らず、累積和的考え方を用いた問題も載せていきます。
キーとなる思想は「前処理に時間をかけてクエリには爆速で答える」です。
#全国統一プログラミング王決定戦本選 A
まずは The 累積和って感じの問題。
この最も典型的な累積和が着想から実装まで淀みなく出来るか確認しよう。
##解答
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
int n; cin >> n;
vector<ll> a(n); rep(i, n) cin >> a[i];
vector<ll> s(n+1); rep(i, n) s[i+1] = s[i] + a[i];
for (int k = 1; k <= n; k++) {
ll ans = 0;
for (int i = 0; i+k <= n; i++) {
// 始点 i, 長さ k の区間の和は s[i+k] - s[i] で取り出せる
chmax(ans, s[i+k] - s[i]);// chmax(A,B) は A = max(A,B) と同じ
}
cout << ans << '\n';
}
}
#ABC 037 C- 総和
続いてまさに「累積和を使ってくれ～！！！」という叫びが聞こえてくるような問題。
##解答
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define vl vector<ll>
int main(){
int n,k; cin >> n >> k;
vl a(n); rep(i, n) cin >> a[i];
vl s(n+1); rep(i, n) s[i+1] = s[i] + a[i];
ll ans = 0LL;
for (int i = 0; i+k <= n; i++) {
ans += s[i+k] - s[i];
}
cout << ans << '\n';
}
#ABC 134 C - Exception Handling
"累積max" の問題。
「前処理で西と東の予選を $O(n)$ で事前にやっといて決勝を $O(1)$ で行う」みたいなイメージ。
単に解くだけなら次のような方針で解ける。
「最大値、２番目の最大値とその index を記録しておいて最大値の index の時だけ第二位の値を出力、それ以外の時は最大値を出力」
勿論、コンテスト中はそれで良い！
しかしこの予選・決勝タイプの累積和の考え方を養うのに非常に良い問題。
##解答
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
#define vi vector<int>
int main(){
int n; cin >> n;
vi a(n); rep(i, n) cin >> a[i];
//a[0], a[1], a[2]
vi lm(n);// lm[i]; iより左にある者たちの中でのmax。 便宜上 lm[0]=0 としておく
vi rm(n);// rm[i]; iより右にある者たちの中でのmax。 便宜上 rm[n-1] = 0
// 求める値は max(lm[i],rm[i]) (i = 0,1,2,...,n-1) の最大値
for(int i = 1; i < n; i++) lm[i] = max(lm[i-1],a[i-1]);
for(int i = n-2; i >= 0; i--) rm[i] = max(rm[i+1],a[i+1]);
rep(i, n) cout << max(lm[i], rm[i]) << '\n';
}
#ARC098 C - Attention
今度はさっきのと同じ方針を"累積和"でやる問題。
##解答
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
#define vi vector<int>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
int n; cin >> n;
string s; cin >> s;
// LW[i]:i番目の人よりLeft にいる人のうち、Wを向いている人の数
// RE[i]:i番目の人よりRightにいる人のうち、Lを向いている人の数
// 求める答えは、LW[i]+RE[i]のうち最小のもの
vi LW(n),RE(n);
// LW の決定。LW[0]=0 としてよい
for (int i = 1; i < n; i++) {
if(s[i-1]=='W') LW[i] = LW[i-1] + 1;
else LW[i] = LW[i-1];
}
// RE の決定。RE[n-1]=0
for (int i = n-2; i >= 0; i--) {
if(s[i+1]=='E') RE[i] = RE[i+1] + 1;
else RE[i] = RE[i+1];
}
int ans = 1e9;
rep(i, n) chmin(ans,LW[i]+RE[i]);
cout << ans << '\n';
}
#Tenka1 Programmer Contest 2019 C - Stones
ほぼ同じ問題。
##解答
#ABC C - GCD on Blackboard
初見だとぎょぎょっ！とするけど、「好きな数字を書き換える」が「邪魔な数字を無視する」と同じなこと、そして gcd はどこから計算しても変わらないこと に気が付けば、後は前の三問と同じ。
実は後者の性質が重要で、これを満たす演算についてはこの累積和的考え方が使える。（sum, max, min, gcd の他には例えば xor とか行列の積とか）
実装は端っこの処理が少し面倒かもしれない。
##解答
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
#define vi vector<int>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int gcd(int a, int b) {
if (b == 0) return a;
else return gcd(b, a % b);
}
int main(){
int n; cin >> n;
vi a(n); rep(i, n) cin >> a[i];
vi lgcd(n),rgcd(n);
/* editorial とは定義が違うので注意
lgcd[i]:A[i]より左側にある数字達(A[i]は含まない)のgcd
rgcd[i]:A[i]より右側にある数字達(A[i]は含まない)のgcd
つまり、
lgcd[i] = gcd(A[0],A[1],...,A[i-1])
rgcd[i] = gcd(A[i+1],A[i+2],...,A[n-1])
*/
lgcd[0] = a[0];
for (int i = 1; i < n; i++) lgcd[i] = gcd(lgcd[i-1],a[i-1]);
rgcd[n-1] = a[n-1];
for (int i = n-2; i >= 0; i--) rgcd[i] = gcd(rgcd[i+1],a[i+1]);
int ans = 0;
chmax(ans,rgcd[0]);// i = 0 は別処理
for(int i = 1; i < n-1; i++){
chmax(ans, gcd(lgcd[i],rgcd[i]));
}
chmax(ans, lgcd[n-1]);// i = n-1 も別処理
cout << ans << '\n';
}
#ABC 124 D - Handstand
累積和、しゃくとり法、二分探索と様々な方法で解ける良問。
ランレングス圧縮して累積和が想定解っぽい。
公式解説放送がちょくだいさんで、非常に丁寧でお勧めなので解説はこちらにお譲りします。（ちなみにこの動画は 51:30 あたりでちょくだいさんが間違えて嘘解法で通しちゃって慌てているのがかわいいので、ぜひ一度見てほしいです。）
##解答
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
#define vi vector<int>
#define pb push_back
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
int n,k; string s;
cin >> n >> k >> s;
vi C;
int now = 1, cnt = 0;
rep(i, n){
if(s[i] == (char)(now + '0')) cnt++;
else{
C.pb(cnt);
now = 1 - now;
cnt = 1;
}
}
C.pb(cnt);
if(C.size()%2 == 0) C.pb(0);
int m = C.size();
vi S(m+1); rep(i, m) S[i+1] = S[i] + C[i];
int ans = 0;
for (int i = 0; i < m; i += 2) {
//chmax(ans, S[i+2*k+1] - S[i]); これじゃダメ
int left = i;
int right = min(i+2*k+1,m);// ここ気を付ける
chmax(ans, S[right] - S[left]);
}
std::cout << ans << '\n';
}
#ABC 129 D - Lamp
けんちょん先生の記事にあるような典型的な二次元累積和ではないが、累積和が使える。
詳しい方針は公式の editorial を参照。
とにかく 前処理に時間をかけてクエリには爆速で答える の考え方が大事。
##解答
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
int H,W; cin >> H >> W;
vector<string> s(H);
rep(i, H) cin >> s[i];
int l[H][W] = {}, r[H][W] = {}, u[H][W] = {}, d[H][W] = {};
rep(h, H) rep(w, W){
if(s[h][w] == '#') {l[h][w] = 0;u[h][w] = 0;}
else{
if(h == 0) u[h][w] = 1;
else u[h][w] = u[h-1][w] + 1;
if(w == 0) l[h][w] = 1;
else l[h][w] = l[h][w-1] + 1;
}
}
for (int h = H-1; h >= 0; h--) for(int w = W-1; w >= 0; w--){
if(s[h][w] == '#') {r[h][w] = 0; d[h][w] = 0;}
else{
if(h == H-1) d[h][w] = 1;
else d[h][w] = d[h+1][w] + 1;
if(w == W-1) r[h][w] = 1;
else r[h][w] = r[h][w+1] + 1;
}
}
int ans = 0;
rep(h, H) rep(w, W){
chmax(ans,l[h][w]+r[h][w]+u[h][w]+d[h][w]-3);
}
cout << ans << '\n';
}
#ABC 143 D - Triangles
多分二分探索が想定解で、しゃくとり法と累積和でも解ける。
三角形の成立条件が abs(a-b) < c < a+d と同値あることに気が付けば、あとは累積和、、、、、というほど楽でもないと思う。
コンテスト中は累積和で行こうとしたが「何の値が何個あるかをカウントする」という方法が思い付かず、爆死。重複に気を使うところも難しい。
解答解説はけんちょん先生のブログにお譲りいたします。
#ABC 133 D - Rain Flows into Dams
累積和勉強したての頃にこの問題に出会って、「累積和だ！！！」となってしまい、必死に実装した問題。
書き終わってみればそんなに長くはないけど結構苦労した。。。
n個の答えを求めるのに、n/2 個の和を計算する必要があるから、まさに累積和が使える構造。
……だけど、実際は答え1個を普通に求めれば残りは漸化式を使ってそれぞれ O(1) で簡単に求まる（editorial 参照）ので、あまり賢い方法ではない。
##解答
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
int main(){
ll n,sum = 0;// sum は数列 a の全要素の和
cin >> n;
vector<ll> a(n),s(2*n+2,0);
rep(i, n){
cin >> a[i];
sum += a[i];
}
rep(i, 2*n) s[i+2] = s[i] + a[(i%n)];//累積和
int m = n/2;
rep(i, n){
ll ans = sum;
ans -= 2*(s[i+1+2*m]-s[i+1]);
std::cout << ans << '\n';
}
}
#DISCO presents (略) 2020予選 B - Iron Bar Cutting
累積和を知らない人でも累積和を意識せずとも自然に使って解きそうな問題。
##解答
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define vl vector<ll>
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const ll INF = 1LL << 60;
int main(){
int n; cin >> n;
vl a(n); rep(i, n) cin >> a[i];
vl s(n+1); rep(i, n) s[i+1] = s[i] + a[i];
ll ans = INF;
rep(i, n){
chmin(ans, abs(s[i+1] - (s[n] - s[i+1]) ) );
}
cout << ans << '\n';
}
#ABC 105 D - Candy Distribution
けんちょん先生の記事で解説されている、
AGC 023 A-Zero-Sum Ranges
とほぼ同じ問題、解説はそちらに飛ぶことをおすすめします。
なお、最後の答えの集計の仕方は次の問題との兼ね合いでけんちょん先生の書き方とは異なっています。
##解答
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define vl vector<ll>
int main(){
int n,m; cin >> n >> m;
vl a(n); rep(i,n) cin >> a[i];
vl s(n+1); rep(i,n) s[i+1] = (s[i] + a[i])%m;
// mapを使って累積和の剰余類ごとの個数を管理
map<ll,ll> C;
ll ans = 0LL;
rep(i,n+1) {
ans += C[s[i]];
C[s[i]]++;
}
cout << ans << endl;
}
なお、map C の宣言の真下のループを見ると、「この書き方だとC[s[i]]が定義される前にアクセスしちゃうことあるじゃん！」 思ってしまうが、実は map は定義されていない C[key] にアクセスすると自動的に ( value が int や ll の場合は) 0で初期化してデータを追加してくれる。（うれしい）
APG4bなどを参照。
#ABC 146 E - Rem of Sum is Num
これも前問とほぼ同じ問題。
さっきの問題は「部分和の余りが0に等しい」だったのが「部分和の余りが要素数に等しい」に変わっている。これを何とかしようと考えていると、「各 $A_i$ を予め１引いておく」と前の問題に帰着すると閃く（天才）。
こんなん天才しか無理やろ！！！と最初は思うけど、実はこういう「予め引いとく」系の工夫はよく使われるっぽい。
例えばこの問題やこの問題でも同じ工夫が使える。
これらのキーワードが頭に入った状態で公式解説を見ると理解が深まるはず。
##解答（公式解説動画のそれと同じ）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define vl vector<ll>
int main(){
int n,k; cin >> n >> k;
vl a(n);
rep(i,n){
cin >> a[i];
a[i]--;
}
vl s(n+1); rep(i,n) s[i+1] = (s[i] + a[i])%k;
map<ll,int> C;
queue<int> q;
ll ans = 0LL;
rep(i,n+1) {
ans += C[s[i]];
C[s[i]]++;
q.push(s[i]);
// 長さが k 以上隔てたペアはカウントしないようにする
if(q.size() == k){
C[q.front()]--;
q.pop();
}
}
cout << ans << endl;
}
#ABC 158 E - Divisible Substring
類題が続きます。これははじめてコンテスト中に通せた青diffで、精進は無駄じゃなかったと感動した非常に思い入れのある問題。なので少し詳しめに解説しちゃう。
例えば $P = 3$ の時なら、「ある数 $N$ が3で割れるかどうか」と「$N$ の各桁の和が3で割れるかどうか」が同値なことはあまりにも有名で、これならCandy Distributionと全く一緒。
この考え方を一般化すると、 $N$ の $i$ 桁目の数を $S[i]$として、次のような数列 $A[i]$ を考えれば良いような気がしてくる。
A[i] := (S[i]\times10^i) \% P
思えば $P = 3$ の時も本当はこれを考えていて、 $10\equiv1$ だからたまたま $A[i] = S[i]$ になっていて分かりやすいから有名になっているだけだった。
だけどこれだと一歩足りない。というのも、例えば
N = 3543
のとき、判定しないといけないのは「$35$ は $P$ で割り切れるかどうか」なわけだけど、数列 $S[i]$ に対する累積和で判定できるのは 「$35\times10^2$ が $P$ で割り切れるかどうか」だからであり、両者が同値になるのは $10^2$ と $P$ が互いに素な時だけ。
しかし今は $P$ が素数なことを考えると、このような例外は2と5の時だけなことに気付く（だから $P$ は素数だったのか！！！！）
##解答
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
#define ll long long
#define vl vector<ll>
int main(){
int n, p; cin >> n >> p;
string s; cin >> s;
ll ans = 0;
// s[i] = (i桁目の数) となると嬉しいので逆順に
reverse(s.begin(),s.end());
// 例外処理
if(p == 2 || p == 5){
rep(i,n) {
int num = s[i]-'0';
if(num%p == 0){
// i 桁目の数が p で割り切れるなら、それを先頭にした連続部分列は全部 p で割り切れる
ans += n-i;
}
}
cout << ans << endl;
return 0;
}
vl a(n);
ll mul = 1;
rep(i,n) {
int num = s[i]-'0';
a[i] = (num * mul) % p;
mul = (mul * 10) % p;
}
vl sum(n+1);
rep(i,n) sum[i+1] = (sum[i] + a[i]) % p;
map<int,int> C;
rep(i,n+1) {
ans += C[sum[i]];
C[sum[i]]++;
}
cout << ans << endl;
}
#ABC 106 D - AtCoder Express 2
区間を二次元に焼き直すと自然と二次元累積和が見えてくる問題。
いや、初見じゃ思い付かない………。けど非常に面白い問題。
- $p \leq L_i \leq R_i \leq q$ なる組 $(L_i,R_i)$ なる組の個数を答えよ
- 正方形 $[p,q]\times[p,q]$ に含まれる点 $(L_i,R_i)$ の個数を数えよ
のような言い換えができるとと思い付くのかなあ…
ちょくだいさんが詳しく解説してくれているので、公式解説も見ると良い。
二次元累積和についてはけんちょん先生の解説を参照。
##解答
公式解説のコードを我々の流儀で書き直すと以下のようになる。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
int a[510][510];
int s[510][510];
int main(){
int n, m, Q; cin >> n >> m >> Q;
rep(i,m) {
int l, r; cin >> l >> r;
l--; r--;
a[l][r]++;
}
rep(i,n) rep(j,n) {
s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + a[i][j];
}
while(Q--){
int p, q; cin >> p >> q;
p--; q--;
cout << s[q+1][q+1] - s[q+1][p] - s[p][q+1] + s[p][p] << endl;
}
}
#ABC 089 D - Practical Skill Test
ぱっと見愚直な実装で通るような気がして、TLE を連発してしまった…
$L_i$ から $R_i$ に至るまでを愚直にシミュレーションしたら、1 クエリあたりの計算量は $O((R_i-L_i)/D)$で、これが最悪 $O(HW)$ になるからダメ。
ここを高速化するとなると、累積和は必ず候補として思い付く。
そこで「じゃあ累積和はどうかな？」という目でもう一度問題を見直すと、累積和が使える構造になっていることを見抜くのはそんなに難しくない。
##解答
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
int a[310][310];
int s[100100];
// C[i] := 数 i がどこにあるか(h,w)を記録する
pair<int,int> C[100100];
int main(){
int H, W, D; cin >> H >> W >> D;
rep(h,H) rep(w,W) {
cin >> a[h][w];
a[h][w]--;
C[a[h][w]] = make_pair(h,w);
}
// s[i+k*D] - s[i] で 「i から始まる k 個の和」を求められるように定義した
for(int i = 0; i+D < H*W; i++) {
int h = C[i].first, w = C[i].second;
int nh = C[i+D].first, nw = C[i+D].second;
int dh = abs(h-nh);
int dw = abs(w-nw);
s[i+D] = s[i] + dh + dw;
}
// rep(i,H*W){
// if(i < H*W-1) printf("%d ", s[i]);
// else printf("%d\n", s[i]);
// }
int q; cin >> q;
while(q--){
int l, r; cin >> l >> r;
l--; r--;
cout << s[r]-s[l] << endl;
}
}
#ABC 047 D - 高橋君と見えざる手
累積min または累積max が使える問題。
高橋君が売り買いする町はそれぞれ一つとして良い。
売る町を全探索することを考える。
売る町を $i$ で固定すると、この場合どこで買っておけば良かったかというと町 $0$ から町 $i-1$ の中で一番安いところである。
したがって町 $i$ で売る場合の利益は、 $A_{min}[i] := min(A[0],A[1],...,A[i-1])$ なる累積min を持っておけば、$A[i]-A_{min}[i]$ と $O(1)$ で取得できる。
求める答えは
max_{0 \leq i \le n}(A[i]-A_{min}[i]) = (A[j]-A_{min}[j])
を満たす $j$ の個数。
##解答
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int a[100100];
int a_min[100100];
int main(){
int n, t; cin >> n >> t;
rep(i,n) cin >> a[i];
rep(i,n) {
if(i == 0){
a_min[i] = 1e9; // a_min[0] は未定義
continue;
}
a_min[i] = min(a_min[i-1], a[i-1]);
}
int tmp = 0;
rep(i,n) chmax(tmp,a[i]-a_min[i]);
int ans = 0;
rep(i,n) if(tmp == a[i]-a_min[i]) ans++;
cout << ans << endl;
}
#ABC 062 D -3N Numbers
n要素の累積minと累積maxを使う問題。
直接的には今まで出ていないけど、累積〇のお気持ちが分かっていれば自然と思い付けるはず。
##解答
#ABC 095 D - Static Sushi
なんか累積和とか累積maxをいっぱい取る問題
##解答
#JSUTC 202004 D - Calculating GCD
累積gcd + 二分探索
##解答
#類似アルゴリズム
累積和は"区間"、"和" などがキーワードのアルゴリズムでした。
そこで例えばこの問題を見てみると、いかにも累積和が使えそうに思えます。
しかし累積和を使っても計算量を $O(n^3)$ から $O(n^2)$ までしか落とせず、間に合いません。
このようなある種の"単調性"が加わった構造の問題に対しては、しゃくとり法というアルゴリズムが使えます。
これも僕が累積和を学んだ直後に勉強し、感動したアルゴリズムです！
面白い上に競プロでも頻出なので興味が湧いたら次の記事などで勉強することをお勧めします！
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
#終わりに
累積和を使う問題を見付けたら随時追加していきます。
初学者ゆえ至らない点は多々あると思いますので、気になることがあればご指摘お願いいたします。