今回はpaiza 累積和メニューセクショ3【区間内の個数】を解説します。
n個の整数の要素からなる配列aがあり、任意の区間内の偶数の数はいくつか？を出力する問題です。
本記事で使用しているアルゴリズムやメソッドについて
解答例で使っているアルゴリズムやメソッドについて、下記の記事で詳しく解説していますので参考にしてみて下さい。
- [アルゴリズム(Ruby)]累積和
- [アルゴリズム(Ruby)]線形探索法
- [Ruby] 標準入力によるデータ取得1
- [Ruby] 標準入力によるデータ取得2
- [Ruby] 標準入力によるデータ取得3
- [Ruby] 標準出力（データを任意に整形して出力する）
- [Ruby]配列の基本操作1
- [Ruby]繰り返し処理
- [Ruby]条件分岐
- [Ruby]繰り返し処理
累積和メニュー3：【区間内の個数】
3-STEP1: 区間内の個数 1 (paizaランク C 相当)
a[0]からa[9]まで10個の整数を要素に持つ配列 a=[1, 5, 9, 7, 5, 3, 2, 5, 8, 4] で、a[2]からa[7]の区間内に偶数がいくつあるかを出力する問題です。
a[0] から a[7] までの偶数の数 = b[0] + b[1] + b[2] + b[3] + b[4] + b[5] + b[6] + b[7] = s[8] = 1
a[0] から a[1] までの偶数の数 = b[0] + b[1] = s[2] = 0
a[2] から a[7] までの偶数の数 = s[8] - s[2] = 1 - 0 = 1
Ruby解答例1-1
空の 配列b を用意し、配列a の先頭から順に数字を調べ、配列b の末尾に 偶数なら1、奇数なら0を追加します。
次に 配列b の 累積和s を求め、a[2] から a[7] までの区間の偶数を s[7+1] - s[2] で求めます。
# 入力
l = 2
r = 7
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
# 偶数: 1, 奇数: 0
b = []
a.each do |num|
if num % 2 == 0
b << 1
else
b << 0
end
end
# 累積和
s = [0]
b.each { |num| s << s[-1] + num }
# 区間の偶数の数
even_count = s[r + 1] - s[l]
puts even_count
Ruby解答例1-2
Ruby解答例1-1の
- if文を三項演算子に変更
- 偶数判定
num%2==0の部分をeven?メソッドnum.even?に変更 - 空配列b=[] を用意して要素を追加した部分をmapに変更
これでコードがスッキリします。今後はこのコードをベースに実装していきます。
# 入力
l = 2
r = 7
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
# 偶数: 1, 奇数: 0
b = a.map { |num| num.even? ? 1 : 0 }
# 累積和
s = [0]
b.each { |num| s << s[-1] + num }
# 区間の偶数の数
even_count = s[r + 1] - s[l]
puts even_count
Ruby解答例2
偶数の 配列b を作らずに 配列a から直接偶数の 累積和s を作ります。
# 入力
l = 2
r = 7
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
# 累積和 (偶数: 1, 奇数: 0)
s = [0]
a.each { |num| s << s[-1] + (num.even? ? 1 : 0) }
# 区間の偶数の数
even_count = s[r + 1] - s[l]
puts even_count
Python解答例1-1
空の 配列b を用意し、配列a の先頭から順に数字を調べ、配列b の末尾に偶数なら1、奇数なら0を追加します。
次に 配列b の 累積和s を求め、a[2] から a[7] までの区間の偶数を s[7+1] - s[2] で求めます。
# 入力
l = 2
r = 7
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
# 偶数: 1, 奇数: 0
b = []
for num in a:
if num % 2 == 0:
b.append(1)
else:
b.append(0)
# 累積和
s = [0]
for num in b:
s.append(s[-1] + num)
# 区間の偶数の数
even_count = s[r + 1] - s[l]
print(even_count)
Python解答例1-2
Python解答例1-1の
- if文を三項演算子に変更
- 空配列b=[] を用意して要素を追加した部分をリスト内包表記に変更
次のステップからPython解答例はこのコードをベースに実装します。
# 入力
l = 2
r = 7
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
# 偶数: 1, 奇数: 0
b = [1 if num % 2 == 0 else 0 for num in a]
# 累積和
s = [0]
for num in b:
s.append(s[-1] + num)
# 区間の偶数の数
even_count = s[r + 1] - s[l]
print(even_count)
Python解答例2
偶数の 配列b を作らずに 配列a から直接偶数の 累積和s を作ります。
# 入力
l = 2
r = 7
a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
# 累積和 (偶数: 1, 奇数: 0)
s = [0]
for num in a:
s.append(s[-1] + (1 if num % 2 == 0 else 0))
# 区間の偶数の数
even_count = s[r + 1] - s[l]
print(even_count)
3-STEP2: 区間内の個数 2 (paizaランク C 相当)
a[0]からa[9]まで10個の整数を要素に持つ配列 a が 半角スペース区切りで与えられ、a[2]からa[7]の区間内に偶数がいくつあるかを出力する問題です。
与えられる条件は以下の通りです。
- 1 ≦ a_i ≦ 100 (0 ≦ i ≦ 9)
入出力例
INPUT1の例
a[2] から a[7] の区間 [3, 4, 5, 6, 7, 8]に偶数は 3個 なので 3 を出力
INPUT2の例
a[2] から a[7] の区間 [7, 8, 9, 6, 3, 1] に偶数は 2個 なので 2 を出力
INPUT1 = <<"EOS" 1 2 3 4 5 6 7 8 9 10 EOS OUTPUT1 = <<"EOS" 3 EOS INPUT2 = <<"EOS" 1 4 7 8 9 6 3 1 5 8 EOS OUTPUT2 = <<"EOS" 2 EOS
Ruby解答例1
配列aの要素を受け取る処理を追加します。あとはSTEP1-Ruby解答例1-2と同じです。
# 入力
l = 2
r = 7
a = gets.split.map(&:to_i)
# 偶数: 1, 奇数: 0
b = a.map { |num| num.even? ? 1 : 0 }
# 累積和
s = [0]
b.each { |num| s << s[-1] + num }
# 区間の偶数の数
even_count = s[r + 1] - s[l]
puts even_count
Ruby解答例2
配列aの要素を受け取る処理を追加します。あとはSTEP1-Ruby解答例2と同じです。
# 入力
l = 2
r = 7
a = gets.split.map(&:to_i)
# 累積和 (偶数: 1, 奇数: 0)
s = [0]
a.each { |num| s << s[-1] + (num.even? ? 1 : 0) }
# 区間の偶数の数
even_count = s[r + 1] - s[l]
puts even_count
Python解答例1
配列aの要素を受け取る処理を追加します。あとはSTEP1-Python解答例1-2と同じです。
# 入力
l = 2
r = 7
a = list(map(int, input().split()))
# 偶数: 1, 奇数: 0
b = [1 if num % 2 == 0 else 0 for num in a]
# 累積和
s = [0]
for num in b:
s.append(s[-1] + num)
# 区間の偶数の数
even_count = s[r + 1] - s[l]
print(even_count)
Python解答例2
配列aの要素を受け取る処理を追加します。あとはSTEP1-Python解答例2と同じです。
# 入力
l = 2
r = 7
a = list(map(int, input().split()))
# 累積和 (偶数: 1, 奇数: 0)
s = [0]
for num in a:
s.append(s[-1] + (1 if num % 2 == 0 else 0))
# 区間の偶数の数
even_count = s[r + 1] - s[l]
print(even_count)
3-STEP3: 区間内の個数 3 (paizaランク C 相当)
1行目で区間x, y、2行目で10個の整数 a[0], a[1] ... a[9] が半角スペース区切りで与えられ、a[x] から a[y]の区間内に偶数がいくつあるかを出力する問題です。
与えられる条件は以下の通りです。
- 0 ≦ x ≦ y ≦ 9
- 1 ≦ a_i ≦ 100 (0 ≦ i ≦ 9)
入出力例
INPUT1の例
a[2] から a[7] の区間 [3, 4, 5, 6, 7, 8]に偶数は 3個 なので 3 を出力
INPUT2の例
a[1] から a[6] の区間 [6, 9, 8, 8, 4, 1]に偶数は 4個 なので 4 を出力
INPUT1 = <<"EOS" 2 7 1 2 3 4 5 6 7 8 9 10 EOS OUTPUT1 = <<"EOS" 3 EOS INPUT2 = <<"EOS" 1 6 3 6 9 8 8 4 1 2 3 5 EOS OUTPUT2 = <<"EOS" 4 EOS
Ruby解答例1
入力1行目から x, y、2行目から配列aの値を受け取ります。あとはSTEP2-Ruby解答例1と同じです。
# 入力
x, y = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
# 偶数: 1, 奇数: 0
b = a.map { |num| num.even? ? 1 : 0 }
# 累積和
s = [0]
b.each { |num| s << s[-1] + num }
# 区間の偶数の数
even_count = s[y + 1] - s[x]
puts even_count
Ruby解答例2
$stdin.read で入力を一括で受け取り、多重代入しています。あとはSTEP2-解答例2と同じです。（入力終了は ctrl+d）
# 入力
x, y, *a = $stdin.read.split.map(&:to_i)
# 累積和 (偶数: 1, 奇数: 0)
s = [0]
a.each { |num| s << s[-1] + (num.even? ? 1 : 0) }
# 区間の偶数の数
even_count = s[y + 1] - s[x]
puts even_count
Python解答例1
入力1行目から x, y、2行目から配列aの値を受け取ります。あとはSTEP2-Python解答例1と同じです。
# 入力
x, y = map(int, input().split())
a = list(map(int, input().split()))
# 偶数: 1, 奇数: 0
b = [1 if num % 2 == 0 else 0 for num in a]
# 累積和
s = [0]
for num in b:
s.append(s[-1] + num)
# 区間の偶数の数
even_count = s[y + 1] - s[x]
print(even_count)
Python解答例2
open(0).read() で入力を一括で受け取り、多重代入しています。あとはSTEP2-解答例2と同じです。（入力終了は ctrl+d）
# 入力
x, y, *a = map(int, open(0).read().split())
# 累積和 (偶数: 1, 奇数: 0)
s = [0]
for num in a:
s.append(s[-1] + (1 if num % 2 == 0 else 0))
# 区間の偶数の数
even_count = s[y + 1] - s[x]
print(even_count)
3-FINAL: 【区間内の個数】区間内の個数 4 (paizaランク C 相当)
問題
1 行目に整数 N, X, Y が与えられます。
2 行目に N 個の整数 a_0, a_1, a_2, ..., a_(N-1) が与えられます。
この数列の a_X から a_Y までの偶数の個数を、累積和を使うことで求め、一行で出力してください。
入力される値
- 1 行目に整数 N, X, Y が与えられます。
- 2 行目に 10 個の整数 a_0, a_1, a_2, ..., a_(N-1) が与えられます。
N X Y
a_0 a_1 a_2 ... a_(N-1)
入力値最終行の末尾に改行が１つ入ります。
期待する出力
数列の a_X から a_Y までの偶数の個数を、累積和を使うことで求め、一行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
条件
すべてのテストケースにおいて、以下の条件をみたします。
- 0 ≦ 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
- 3
- 入力例2
- 8 1 3
1 3 8 3 1 8 8 1
- 出力例2
- 1
攻略ポイント
ポイント
Ruby 問題を解く流れ
入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。
INPUT1 = <<"EOS" 10 2 7 1 2 3 4 5 6 7 8 9 10 EOS OUTPUT1 = <<"EOS" 3 EOS INPUT2 = <<"EOS" 8 1 3 1 3 8 3 1 8 8 1 EOS OUTPUT2 = <<"EOS" 1 EOS # 確認用コード p INPUT1 p OUTPUT1 p INPUT2 p OUTPUT2 # 実行結果 # > "10 2 7\n1 2 3 4 5 6 7 8 9 10\n" # > "3\n" # > "8 1 3\n1 3 8 3 1 8 8 1\n" # > "1\n"
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。
まず、入力データを受け取る処理を書きます。
def solve(input_str)
input_lines = input_str.split("\n")
_, x, y = input_lines[0].split.map(&:to_i)
a = input_lines[1].split.map(&:to_i)
# 確認用コード
[x, y, a]
end
# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > [2, 7, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]
# > [1, 3, [1, 3, 8, 3, 1, 8, 8, 1]]
データが正しく受け取れていれば、問題を解く処理を書いていきます。
配列aの要素が偶数なら1、奇数なら0に変換した配列bを作ります。
def solve(input_str)
# 入力
input_lines = input_str.split("\n")
_, x, y = input_lines[0].split.map(&:to_i)
a = input_lines[1].split.map(&:to_i)
# 偶数: 1, 奇数: 0
b = a.map { |num| num.even? ? 1 : 0 }
# 確認用コード
[a, b]
end
# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]]
# > [[1, 3, 8, 3, 1, 8, 8, 1], [0, 0, 1, 0, 0, 1, 1, 0]]
配列bの累積和sを求め、 s[y+1] - s[x] で a[x] から a[y] の区間内の偶数の数を求めます。
def solve(input_str)
# 入力
input_lines = input_str.split("\n")
_, x, y = input_lines[0].split.map(&:to_i)
a = input_lines[1].split.map(&:to_i)
# 偶数: 1, 奇数: 0
b = a.map { |num| num.even? ? 1 : 0 }
# 累積和
s = [0]
b.each { |num| s << s[-1] + num }
# a[x] ~ a[y] 区間の偶数の数を返す
s[y + 1] - s[x]
end
# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > 3
# > 1
INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。
Ruby 解答コード
def solve(input_str)
# 入力
input_lines = input_str.split("\n")
_, x, y = input_lines[0].split.map(&:to_i)
a = input_lines[1].split.map(&:to_i)
# 偶数: 1, 奇数: 0
b = a.map { |num| num.even? ? 1 : 0 }
# 累積和
s = [0]
b.each { |num| s << s[-1] + num }
# a[x] ~ a[y] 区間の偶数の数を返す
s[y + 1] - s[x]
end
puts solve($stdin.read)
Ruby 他の解答例
STEP1～3の解答例2に倣った書き方です。
def solve(input_str)
# 入力
_, x, y, *a = input_str.split.map(&:to_i)
# 累積和 (偶数: 1, 奇数: 0)
s = [0]
a.each { |num| s << s[-1] + (num.even? ? 1 : 0) }
# 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 = """\ 3 """ INPUT2 = """\ 8 1 3 1 3 8 3 1 8 8 1 """ OUTPUT2 = """\ 1 """ # 確認用コード 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' # > '3\n' # > '8 1 3\n1 3 8 3 1 8 8 1\n' # > '1\n'
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。
まず、入力データを受け取る処理を書きます。
def solve(input_str):
input_lines = input_str.split("\n")
_, x, y = map(int, input_lines[0].split())
a = list(map(int, input_lines[1].split()))
# 確認用コード
return [x, y, a]
# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > [2, 7, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]
# > [1, 3, [1, 3, 8, 3, 1, 8, 8, 1]]
データが正しく受け取れていれば、問題を解く処理を書いていきます。
配列aの要素が偶数なら1、奇数なら0に変換した配列bを作ります。
def solve(input_str):
# 入力
input_lines = input_str.split("\n")
_, x, y = map(int, input_lines[0].split())
a = list(map(int, input_lines[1].split()))
# 偶数: 1, 奇数: 0
b = [1 if num % 2 == 0 else 0 for num in a]
# 確認用コード
return [a, b]
# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]]
# > [[1, 3, 8, 3, 1, 8, 8, 1], [0, 0, 1, 0, 0, 1, 1, 0]]
配列bの累積和sを求め、 s[y+1] - s[x] で a[x] から a[y] の区間内の偶数の数を求めます。
def solve(input_str):
# 入力
input_lines = input_str.split("\n")
_, x, y = map(int, input_lines[0].split())
a = list(map(int, input_lines[1].split()))
# 偶数: 1, 奇数: 0
b = [1 if num % 2 == 0 else 0 for num in a]
# 累積和
s = [0]
for num in b:
s.append(s[-1] + num)
# a[x] ~ a[y] 区間の偶数の数を返す
return s[y + 1] - s[x]
# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > 3
# > 1
INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。
Python 解答コード
def solve(input_str):
# 入力
input_lines = input_str.split("\n")
_, x, y = map(int, input_lines[0].split())
a = list(map(int, input_lines[1].split()))
# 偶数: 1, 奇数: 0
b = [1 if num % 2 == 0 else 0 for num in a]
# 累積和
s = [0]
for num in b:
s.append(s[-1] + num)
# a[x] ~ a[y] 区間の偶数の数を返す
return s[y + 1] - s[x]
print(solve(open(0).read()))
Python 他の解答例
STEP1～3の解答例2に倣った書き方です。
def solve(input_str):
# 入力
_, x, y, *a = map(int, input_str.split())
# 累積和 (偶数: 1, 奇数: 0)
s = [0]
for num in a:
s.append(s[-1] + (1 if num % 2 == 0 else 0))
# a[x] ~ a[y] 区間の偶数の数を返す
return s[y + 1] - s[x]
print(solve(open(0).read()))
今回のまとめ
累積和を使って、配列の任意の区間の条件を満たす要素の数を求めることが出来ました。
