今回はpaiza 累積和メニューセクション1【区間の和】を解説します。
セクション1は、累積和から区間和を求める問題です。
本記事で使用しているアルゴリズムやメソッドについて
解答例で使っているアルゴリズムやメソッドについて、下記の記事で詳しく解説していますので参考にしてみて下さい。
- [アルゴリズム(Ruby)]累積和
- [Ruby] 標準入力によるデータ取得1
- [Ruby] 標準入力によるデータ取得2
- [Ruby] 標準入力によるデータ取得3
- [Ruby] 標準出力（データを任意に整形して出力する）
- [Ruby]配列の基本操作1
- [Ruby]繰り返し処理
- [Ruby]条件分岐
- [Ruby]繰り返し処理
セクション1：【区間の和】
1-STEP1: 区間の和 1 (paizaランク C 相当)
a[0]からa[9]まで10個の整数を要素に持つ配列 a=[1, 5, 9, 7, 5, 3, 2, 5, 8, 4] と、左端 l=2, 右端 r=7 が与えられ、範囲内の要素の和 (a[2] + a[3] + a[4] + a[5] + a[6] + a[7]) を累積和を使って求め、出力する問題です。
Ruby解答例1
インデックスを使って累積和 s を求める方法です。
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4] l = 2 r = 7 # 累積和 n = a.length s = Array.new(n + 1, 0) 0.upto(n - 1) do |i| s[i + 1] = s[i] + a[i] end # p s # > [0, 1, 6, 15, 22, 27, 30, 32, 37, 45, 49] # a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] r_sum = s[r + 1] # a[0] + a[1] l_sum = s[l] # a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] # - a[0] + a[1] # _______________________________________________________ # = a[2] + a[3] + a[4] + a[5] + a[6] + a[7] # 区間和を出力 section_sum = r_sum - l_sum puts section_sum
Ruby解答例2
累積和sの末尾要素（初期値s[0]=0）に配列aの要素を足していく方法です。
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4] l = 2 r = 7 # 累積和 s = [0] a.each do |num| s << s[-1] + num end # 区間和を出力 section_sum = s[r + 1] - s[l] puts section_sum
Python解答例1
インデックスを使って累積和 s を求める方法です。
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
l = 2
r = 7
# 累積和
n = len(a)
s = [0] * (n + 1)
for i in range(n):
s[i + 1] = s[i] + a[i]
# print(s)
# > [0, 1, 6, 15, 22, 27, 30, 32, 37, 45, 49]
# a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]
r_sum = s[r + 1]
# a[0] + a[1]
l_sum = s[l]
# a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]
# - a[0] + a[1]
# _______________________________________________________
# = a[2] + a[3] + a[4] + a[5] + a[6] + a[7]
# 区間和を出力
section_sum = r_sum - l_sum
print(section_sum)
Python解答例2
累積和sの末尾要素（初期値s[0]=0）に配列aの要素を足していく方法です。
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
l = 2
r = 7
# 累積和
s = [0]
for num in a:
s.append(s[-1] + num)
# 区間和を出力
section_sum = s[r + 1] - s[l]
print(section_sum)
1-STEP2: 区間の和 2 (paizaランク C 相当)
a[0]からa[9]まで10個の整数を要素に持つ配列 aと、左端 l=2, 右端 r=7 が与えられ、範囲内の要素の和 (a[2] + a[3] + a[4] + a[5] + a[6] + a[7]) を累積和を使って求め、出力する問題です。
ただし、配列aの要素は半角スペース区切りで標準入力から与えられます。
入出力例
INPUT1の例
a[2] + a[3] + a[4] + a[5] +a[6] + a[7] = 3 + 4 + 5 + 6 + 7 + 8 = 33
を、累積和で求める。
INPUT1 = <<"EOS" 1 2 3 4 5 6 7 8 9 10 EOS OUTPUT1 = <<"EOS" 33 EOS
Ruby解答例
配列aの要素を受け取るコードを追加します。あとは、STEP1-解答例2と同じコードです。
l = 2 r = 7 # 入力 a = gets.split.map(&:to_i) # 累積和 s = [0] a.each do |num| s << s[-1] + num end # 区間和を出力 section_sum = s[r + 1] - s[l] puts section_sum
Python解答例
配列aの要素を受け取るコードを追加します。あとは、STEP1-解答例2と同じコードです。
l = 2
r = 7
# 入力
a = list(map(int, input().split()))
# 累積和
s = [0]
for num in a:
s.append(s[-1] + num)
# 区間和を出力
section_sum = s[r + 1] - s[l]
print(section_sum)
1-STEP3: 区間の和 3 (paizaランク C 相当)
1行目で整数 x, y 、2行目で10個の整数 a[0], a[1] ... a[9] が半角スペース区切りで与えられ、 a[x] から a[y] の範囲内の要素の和 (a[x] + ... + a[y]) を累積和を使って求め、出力する問題です。
与えられる条件は以下の通りです。
- 0 ≦ x ≦ y ≦ 9
- 1 ≦ a_i ≦ 100 (0 ≦ i ≦ 9)
入出力例
INPUT1の例 a[2] + a[3] + a[4] + a[5] +a[6] + a[7] = 3 + 4 + 5 + 6 + 7 + 8 = 33
INPUT2の例 a[3] + a[4] + a[5] = 1 + 5 + 9 = 15
を、累積和で求める。
INPUT1 = <<"EOS" 2 7 1 2 3 4 5 6 7 8 9 10 EOS OUTPUT1 = <<"EOS" 33 EOS INPUT2 = <<"EOS" 3 5 3 5 7 1 5 9 8 5 2 4 EOS OUTPUT2 = <<"EOS" 15 EOS
Ruby解答例1
左端 x, 右端 y の入力受け取りが増えるだけで、あとはSTEP1~2と同じです。
# 入力 x, y = gets.split.map(&:to_i) a = gets.split.map(&:to_i) # 累積和 s = [0] a.each do |num| s << s[-1] + num end # 区間和を出力 section_sum = s[y + 1] - s[x] puts section_sum
Ruby解答例2
$stdin.read で入力を一括で受け取り、多重代入しています。（入力終了は ctrl+d）
# 入力
x, y, *a = $stdin.read.split.map(&:to_i)
# 累積和
s = [0]
a.each { |num| s << s[-1] + num }
# 区間和を出力
section_sum = s[y + 1] - s[x]
puts section_sum
Python解答例1
左端 x, 右端 y の入力受け取りが増えるだけで、あとはSTEP1~2と同じです。
# 入力
x, y = map(int, input().split())
a = list(map(int, input().split()))
# 累積和
s = [0]
for num in a:
s.append(s[-1] + num)
# 区間和を出力
section_sum = s[y + 1] - s[x]
print(section_sum)
Python解答例2
open(0).read() で入力を一括で受け取り、多重代入しています。（入力終了は ctrl+d）
# 入力
x, y, *a = map(int, open(0).read().split())
# 累積和
s = [0]
for num in a:
s.append(s[-1] + num)
# 区間和を出力
section_sum = s[y + 1] - s[x]
print(section_sum)
1-FINAL: 【区間の和】 区間の和 4 (paizaランク C 相当)
問題
1 行目に整数 N, X, Y が与えられます。
2 行目に N 個の整数 a_0, a_1, a_2, ..., a_(N-1) からなる数列 a が与えられます。
この数列の a_X から a_Y までの和 (a_X + a_{X + 1} + ... + a_Y) を、累積和を使うことで求め、一行で出力してください。
入力される値
- 1 行目 整数 N, X, Y が与えられます。
- 2 行目に N 個の整数 a_0, a_1, a_2, ..., a_(N-1) が与えられます。
N X Y
a_0 a_1 a_2 ... a_(N-1)
入力値最終行の末尾に改行が１つ入ります。
期待する出力
数列 a の a_X から a_Y までの和を、累積和を使うことで求め、一行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
条件
すべてのテストケースにおいて、以下の条件をみたします。
- 2 ≦ N ≦ 1,000
- 0 ≦ X < Y ≦ N-1
- 1 ≦ a_i ≦ 100 (0 ≦ i ≦ N-1)
- 入力例1
- 10 2 7
- 1 2 3 4 5 6 7 8 9 10
- 出力例1
- 33
- 入力例2
- 8 1 3
- 1 3 8 3 1 8 8 1
- 出力例2
- 14
攻略ポイント
ポイント
Ruby 問題を解く流れ
入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。
INPUT1 = <<"EOS" 10 2 7 1 2 3 4 5 6 7 8 9 10 EOS OUTPUT1 = <<"EOS" 33 EOS INPUT2 = <<"EOS" 8 1 3 1 3 8 3 1 8 8 1 EOS OUTPUT2 = <<"EOS" 14 EOS # 確認用コード p INPUT1 p OUTPUT1 p INPUT2 p OUTPUT2 # 実行結果 # > "10 2 7\n1 2 3 4 5 6 7 8 9 10\n" # > "33\n" # > "8 1 3\n1 3 8 3 1 8 8 1\n" # > "14\n"
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。
まず、入力データを受け取る処理を書きます。
def solve(input_str)
# 入力
input_lines = input_str.split("\n")
n, x, y = input_lines[0].split.map(&:to_i)
a = input_lines[1].split.map(&:to_i)
# 確認用コード
[n, x, y, a]
end
# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 出力表示
# > [10, 2, 7, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]
# > [8, 1, 3, [1, 3, 8, 3, 1, 8, 8, 1]]
データが正しく受け取れていれば、問題を解く処理を書いていきます。
まずはインデックスを使って累積和を求めます。
def solve(input_str)
# 入力
input_lines = input_str.split("\n")
n, x, y = input_lines[0].split.map(&:to_i)
a = input_lines[1].split.map(&:to_i)
# 累積和
s = Array.new(n + 1, 0)
0.upto(n - 1) do |i|
s[i + 1] = s[i] + a[i]
end
# 確認用コード
s
end
# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
# > [0, 1, 4, 12, 15, 16, 24, 32, 33]
累積和が正しく計算出来ているので、累積和s, 左端x, 右端y を使って区間和を求めるコードを追加します。
def solve(input_str)
# 入力
input_lines = input_str.split("\n")
n, x, y = input_lines[0].split.map(&:to_i)
a = input_lines[1].split.map(&:to_i)
# 累積和
s = Array.new(n + 1, 0)
0.upto(n - 1) do |i|
s[i + 1] = s[i] + a[i]
end
# a[x] から a[y] までの区間和を返す
return s[y + 1] - s[x]
end
# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# 33
# 14
INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。
Ruby 解答コード
def solve(input_str)
# 入力
input_lines = input_str.split("\n")
n, x, y = input_lines[0].split.map(&:to_i)
a = input_lines[1].split.map(&:to_i)
# 累積和
s = Array.new(n + 1, 0)
0.upto(n - 1) do |i|
s[i + 1] = s[i] + a[i]
end
# a[x] から a[y] までの区間和を返す
return s[y + 1] - s[x]
end
puts solve($stdin.read)
Ruby 他の解答例
省略できる箇所を省略してみます。
- 入力を一括で受け取る
- インデックスを使わず累積和を求める
- return を省略
def solve(input_str)
# 入力
_, x, y, *a = input_str.split.map(&:to_i)
# 累積和
s = [0]
a.each { |num| s << s[-1] + num }
# a[x] から a[y] までの区間和を返す
s[y + 1] - s[x]
end
puts solve($stdin.read)
Python 問題を解く流れ
入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。
INPUT1 = """\ 10 2 7 1 2 3 4 5 6 7 8 9 10 """ OUTPUT1 = """\ 33 """ INPUT2 = """\ 8 1 3 1 3 8 3 1 8 8 1 """ OUTPUT2 = """\ 14 """ # 確認用コード print(repr(INPUT1)) print(repr(OUTPUT1)) print(repr(INPUT2)) print(repr(OUTPUT2)) # 実行結果 # > '10 2 7\n1 2 3 4 5 6 7 8 9 10\n' # > '33\n' # > '8 1 3\n1 3 8 3 1 8 8 1\n' # > '14\n'
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。
まず、入力データを受け取る処理を書きます。
def solve(input_str):
# 入力
input_lines = input_str.split("\n")
n, x, y = map(int, input_lines[0].split())
a = list(map(int, input_lines[1].split()))
# 確認用コード
return [n, x, y, a]
# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > [10, 2, 7, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]
# > [8, 1, 3, [1, 3, 8, 3, 1, 8, 8, 1]]
データが正しく受け取れていれば、問題を解く処理を書いていきます。
まずはインデックスを使って累積和を求めます。
def solve(input_str):
# 入力
input_lines = input_str.split("\n")
n, x, y = map(int, input_lines[0].split())
a = list(map(int, input_lines[1].split()))
# 累積和
s = [0] * (n + 1)
for i in range(n):
s[i + 1] = s[i] + a[i]
# 確認用コード
return s
# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
# > [0, 1, 4, 12, 15, 16, 24, 32, 33]
累積和が正しく計算出来ているので、累積和s, 左端x, 右端y を使って区間和を求めるコードを追加します。
def solve(input_str):
# 入力
input_lines = input_str.split("\n")
n, x, y = map(int, input_lines[0].split())
a = list(map(int, input_lines[1].split()))
# 累積和
s = [0] * (n + 1)
for i in range(n):
s[i + 1] = s[i] + a[i]
# a[x] から a[y] までの区間和を返す
return s[y + 1] - s[x]
# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > 33
# > 14
INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。
Python 解答コード
def solve(input_str):
# 入力
input_lines = input_str.split("\n")
n, x, y = map(int, input_lines[0].split())
a = list(map(int, input_lines[1].split()))
# 累積和
s = [0] * (n + 1)
for i in range(n):
s[i + 1] = s[i] + a[i]
# a[x] から a[y] までの区間和を返す
return s[y + 1] - s[x]
print(solve(open(0).read()))
Python 他の解答例
省略できる箇所を省略してみます。
- 入力を一括で受け取る
- インデックスを使わず累積を求める
def solve(input_str):
# 入力
_, x, y, *a = map(int, input_str.split())
# 累積和
s = [0]
for num in a:
s.append(s[-1] + num)
# a[x] から a[y] までの区間和を返す
return s[y + 1] - s[x]
print(solve(open(0).read()))
今回のまとめ
- 数列の累積和を計算しておくと、任意の区間の和が1回の引き算で求めることが出来る。
セクション1では区間和の求め方を学習しました！
半開区間の考え方が最初は戸惑いますが、何度か見るうちにだんだん慣れてきますﾖ(*'ω'*)
