[Ruby|Python]paiza 累積和メニュー5 【二次元累積和】

2023-10-24

今回はpaiza 累積和メニューセクショ5【二次元累積和】を解説します。

整数の要素をもつ、h行 w列の二次元配列aの、左上の要素をa[sy][sx], 右下の要素をa[gy][gx]としたときに出来る長方形の区間和を出力する問題です。

本記事で使用しているアルゴリズムやメソッドについて
累積和メニュー5：【二次元累積和】
今回のまとめ

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

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

累積和メニュー5：【二次元累積和】

5-STEP1: 二次元累積和 1 (paizaランク C 相当)

整数の要素をもつ、5行 5列の二次元配列aの、左上の要素をa[1][1], 右下の要素をa[3][3]としたときに出来る長方形の区間和を出力する問題です。

※ STEP1～STEP7(BOSS2) まで問題がありますが、最初から最後までほぼ同じ解答コードが続きます💦

Ruby解答例

5行5列の二次元配列a の 累積和s を求め、左上がa[1][1], 右上がa[3][3]の長方形の区間和を s[4][4] - s[1][4]-s[4][1] + s[1][1] で求めます。

# 入力
sy, sx = 1, 1
gy, gx = 3, 3
h, w = 5, 5
a = [
  [1, 2, 3, 4, 5],
  [2, 3, 4, 5, 6],
  [3, 4, 5, 6, 7],
  [4, 5, 6, 7, 8],
  [5, 6, 7, 8, 9],
]

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Python解答例

5行5列の二次元配列a の 累積和s を求め、左上がa[1][1], 右上がa[3][3]の長方形の区間和を s[4][4] - s[1][4]-s[4][1] + s[1][1] で求めます。

# 入力
sy, sx = 1, 1
gy, gx = 3, 3
h, w = 5, 5
a = [
    [1, 2, 3, 4, 5],
    [2, 3, 4, 5, 6],
    [3, 4, 5, 6, 7],
    [4, 5, 6, 7, 8],
    [5, 6, 7, 8, 9],
]

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

5-STEP2: 二次元累積和 2 (paizaランク C 相当)

整数の要素をもつ、5行 5列の二次元配列aの要素が5行で与えられ、左上の要素をa[1][1], 右下の要素をa[3][3]としたときに出来る長方形の区間和を出力する問題です。

入出力例

INPUT1の例
左上がa[1][1], 右下がa[3][3] の長方形の要素は、[[3, 4, 5], [4, 5, 6], [5, 6, 7]] なので区間和 45 を出力する

INPUT1 = <<"EOS"
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
EOS
OUTPUT1 = <<"EOS"
45
EOS

Ruby解答例1

入力を gets で受け取ります。あとはSTEP1-Ruby解答例と同じです。

# 入力
sy, sx = 1, 1
gy, gx = 3, 3
h, w = 5, 5
a = []
h.times { a << gets.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Ruby解答例2

入力を $stdin.read で受け取ります。あとはSTEP1-Ruby解答例と同じです。

# 入力
sy, sx = 1, 1
gy, gx = 3, 3
h, w = 5, 5
a = $stdin.read.split("\n").map { |l| l.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Python解答例1

入力を input() で受け取ります。あとはSTEP1-Python解答例と同じです。

# 入力
sy, sx = 1, 1
gy, gx = 3, 3
h, w = 5, 5
a = []
for _ in range(h):
    a.append(list(map(int, input().split())))

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

Python解答例2

入力を open(0).read() で受け取ります。あとはSTEP1-Python解答例と同じです。

# 入力
sy, sx = 1, 1
gy, gx = 3, 3
h, w = 5, 5
a = [list(map(int, l.split())) for l in open(0).read().rstrip().split("\n")]

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

5-STEP3: 二次元累積和 3 (paizaランク C 相当)

1行目で sy, gy (問題文では a, b となっていますが sy, gy とします) 、続く5行で整数の要素をもつ、5行 5列の二次元配列aの要素が与えられ、左上の要素をa[sy][3], 右下の要素をa[gy][3]としたときに出来る長方形の区間和を出力する問題です。

与えられる条件は以下の通りです。

0 ≦ sy ≦ gy ≦ 4
1 ≦ a_{i, j} ≦ 100 (0 ≦ i ≦ 4, 0 ≦ j ≦ 4)

入出力例

INPUT1の例
左上がa[1][3], 右下がa[3][3] の長方形の要素は、[[5], [6], [7]] なので区間和 18 を出力する

INPUT2の例
左上がa[1][3], 右下がa[3][3] の長方形の要素は、[[1], [3], [8]] なので区間和 12 を出力する

INPUT1 = <<"EOS"
1 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
EOS
OUTPUT1 = <<"EOS"
18
EOS

INPUT2 = <<"EOS"
1 3
8 1 3 8 1
1 3 8 1 3
3 8 1 3 8
8 1 3 8 1
1 3 8 1 3
EOS
OUTPUT2 = <<"EOS"
12
EOS

Ruby解答例1

入力を gets で受け取ります。あとはSTEP2-Ruby解答例1と同じです。

# 入力
sx, gx = 3, 3
h, w = 5, 5
sy, gy = gets.split.map(&:to_i)
a = []
h.times { a << gets.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Ruby解答例2

入力を $stdin.read で受け取ります。あとはSTEP2-Ruby解答例2と同じです。

# 入力
sx, gx = 3, 3
h, w = 5, 5
input_lines = $stdin.read.split("\n")
sy, gy = input_lines.shift.split.map(&:to_i)
a = input_lines.map { |l| l.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Python解答例1

入力を input() で受け取ります。あとはSTEP2-Python解答例1と同じです。

# 入力
sx, gx = 3, 3
h, w = 5, 5
sy, gy = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(map(int, input().split())))

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

Python解答例2

入力を open(0).read() で受け取ります。あとはSTEP2-Python解答例2と同じです。

# 入力
sx, gx = 3, 3
h, w = 5, 5
input_lines = open(0).read().rstrip().split("\n")
sy, gy = map(int, input_lines[0].split())
a = [list(map(int, l.split())) for l in input_lines[1:]]

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

5-STEP4: 二次元累積和 4 (paizaランク C 相当)

1行目で sy, sx, gy, gx (問題文では a, b, c, d となっていますが sy, sx, gy, gx とします) 、続く5行で整数の要素をもつ、5行 5列の二次元配列aの要素が与えられ、左上の要素をa[sy][sx], 右下の要素をa[gy][gx]としたときに出来る長方形の区間和を出力する問題です。

与えられる条件は以下の通りです。

0 ≦ sy ≦ gy ≦ 4
0 ≦ sx ≦ gx ≦ 4
1 ≦ a_{i, j} ≦ 100 (0 ≦ i ≦ 4, 0 ≦ j ≦ 4)

入出力例

INPUT1の例
左上がa[1][1], 右下がa[3][3] の長方形の要素は、[[3, 4, 5], [4, 5, 6], [5, 6, 7]] なので区間和 48 を出力する

INPUT2の例
左上がa[0][0], 右下がa[4][4] の長方形の要素は、[[8, 1, 3, 8, 1], [1, 3, 8, 1, 3], [3, 8, 1, 3, 8], [8, 1, 3, 8, 1], [1, 3, 8, 1, 3]] なので区間和 97 を出力する

INPUT1 = <<"EOS"
1 1 3 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
EOS
OUTPUT1 = <<"EOS"
45
EOS

INPUT2 = <<"EOS"
0 0 4 4
8 1 3 8 1
1 3 8 1 3
3 8 1 3 8
8 1 3 8 1
1 3 8 1 3
EOS
OUTPUT2 = <<"EOS"
97
EOS

Ruby解答例1

入力を gets で受け取ります。あとはSTEP3-Ruby解答例1と同じです。

# 入力
h, w = 5, 5
sy, sx, gy, gx = gets.split.map(&:to_i)
a = []
h.times { a << gets.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Ruby解答例2

入力を $stdin.read で受け取ります。あとはSTEP3-Ruby解答例2と同じです。

# 入力
h, w = 5, 5
input_lines = $stdin.read.split("\n")
sy, sx, gy, gx = input_lines.shift.split.map(&:to_i)
a = input_lines.map { |l| l.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Python解答例1

入力を input() で受け取ります。あとはSTEP3-Python解答例1と同じです。

# 入力
h, w = 5, 5
sy, sx, gy, gx = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(map(int, input().split())))

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

Python解答例2

入力を open(0).read() で受け取ります。あとはSTEP3-Python解答例2と同じです。

# 入力
h, w = 5, 5
input_lines = open(0).read().rstrip().split("\n")
sy, sx, gy, gx = map(int, input_lines[0].split())
a = [list(map(int, l.split())) for l in input_lines[1:]]

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

5-STEP5: 二次元累積和 5 (paizaランク C 相当)

1行目で整数n、2行目で sy, sx, gy, gx (問題文では a, b, c, d となっていますが sy, sx, gy, gx とします) 、続くn行で整数の要素をもつ、n行 n列の二次元配列aの要素が与えられ、左上の要素をa[sy][sx], 右下の要素をa[gy][gx]としたときに出来る長方形の区間和を出力する問題です。

与えられる条件は以下の通りです。

2 ≦ n ≦ 10
0 ≦ sy ≦ gy ≦ n - 1
0 ≦ sx ≦ gx ≦ n - 1
1 ≦ a_{i, j} ≦ 100 (0 ≦ i ≦ 4, 0 ≦ j ≦ 4)

入出力例

INPUT1の例
左上がa[1][1], 右下がa[3][3] の長方形の要素は、[[3, 4, 5], [4, 5, 6], [5, 6, 7]] なので区間和 45 を出力する

INPUT2の例
左上がa[0][0], 右下がa[5][5] の長方形の要素は、
[[8, 1, 3, 8, 1, 3],[1, 3, 8, 1, 3, 8], [3, 8, 1, 3, 8, 1], [8, 1, 3, 8, 1, 3], [1, 3, 8, 1, 3, 8], [3, 8, 1, 3, 8, 1]] なので区間和 144 を出力する

INPUT1 = <<"EOS"
5
1 1 3 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
EOS
OUTPUT1 = <<"EOS"
45
EOS

INPUT2 = <<"EOS"
6
0 0 5 5
8 1 3 8 1 3
1 3 8 1 3 8
3 8 1 3 8 1
8 1 3 8 1 3
1 3 8 1 3 8
3 8 1 3 8 1
EOS
OUTPUT2 = <<"EOS"
144
EOS

Ruby解答例1

入力を gets で受け取ります。あとはSTEP4-Ruby解答例1と同じです。

# 入力
h = w = gets.to_i
sy, sx, gy, gx = gets.split.map(&:to_i)
a = []
h.times { a << gets.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Ruby解答例2

入力を $stdin.read で受け取ります。あとはSTEP4-Ruby解答例2と同じです。

# 入力
input_lines = $stdin.read.split("\n")
h = w = input_lines.shift.to_i
sy, sx, gy, gx = input_lines.shift.split.map(&:to_i)
a = input_lines.map { |l| l.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Python解答例1

入力を input() で受け取ります。あとはSTEP4-Python解答例1と同じです。

# 入力
h = w = int(input())
sy, sx, gy, gx = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(map(int, input().split())))

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

Python解答例2

入力を open(0).read() で受け取ります。あとはSTEP4-Python解答例2と同じです。

# 入力
input_lines = open(0).read().rstrip().split("\n")
h = w = int(input_lines[0])
sy, sx, gy, gx = map(int, input_lines[1].split())
a = [list(map(int, l.split())) for l in input_lines[2:]]

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

5-STEP6: 【二次元累積和】二次元累積和 6 (paizaランク C 相当)

1行目で整数h, w(問題文では n, m となっていますが h, w とします)、2行目で sy, sx, gy, gx (問題文では a, b, c, d となっていますが sy, sx, gy, gx とします) 、続くn行で整数の要素をもつ、h行 w列の二次元配列aの要素が与えられ、左上の要素をa[sy][sx], 右下の要素をa[gy][gx]としたときに出来る長方形の区間和を出力する問題です。

与えられる条件は以下の通りです。

2 ≦ h, w ≦ 10
0 ≦ sy ≦ gy ≦ h - 1
0 ≦ sx ≦ gx ≦ w - 1
1 ≦ a_{i, j} ≦ 100 (0 ≦ i ≦ 4, 0 ≦ j ≦ 4)

入出力例

INPUT1の例
左上がa[1][1], 右下がa[3][3] の長方形の要素は、[[3, 4, 5], [4, 5, 6], [5, 6, 7]] なので区間和 45 を出力する

INPUT2の例
左上がa[0][0], 右下がa[7][2] の長方形の要素は、
[[8, 1, 3], [1, 3, 8], [3, 1, 8], [8, 1, 3], [1, 3, 8], [3, 1, 8], [8, 1, 3], [1, 3, 8]] なので区間和 96 を出力する

INPUT1 = """\
5 5
1 1 3 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
"""
OUTPUT1 = """\
45
"""

INPUT2 = """\
8 3
0 0 7 2
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
"""
OUTPUT2 = """\
96
"""

Ruby解答例1

入力を gets で受け取ります。あとはSTEP5-Ruby解答例1と同じです。

# 入力
h, w = gets.split.map(&:to_i)
sy, sx, gy, gx = gets.split.map(&:to_i)
a = []
h.times { a << gets.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Ruby解答例2

入力を $stdin.read で受け取ります。あとはSTEP5-Ruby解答例2と同じです。

# 入力
input_lines = $stdin.read.split("\n")
h, w = input_lines.shift.split.map(&:to_i)
sy, sx, gy, gx = input_lines.shift.split.map(&:to_i)
a = input_lines.map { |l| l.split.map(&:to_i) }

# 累積和
s = Array.new(h + 1) { Array.new(w + 1, 0) }
(0...h).each do |y|
  (0...w).each do |x|
    s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
  end
end

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
puts section_sum

Python解答例1

入力を input() で受け取ります。あとはSTEP5-Python解答例1と同じです。

# 入力
h, w = map(int, input().split())
sy, sx, gy, gx = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(map(int, input().split())))

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

Python解答例2

入力を open(0).read() で受け取ります。あとはSTEP5-Python解答例2と同じです。

# 入力
input_lines = open(0).read().rstrip().split("\n")
h, w = map(int, input_lines[0].split())
sy, sx, gy, gx = map(int, input_lines[1].split())
a = [list(map(int, l.split())) for l in input_lines[2:]]

# 累積和
s = [[0] * (w + 1) for _ in range(h + 1)]
for y in range(h):
    for x in range(w):
        s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

# 長方形の区間和を出力
section_sum = s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
print(section_sum)

5-STEP7: 【二次元累積和】二次元累積和 7 (paizaランク C 相当)

問題

1 行目に整数 N, M, Q が与えられます。

2 行目以降に N 行 M 列の整数の二次元配列 A が与えられます。

2 + N 行目以降に Q 行に渡って整数 a_i, b_i, c_i, d_i (0 ≦ i ≦ Q - 1) が与えられます。

A の j 行目 k 列目を A_{j, k} (0 ≦ j ≦ N - 1, 0 ≦ k ≦ M - 1) と表すことにします。

i 番目の長方形領域の左上の要素を A_{a_i, b_i}, 右下の要素を A_{c_i, d_i} としたとき、これら Q 個の長方形領域内の整数の和を累積和を用いて求め、改行区切りで出力してください。

入力される値

1 行目に整数 N, M, Q が与えられます。
2 行目以降に N 行 M 列の整数の二次元配列 A が与えられます。
2 + N 行目以降に Q 行に渡って整数 a_i, b_i, c_i, d_i (0 ≦ i ≦ Q - 1) が与えられます。

N M Q
A_{0, 0} A_{0, 1} ... A_{0, M - 1}
A_{1, 0} A_{1, 1} ... A_{1, M - 1}
...
A_{N - 1, 0} A_{N - 1, 1} ... A_{N - 1, M - 1}
a_0 b_0 c_0 d_0
a_1 b_1 c_1 d_1
...
a_{Q - 1} b_{Q - 1} c_{Q - 1} d_{Q - 1}

入力値最終行の末尾に改行が１つ入ります。

期待する出力

末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

1 ≦ N, M, Q ≦ 10
1 ≦ A_{i, j} ≦ 100 (0 ≦ i ≦ N - 1, 0 ≦ j ≦ M - 1)
0 ≦ a_i ≦ c_i ≦ N - 1 (0 ≦ i ≦ Q - 1)
0 ≦ b_i ≦ d_i ≦ M - 1 (0 ≦ i ≦ Q - 1)

入力例1: 5 5 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
1 1 3 3
2 2 4 4
0 0 2 2

出力例1: 45
63
27

入力例2: 8 3 1
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
0 0 7 2

出力例2: 96

攻略ポイント

ポイント

累積和

[アルゴリズム(Ruby)]累積和

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

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

Ruby 問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = <<"EOS"
5 5 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
1 1 3 3
2 2 4 4
0 0 2 2
EOS
OUTPUT1 = <<"EOS"
45
63
27
EOS

INPUT2 = <<"EOS"
8 3 1
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
0 0 7 2
EOS
OUTPUT2 = <<"EOS"
96
EOS

# 確認用コード
p INPUT1
p OUTPUT1
p INPUT2
p OUTPUT2
# 実行結果
# > "5 5 3\n1 2 3 4 5\n2 3 4 5 6\n3 4 5 6 7\n4 5 6 7 8\n5 6 7 8 9\n1 1 3 3\n2 2 4 4\n0 0 2 2\n"
# > "45\n63\n27\n"
# > "8 3 1\n8 1 3\n1 3 8\n3 1 8\n8 1 3\n1 3 8\n3 1 8\n8 1 3\n1 3 8\n0 0 7 2\n"
# > "96\n"

続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。

まず、入力データを受け取る処理を書きます。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  h, w, q = input_lines[0].split.map(&:to_i)
  a = []
  input_lines[1..h].each { |l| a << l.split.map(&:to_i) }
  rects = []
  input_lines[(h + 1)..].each { |l| rects << l.split.map(&:to_i) }

  # 確認用コード
  [h, w, q, a, rects]
end

# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > [5, 5, 3, [[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8], [5, 6, 7, 8, 9]], [[1, 1, 3, 3], [2, 2, 4, 4], [0, 0, 2, 2]]]
# > [8, 3, 1, [[8, 1, 3], [1, 3, 8], [3, 1, 8], [8, 1, 3], [1, 3, 8], [3, 1, 8], [8, 1, 3], [1, 3, 8]], [[0, 0, 7, 2]]]

データが正しく受け取れていれば、問題を解く処理を書いていきます。

二次元配列aの累積和sを求め、rects に格納されている sy, sx, gy, gx の情報から区間和を計算し、配列 results に格納します。

最後に、格納された区間和を改行で連結して返します。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  h, w, q = input_lines[0].split.map(&:to_i)
  a = []
  input_lines[1..h].each { |l| a << l.split.map(&:to_i) }
  rects = []
  input_lines[(h + 1)..].each { |l| rects << l.split.map(&:to_i) }

  # 累積和
  s = Array.new(h + 1) { Array.new(w + 1, 0) }
  (0...h).each do |y|
    (0...w).each do |x|
      s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
    end
  end

  # 長方形の区間和
  results = []
  rects.each do |sy, sx, gy, gx|
    results << s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
  end

  # 長方形の区間和を改行で連結した文字列を返す
  results.join("\n")
end

# 確認用コード
p solve(INPUT1)
p solve(INPUT2)
# 実行結果
# > "45\n63\n27"
# > "96"

INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。

Ruby 解答コード

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  h, w, q = input_lines[0].split.map(&:to_i)
  a = []
  input_lines[1..h].each { |l| a << l.split.map(&:to_i) }
  rects = []
  input_lines[(h + 1)..].each { |l| rects << l.split.map(&:to_i) }

  # 累積和
  s = Array.new(h + 1) { Array.new(w + 1, 0) }
  (0...h).each do |y|
    (0...w).each do |x|
      s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
    end
  end

  # 長方形の区間和
  results = []
  rects.each do |sy, sx, gy, gx|
    results << s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx]
  end

  # 長方形の区間和を改行で連結した文字列を返す
  results.join("\n")
end

puts solve($stdin.read)

Ruby 他の解答例

STEP1～6の解答例2に倣った書き方です。
また、Rubyのリストはキュー(Queue)のように使うことが出来るので入力文字列を改行で分割した input_lines から shift メソッドで任意の行数を取り出すことが出来ます。

def solve(input_str)
  # 入力
  input_lines = input_str.split("\n")
  h, w, q = input_lines.shift.split.map(&:to_i)
  a = input_lines.shift(h).map { |l| l.split.map(&:to_i) }
  rects = input_lines.shift(q).map { |l| l.split.map(&:to_i) }

  # 累積和
  s = Array.new(h + 1) { Array.new(w + 1, 0) }
  (0...h).each do |y|
    (0...w).each do |x|
      s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]
    end
  end

  # 長方形の区間和を改行で連結した文字列を返す
  rects.map { |sy, sx, gy, gx| s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx] }.join("\n")
end

puts solve($stdin.read)

Python 問題を解く流れ

入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。

INPUT1 = """\
5 5 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
1 1 3 3
2 2 4 4
0 0 2 2
"""
OUTPUT1 = """\
45
63
27
"""

INPUT2 = """\
8 3 1
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
0 0 7 2
"""
OUTPUT2 = """\
96
"""

# 確認用コード
print(repr(INPUT1))
print(repr(OUTPUT1))
print(repr(INPUT2))
print(repr(OUTPUT2))
# 実行結果
# > '5 5 3\n1 2 3 4 5\n2 3 4 5 6\n3 4 5 6 7\n4 5 6 7 8\n5 6 7 8 9\n1 1 3 3\n2 2 4 4\n0 0 2 2\n'
# > '45\n63\n27\n'
# > '8 3 1\n8 1 3\n1 3 8\n3 1 8\n8 1 3\n1 3 8\n3 1 8\n8 1 3\n1 3 8\n0 0 7 2\n'
# > '96\n'

続いて問題を解くメソッド（solveメソッドとします）を変数の下に定義します。

まず、入力データを受け取る処理を書きます。

def solve(input_str):
    # 入力
    input_lines = input_str.rstrip().split("\n")
    h, w, q = map(int, input_lines[0].split())
    a = []
    for l in input_lines[1:h+1]:
        a.append(list(map(int, l.split())))
    rects = []
    for l in input_lines[h+1:]:
        rects.append(list(map(int, l.split())))

    # 確認用コード
    return [h, w, q, a, rects]


# 確認用コード
print(solve(INPUT1))
print(solve(INPUT2))
# 実行結果
# > [5, 5, 3, [[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8], [5, 6, 7, 8, 9]], [[1, 1, 3, 3], [2, 2, 4, 4], [0, 0, 2, 2]]]
# > [8, 3, 1, [[8, 1, 3], [1, 3, 8], [3, 1, 8], [8, 1, 3], [1, 3, 8], [3, 1, 8], [8, 1, 3], [1, 3, 8]], [[0, 0, 7, 2]]]

データが正しく受け取れていれば、問題を解く処理を書いていきます。

二次元配列aの累積和sを求め、rects に格納されている sy, sx, gy, gx の情報から区間和を計算し、配列 results に格納します。

最後に、格納された区間和を改行で連結して返します。

def solve(input_str):
    # 入力
    input_lines = input_str.rstrip().split("\n")
    h, w, q = map(int, input_lines[0].split())
    a = []
    for l in input_lines[1:h+1]:
        a.append(list(map(int, l.split())))
    rects = []
    for l in input_lines[h+1:]:
        rects.append(list(map(int, l.split())))

    # 累積和
    s = [[0] * (w + 1) for _ in range(h + 1)]
    for y in range(h):
        for x in range(w):
            s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

    # 長方形の区間和
    results = []
    for sy, sx, gy, gx in rects:
        results.append(s[gy + 1][gx + 1] - s[sy]
                       [gx + 1] - s[gy + 1][sx] + s[sy][sx])

    # 長方形の区間和を改行で連結した文字列を返す
    return "\n".join(map(str, results))


# 確認用コード
print(repr(solve(INPUT1)))
print(repr(solve(INPUT2)))
# 実行結果
# > '45\n63\n27'
# > '96'

INPUT1、INPUT2共に正しく計算出来ていますので、sovleメソッド呼び出し部分を提出用に書き換え、手入力で最終確認を行います。

Python 解答コード

def solve(input_str):
    # 入力
    input_lines = input_str.rstrip().split("\n")
    h, w, q = map(int, input_lines[0].split())
    a = []
    for l in input_lines[1:h+1]:
        a.append(list(map(int, l.split())))
    rects = []
    for l in input_lines[h+1:]:
        rects.append(list(map(int, l.split())))

    # 累積和
    s = [[0] * (w + 1) for _ in range(h + 1)]
    for y in range(h):
        for x in range(w):
            s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

    # 長方形の区間和
    results = []
    for sy, sx, gy, gx in rects:
        results.append(s[gy + 1][gx + 1] - s[sy]
                       [gx + 1] - s[gy + 1][sx] + s[sy][sx])

    # 長方形の区間和を改行で連結した文字列を返す
    return "\n".join(map(str, results))


print(solve(open(0).read()))

Python 他の解答例

STEP1～6の解答例2に倣った書き方です。

def solve(input_str):
    # 入力
    input_lines = input_str.rstrip().split("\n")
    h, w, q = map(int, input_lines[0].split())
    a = [list(map(int, l.split())) for l in input_lines[1:h+1]]
    rects = [list(map(int, l.split())) for l in input_lines[-q:]]

    # 累積和
    s = [[0] * (w + 1) for _ in range(h + 1)]
    for y in range(h):
        for x in range(w):
            s[y + 1][x + 1] = a[y][x] + s[y][x + 1] + s[y + 1][x] - s[y][x]

    # 長方形の区間和を改行で連結した文字列を返す
    results = [
        s[gy + 1][gx + 1] - s[sy][gx + 1] - s[gy + 1][sx] + s[sy][sx] for sy, sx, gy, gx in rects
    ]
    return "\n".join(map(str, results))


print(solve(open(0).read()))

今回のまとめ

累積和を使って、二次元配列の任意の区間和を求めることが出来ました。

【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

: paiza プログラミング

[Ruby|Python]paiza 標準出力メニュー【半角スペース区切りの出力】

今回はpaiza 標準入力メニューセクション2【半角スペース区切りの出力】を解説します。セクション2は、指定された整数値を半角スペース区切りで出力する問題です。目次本記事で使用しているメソッドにつ ...

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

[アルゴリズム(Ruby)]深さ優先探索・幅優先探索の解説

こんにちは！じゃいごテックのあつしです。今回は木構造やグラフの探索に用いられる、深さ優先探索(Depth First Search)と、幅優先探索(Breadth First Search)をご紹介 ...

: paiza プログラミング

[Ruby|Python]paiza 標準出力メニュー【出力形式を指定して出力】

今回はpaiza 標準入力メニューセクション10【出力形式を指定して出力】をRubyとPythonで解説します。セクション10は、文字列や整数値を指定された形式で出力する問題です。目次本記事で使用 ...

: paiza プログラミング

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

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

: paiza プログラミング

paizaでプログラミング能力を測定しよう！

こんにちは！じゃいごテックのあつしです。突然ですがプログラミングの入門書や学習サイトで勉強したあとはどうしていますか？オリジナルゲームの開発？Webアプリの開発？いきなりアプリ開発は難しい！でも ...

PREV: [Ruby|Python]paiza 累積和メニュー4 【区間内の個数 (文字列)】

[Ruby|Python]paiza 累積和メニュー5 【二次元累積和】

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

累積和メニュー5：【二次元累積和】

5-STEP1: 二次元累積和 1 (paizaランク C 相当)

Ruby解答例

Python解答例

5-STEP2: 二次元累積和 2 (paizaランク C 相当)

入出力例

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

5-STEP3: 二次元累積和 3 (paizaランク C 相当)

入出力例

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

5-STEP4: 二次元累積和 4 (paizaランク C 相当)

入出力例

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

5-STEP5: 二次元累積和 5 (paizaランク C 相当)

入出力例

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

5-STEP6: 【二次元累積和】 二次元累積和 6 (paizaランク C 相当)

入出力例

Ruby解答例1

Ruby解答例2

Python解答例1

Python解答例2

5-STEP7: 【二次元累積和】 二次元累積和 7 (paizaランク C 相当)

問題

攻略ポイント

Ruby 問題を解く流れ

Ruby 解答コード

Ruby 他の解答例

Python 問題を解く流れ

Python 解答コード

Python 他の解答例

今回のまとめ

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

5-STEP6: 【二次元累積和】二次元累積和 6 (paizaランク C 相当)

5-STEP7: 【二次元累積和】二次元累積和 7 (paizaランク C 相当)