AtCoder NoviStepsを埋めてみる(22) ポテンシャル付き Union-Findの続きです。今回は累積和です。累積和を使えば大量の区間和を高速に求めることができるようになります。
累積和とは何か？ 038 – How Many Guests?
問題の概要
某遊園地で N 日間にわたるイベントが開催され、i 日目 には A[i] 人が来場した。
以下の Q 個の質問に答えるプログラムを作成せよ。
（質問）L[i] 日目から R[i] 日目までの合計来場者数は？
累積和を知らないならこんなコードを書くしかないですが、これでは TLE 必至です。時間計算量は O(QN) です。N, Q の値を考えると絶対に間に合いません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int i = 0; i < Q; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0] - 1; int b = ab[1] - 1; int sum = 0; for (int j = a; j <= b; j++) sum += A[j]; Console.WriteLine(sum); } } } |
ではどうするかですが、最初に i までの区間和を計算しておきます。[0, i] の区間和を sums[i + 1] に格納しておきます。
|
1 2 3 |
int[] sums = new int[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; |
そうすると [x, y] の区間和であれば sums[y] – sums[x – 1] で求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] sums = new int[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; for (int i = 0; i < Q; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0]; int b = ab[1]; Console.WriteLine(sums[b] - sums[a - 1]); } } } |
B – 果物の収穫
問題の概要
数列 A が与えられる。
連続する K 個の要素を選んだときの区間和の最小値を求めよ。
区間和の最小値を求める問題です。[i, i + K – 1] の区間和をすべて調べて最小のものを出力すればよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Program { static void Main() { int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nk[0]; int K = nk[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] sums = new long[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; long ans = long.MaxValue; for (int i = 0; i + K < sums.Length; i++) ans = Math.Min(ans, sums[i + K] - sums[i]); Console.WriteLine(ans); } } |
040 – Travel
問題の概要
N 個の駅があり、駅 i と駅 i + 1 距離は A[i] である。
駅 B[0] から出発し、駅 B[M – 1] まで順番に移動する場合の総移動距離を求めよ。
累積和で各駅の 駅 0 からの距離を求めれば、駅 i と駅 i + 1 間の距離は sums[Math.Max(B[i], B[i + 1])] – sums[Math.Min(B[i], B[i + 1])] で計算できます。あとはすべて足すだけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int M = int.Parse(Console.ReadLine()); int[] B = new int[M]; for (int i = 0; i < M; i++) B[i] = int.Parse(Console.ReadLine()) - 1; long[] sums = new long[A.Length + 1]; for (int i = 0; i < A.Length; i++) sums[i + 1] = sums[i] + A[i]; long ans = 0; for (int i = 0; i < M - 1; i++) ans += sums[Math.Max(B[i], B[i + 1])] - sums[Math.Min(B[i], B[i + 1])]; Console.WriteLine(ans); } } |
A – Abundant Resources
問題の概要
数列 A が与えられる。
連続する区間の長さが 1, 2, …, N の区間和の最大値をそれぞれ求めよ。
すべての区間和を調べ、区間の長さで分けて dic に格納します。最後にそれぞれの最大値をとればよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] sums = new long[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; Dictionary<int, List<long>> dic = new Dictionary<int, List<long>>(); for (int left = 0; left < sums.Length; left++) { for (int right = left + 1; right < sums.Length; right++) { long v = sums[right] - sums[left]; int len = right - left; if(!dic.ContainsKey(len)) dic.Add(len, new List<long>()); dic[len].Add(v); } } for (int i = 1; i <= N; i++) Console.WriteLine(dic[i].Max()); } } |
010 – Score Sum Queries（★2）
問題の概要
クラスは 2 つあり、学籍番号 i 番の生徒のクラスは C[i] 組である。
学籍番号 i 番の生徒の試験の点数は P[i] 点であった。
学籍番号が L[j] 番から R[j] 番までの 1 組と 2 組の生徒の合計点をそれぞれ求めよ。
配列 A, B を定義し、学籍番号 i 番で 1 組であるなら A[i] に P[i]を、2 組であるなら B[i] に P[i]を代入します。A, B それぞれの累積和から学籍番号が L[j] 番から R[j] 番までの 1 組と 2 組の生徒の合計点をそれぞれ求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = new int[N]; int[] B = new int[N]; for (int i = 0; i < N; i++) { int[] cp = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int c = cp[0]; int p = cp[1]; if (c == 1) A[i] = p; if (c == 2) B[i] = p; } long[] sumsA = new long[N + 1]; long[] sumsB = new long[N + 1]; for (int i = 0; i < N; i++) { sumsA[i + 1] = sumsA[i] + A[i]; sumsB[i + 1] = sumsB[i] + B[i]; } int Q = int.Parse(Console.ReadLine()); for (int i = 0; i < Q; i++) { int[] lr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int l = lr[0]; int r = lr[1]; long v1 = sumsA[r] - sumsA[l - 1]; long v2 = sumsB[r] - sumsB[l - 1]; Console.WriteLine($"{v1} {v2}"); } } } |
C – K-bonacci
問題の概要
正整数 N, K が与えられる。
長さ N + 1 の数列 A の各要素の値を、以下の方法で定義する。
0 ≦ i < K のとき A[i] = 1
K ≦ i のとき A[i] = A[i – K] + A[i – K + 1] + … + A[i – 1]
A[N] を 10^9 で割ったあまりを求めよ。
累積和を使えば A[i – K] + A[i – K + 1] + … + A[i – 1] を高速で求めることができます。剰余をとることで sums[i] – sums[i – K] が負数になる場合があります。この場合は 10^9を足して非負数にする必要があります。また N < K のときは常に 1 が解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Program { static void Main() { int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nk[0]; int K = nk[1]; if (N < K) { Console.WriteLine(1); return; } long mod = (long)Math.Pow(10, 9); long[] A = new long[N + 1]; long[] sums = new long[N + 2]; for (int i = 0; i < K; i++) { A[i] = 1; sums[i + 1] = sums[i] + A[i]; } for (int i = K; i <= N; i++) { A[i] = sums[i] - sums[i - K]; A[i] %= mod; if(A[i] < 0) A[i] += mod; sums[i + 1] = sums[i] + A[i]; sums[i + 1] %= mod; } Console.WriteLine(A[N]); } } |
C – 投票 (Voting)
問題の概要
ある議題に関して「賛成」か「反対」かを問う採決が行われた。投票者は N 人である。
各人は自分の投票前にそれまでに投票した他の人がどちらに投票したかを知ることができた。
i 番目に投票した人は 自分の直前に投票した X[i] 人のうち Y[i] 人以上が賛成に投票したときだけ賛成に投票し、そうでないときは反対に投票した。
賛成に投票した人の人数を求めよ。
動的に累積和を構築する問題です。i 番目の人が投票したら i 番目までに投票した人が投じた賛成票の数を sums[i + 1] に保存しておきます。これで自分の直前に投票した X[i] 人のうち Y[i] 人以上が賛成に投票したかどうかがわかるようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); long[] sums = new long[N + 1]; for (int i = 0; i < N; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = xy[0]; int y = xy[1]; sums[i + 1] = sums[i] + (sums[i] - sums[i - x] >= y ? 1 : 0); } Console.WriteLine(sums[N]); } } |
C – GeT AC
問題の概要
A, C, G, T からなる長さ N の文字列 S が与えられる。
l[i] 文字目から r[i] 文字目までの (両端含む) 連続部分文字列のなかに “AC” は部分文字列として何回現れるか。
配列 A を定義し、A[i] に S[i] == ‘A’ && S[i + 1] == ‘C’ であれば 1 そうでないなら 0 を代入します。あとは累積和を取れば l[i] 文字目から r[i] 文字目までに現れる部分文字列 “AC” の個数がわかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; string S = Console.ReadLine(); int[] A = new int[N - 1]; for (int i = 0; i < N - 1; i++) A[i] = (S[i] == 'A' && S[i + 1] == 'C') ? 1 : 0; long[] sums = new long[A.Length + 1]; for (int i = 0; i < A.Length; i++) sums[i + 1] = sums[i] + A[i]; for (int i = 0; i < Q; i++) { int[] lr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int l = lr[0] - 1; int r = lr[1] - 1; Console.WriteLine(sums[r] - sums[l]); } } } |
C – Rotate and Sum Query
問題の概要
長さ N の整数列 A が与えられる。
Q 個のクエリを順に処理せよ。
クエリ 1：A の先頭の要素を末尾に移動させる操作を c 回おこなう。
クエリ 2：[l, r] の区間和を出力する。
区間和は累積和をつかって計算するのですが、数列の要素が変化してしまうと対応できないので クエリ 1 が来た後 クエリ 2 が来たら求める区間を適切に変更することでこれに対応します。
|
1 2 3 4 5 |
l--; l += shift; l %= N; r += shift; r %= N; |
ただ単純に上記の処理だけだと剰余を取ったときに r ≦ l になってしまうことがあるので困ります。そこで r ≦ l のときは r に N を加算して l < r の関係が維持されるようにしています。この場合は累積和は N までではなく 2N まで計算しておく必要があります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] sums = new long[2 * N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; for (int i = 0; i < N; i++) sums[i + 1 + N] = sums[i + N] + A[i]; int shift = 0; for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = query[0]; if (t == 1) { int c = query[1]; shift += c; shift %= N; } if (t == 2) { int l = query[1]; int r = query[2]; l--; l += shift; l %= N; r += shift; r %= N; if (r <= l) r += N; Console.WriteLine(sums[r] - sums[l]); } } } } |
C – Comfortable Distance
問題の概要
文字列 S が与えられる。
S[i] = S[j] (i ≦ j, L ≦ j – i ≦ R) である整数の組 (i, j) の個数を求めよ。
各 i において S[j] = S[i] ( j は [i + L, i + R]) である j の個数を数えればよいです。i 文字目までで各文字が何回出現しているかを累積和で取得しておけば、[i + L, i + R] 間にある S[i] と同じ文字の出現回数は count_sums[ch, Math.Min(i + R + 1, N)] – count_sums[ch, Math.Min(i + L, N)] で計算できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Program { static void Main() { int[] nlr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nlr[0]; int L = nlr[1]; int R = nlr[2]; string S = Console.ReadLine(); int[,] counts = new int[26, N]; int[,] count_sums = new int[26, N + 1]; for (int i = 0; i < N; i++) { int ch = S[i] - 'a'; counts[ch, i] = 1; } for (int ch = 0; ch < 26; ch++) { for (int i = 0; i < N; i++) count_sums[ch, i + 1] = count_sums[ch, i] + counts[ch, i]; } long ans = 0; for (int i = 0; i < N; i++) { int ch = S[i] - 'a'; int v = count_sums[ch, Math.Min(i + R + 1, N)] - count_sums[ch, Math.Min(i + L, N)]; ans += v; } Console.WriteLine(ans); } } |
D – Swap and Range Sum
問題の概要
長さ N の数列 A が与えられる。
Q 個のクエリを処理せよ。
クエリ 1：A[x] と A[x + 1] の値を入れ替える。
クエリ 2：区間和 [l, r] を求める。
累積和の弱点として「値が更新されるケースに対応できない」があります。クエリ 1 で値が更新されるため、累積和では解けなさそうなのですが、隣と値を入れ替えるだけなので事前に計算しておいた累積和のうち更新が必要なのは一箇所だけです。なのでこの場合は累積和で対応できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] sums = new long[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + A[i]; for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = query[0]; if (t == 1) { // 隣と値を入れ替えるだけなので、sums の更新が必要なのは一箇所だけ int x = query[1]; int old = A[x - 1]; (A[x - 1], A[x]) = (A[x], A[x - 1]); int diff = A[x - 1] - old; sums[x] += diff; } if (t == 2) { int l = query[1]; int r = query[2]; Console.WriteLine(sums[r] - sums[l - 1]); } } } } |
C – Striped Horse
問題の概要
1 から N の番号がついた N 個の白いマスが一列に並んでいる。
正整数 x を自由に選んで、1 ≦ i ≦ N を満たす整数 i のうち、 i + x を 2W で割った余りが W より小さくなるものはすべて黒く塗る。そのさい コスト C[i] が必要である。
コストの合計の最小値を求めよ。
「W マス連続して黒く塗り、続けて W マス連続して白いままにする」という塗り方をすべて試します。このとき、W = 3 なら ●◯◯◯●●●◯◯◯●●● のように、最初に 1 個以上、W 個未満の黒マスがある場合を見落とさないように注意が必要です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
class Program { static void Main() { int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { Solve(); } void Solve() { int[] nw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nw[0]; int W = nw[1]; int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] sums = new long[N + 1]; for (int i = 0; i < N; i++) sums[i + 1] = sums[i] + C[i]; long ans = long.MaxValue; for (int ofset = 0; ofset < 2 * W; ofset++) { int j = -1; long cost = 0; while (true) { int right = Math.Min(sums.Length - 1, (2 * j + 1) * W + ofset); if (right <= 0) { j++; continue; } int left = Math.Min(sums.Length - 1, (2 * j) * W + ofset); if (right == left) break; if(left < 0) left = 0; long v = sums[right] - sums[left]; cost += v; j++; } ans = Math.Min(ans, cost); } Console.WriteLine(ans); } } } |
