[Ruby|Python]paiza 累積和メニュー1 【区間の和】

2023-10-14

今回はpaiza 累積和メニューセクション1【区間の和】を解説します。

セクション1は、累積和から区間和を求める問題です。

本記事で使用しているアルゴリズムやメソッドについて
セクション1：【区間の和】
今回のまとめ

本記事で使用しているアルゴリズムやメソッドについて

解答例で使っているアルゴリズムやメソッドについて、下記の記事で詳しく解説していますので参考にしてみて下さい。

セクション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)]累積和

メソッドの定義と呼び出し

[Ruby]メソッドの定義と呼び出し

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では区間和の求め方を学習しました！
半開区間の考え方が最初は戸惑いますが、何度か見るうちにだんだん慣れてきますﾖ(*'ω'*)

【PR】アルゴリズム学習でお世話になった本

アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。

通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [ 渡部有隆 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。

プログラミングコンテストチャレンジブック第2版問題解決のアルゴリズム活用力とコーディングテクニッ [ 秋葉拓哉 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者～中級者向けに書かれているので解説が非常に丁寧です。

最強最速アルゴリズマー養成講座プログラミングコンテストTopCoder攻略ガイド【電子書籍】[ 高橋直大 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。

Pythonで体験してわかるアルゴリズムとデータ構造 [ 西澤弘毅 ]

posted with カエレバ

comment

: Ruby プログラミング

[Ruby] 標準入力からのデータ取得3

こんにちは！じゃいごテックのあつしです。今回は多重代入と、shift・unshift・pop・pushメソッドを紹介します。目次多重代入shift・unshiftpop・pushpaiza練習問題 ...

: paiza プログラミング

[Ruby|Python]paiza 標準出力メニュー【n * n の 2 次元配列の表示】

今回はpaiza 標準入力メニューセクション6【n * n の 2 次元配列の表示】を解説します。セクション6は、任意の二次元配列を生成し、出力する問題です。目次本記事で使用しているメソッドについ ...

: paiza プログラミング

[Ruby|Python]paiza 標準入力メニューセクション4～6（整数）

今回はpaiza 標準入力メニューセクション4～6（整数値の入力）を解説します。セクション4は、複数行の入力データを整数値で受け取る問題です。セクション5は、半角スペース区切りの入力データがあった ...

: paiza プログラミング

[Ruby]paiza Bランクレベルアップメニューアルファベット探し (paizaランク C 相当)の解説

こんにちは！じゃいごテックのあつしです。今回はpaiza Bランクレベルアップメニューからアルファベット探しという問題を解説します。この問題集は文字列に関する3個のSTEP問題(D級)とFINA ...

: アルゴリズム・データ構造プログラミング

[アルゴリズム(Ruby)]分割統治法・動的計画法（マージソート・フィボナッチ数・部分和問題を例に解説）

こんにちは！じゃいごテックのあつしです。今回は複雑な問題を解く際に用いられるアルゴリズム、分割統治法(divide and conquer)と、動的計画法(dynamic programming)を ...

PREV: [Ruby|Python]paiza paizaの森練習問題コンテスト過去問題6
NEXT: [Ruby|Python]paiza 累積和メニュー2 【連続するN個の和の最大値】

[Ruby|Python]paiza 累積和メニュー1 【区間の和】

本記事で使用しているアルゴリズムやメソッドについて

セクション1：【区間の和】

1-STEP1: 区間の和 1 (paizaランク C 相当)

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

1-STEP2: 区間の和 2 (paizaランク C 相当)

入出力例

Ruby解答例

Python解答例

1-STEP3: 区間の和 3 (paizaランク C 相当)

入出力例

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

1-FINAL: 【区間の和】 区間の和 4 (paizaランク C 相当)

問題

攻略ポイント

Ruby 問題を解く流れ

Ruby 解答コード

Ruby 他の解答例

Python 問題を解く流れ

Python 解答コード

Python 他の解答例

今回のまとめ

【PR】アルゴリズム学習でお世話になった本

1-FINAL: 【区間の和】区間の和 4 (paizaランク C 相当)