累積和メニュー

STEP: 1 区間の和 1

a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
s = [0] * 11
(0..9).each do |i|
    s[i + 1] = s[i] + a[i]
end
puts s[8] - s[2]

STEP: 2 区間の和 2

a = gets.split.map(&:to_i)
s = [0] * 11
(0..9).each do |i|
    s[i + 1] = s[i] + a[i]
end
puts s[8] - s[2]

STEP: 3 区間の和 3

x, y = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
s = [0] * 11
(0..9).each do |i|
    s[i + 1] = s[i] + a[i]
end
puts s[y + 1] - s[x]

FINAL問題【区間の和】区間の和 4

n, x, y = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
s = [0] * (n + 1)
(0...n).each do |i|
    s[i + 1] = s[i] + a[i]
end
puts s[y + 1] - s[x]

STEP: 1 連続する N 個の和の最大値 1

a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
s = [0] * 11
max_sum = 0
(0..9).each do |i|
    s[i + 1] = s[i] + a[i]
end
(0..7).each do |i|
    max_sum = [s[i + 3] - s[i], max_sum].max
end
puts max_sum

STEP: 2 連続する N 個の和の最大値 2

a = gets.split.map(&:to_i)
s = [0] * 11
max_sum = 0
(0..9).each do |i|
    s[i + 1] = s[i] + a[i]
end
(0..7).each do |i|
    max_sum = [s[i + 3] - s[i], max_sum].max
end
puts max_sum

STEP: 3 連続する N 個の和の最大値 3

n = gets.to_i
a = gets.split.map(&:to_i)
s = [0] * (n + 1)
max_sum = 0
(0...n).each do |i|
    s[i + 1] = s[i] + a[i]
end
(0..n - 3).each do |i|
    max_sum = [s[i + 3] - s[i], max_sum].max
end
puts max_sum

FINAL問題【連続する N 個の和の最大値】連続する N 個の和の最大値 4

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
s = [0] * (n + 1)
max_sum = 0
(0...n).each do |i|
    s[i + 1] = s[i] + a[i]
end
(0..n - k).each do |i|
    max_sum = [s[i + k] - s[i], max_sum].max
end
puts max_sum

STEP: 1 区間内の個数 1

a = [1, 5, 9, 7, 5, 3, 2, 5, 8, 4]
b = [0] * 10
s = [0] * 11
(0..9).each do |i|
    if a[i].even?
        b[i] = 1
    end
end
(0..9).each do |i|
    s[i + 1] = s[i] + b[i]
end
puts s[8] - s[2]

STEP: 2 区間内の個数 2

a = gets.split.map(&:to_i)
b = [0] * 10
s = [0] * 11
(0..9).each do |i|
    if a[i].even?
        b[i] = 1
    end
end
(0..9).each do |i|
    s[i + 1] = s[i] + b[i]
end
puts s[8] - s[2]

STEP: 3 区間内の個数 3

x, y = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = [0] * 10
s = [0] * 11
(0..9).each do |i|
    if a[i].even?
        b[i] = 1
    end
end
(0..9).each do |i|
    s[i + 1] = s[i] + b[i]
end
puts s[y + 1] - s[x]

FINAL問題【区間内の個数】区間内の個数 4

n, x, y = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = [0] * n
s = [0] * (n + 1)
(0...n).each do |i|
    if a[i].even?
        b[i] = 1
    end
end
(0...n).each do |i|
    s[i + 1] = s[i] + b[i]
end
puts s[y + 1] - s[x]

STEP: 1 区間内の個数 (文字列) 1

str = "bwwbwbbwbwbb"
b = [0] * 10
s = [0] * 11
(0..9).each do |i|
    if str[i] == "b"
        b[i] = 1
    end
end
(0..9).each do |i|
    s[i + 1] = s[i] + b[i]
end
puts s[8] - s[2]

STEP: 2 区間内の個数 (文字列) 2

str = gets.chomp
b = [0] * 10
s = [0] * 11
(0..9).each do |i|
    if str[i] == "b"
        b[i] = 1
    end
end
(0..9).each do |i|
    s[i + 1] = s[i] + b[i]
end
puts s[8] - s[2]

STEP: 3 区間内の個数 (文字列) 3

x, y = gets.split.map(&:to_i)
str = gets.chomp
b = [0] * 10
s = [0] * 11
(0..9).each do |i|
    if str[i] == "b"
        b[i] = 1
    end
end
(0..9).each do |i|
    s[i + 1] = s[i] + b[i]
end
puts s[y] - s[x - 1]

FINAL問題【区間内の個数 (文字列) 】区間内の個数 (文字列) 4

n, x, y = gets.split.map(&:to_i)
str = gets.chomp
b = [0] * n
s = [0] * (n + 1)
(0...n).each do |i|
    if str[i] == "b"
        b[i] = 1
    end
end
(0...n).each do |i|
    s[i + 1] = s[i] + b[i]
end
puts s[y] - s[x - 1]

STEP: 1 二次元累積和 1

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(6) {[0] * 6}
(0..4).each do |y|
    (0..4).each do |x|
        s[y + 1][x + 1] = s[y][x + 1] + s[y + 1][x] - s[y][x] + a[y][x]
    end
end
puts s[4][4] - s[1][4] - s[4][1] + s[1][1]

STEP: 2 二次元累積和 2

a = 5.times.map { gets.split.map(&:to_i) }
s = Array.new(6) {[0] * 6}
(0..4).each do |y|
    (0..4).each do |x|
        s[y + 1][x + 1] = s[y][x + 1] + s[y + 1][x] - s[y][x] + a[y][x]
    end
end
puts s[4][4] - s[1][4] - s[4][1] + s[1][1]

STEP: 3 二次元累積和 3

a, b = gets.split.map(&:to_i)
array = 5.times.map { gets.split.map(&:to_i) }
s = Array.new(6) {[0] * 6}
(0..4).each do |y|
    (0..4).each do |x|
        s[y + 1][x + 1] = s[y][x + 1] + s[y + 1][x] - s[y][x] + array[y][x]
    end
end
puts s[b + 1][4] - s[a][4] - s[b + 1][3] + s[a][3]

STEP: 4 二次元累積和 4

a, b, c, d = gets.split.map(&:to_i)
array = 5.times.map { gets.split.map(&:to_i) }
s = Array.new(6) {[0] * 6}
(0..4).each do |y|
    (0..4).each do |x|
        s[y + 1][x + 1] = s[y][x + 1] + s[y + 1][x] - s[y][x] + array[y][x]
    end
end
puts s[c + 1][d + 1] - s[a][d + 1] - s[c + 1][b] + s[a][b]

STEP: 5 二次元累積和 5

n = gets.to_i
a, b, c, d = gets.split.map(&:to_i)
array = n.times.map { gets.split.map(&:to_i) }
s = Array.new(n + 1) {[0] * (n + 1)}
(0...n).each do |y|
    (0...n).each do |x|
        s[y + 1][x + 1] = s[y][x + 1] + s[y + 1][x] - s[y][x] + array[y][x]
    end
end
puts s[c + 1][d + 1] - s[a][d + 1] - s[c + 1][b] + s[a][b]

STEP: 6 【二次元累積和】二次元累積和 6

n, m = gets.split.map(&:to_i)
a, b, c, d = gets.split.map(&:to_i)
array = n.times.map { gets.split.map(&:to_i) }
s = Array.new(n + 1) {[0] * (m + 1)}
(0...n).each do |y|
    (0...m).each do |x|
        s[y + 1][x + 1] = s[y][x + 1] + s[y + 1][x] - s[y][x] + array[y][x]
    end
end
puts s[c + 1][d + 1] - s[a][d + 1] - s[c + 1][b] + s[a][b]

FINAL問題【二次元累積和】二次元累積和 7

n, m, q = gets.split.map(&:to_i)
array = n.times.map { gets.split.map(&:to_i) }
s = Array.new(n + 1) {[0] * (m + 1)}
(0...n).each do |y|
    (0...m).each do |x|
        s[y + 1][x + 1] = s[y][x + 1] + s[y + 1][x] - s[y][x] + array[y][x]
    end
end
q.times do |i|
    a, b, c, d = gets.split.map(&:to_i)
    puts s[c + 1][d + 1] - s[a][d + 1] - s[c + 1][b] + s[a][b]
end

STEP: 1 1 次元上のいもす法 1

a = [0] * 11
l = [1, 1, 3, 3, 7]
r = [3, 8, 8, 6, 9]
5.times do |i|
    a[l[i] - 1] += 1
    a[r[i]] -= 1
end
(0..9).each do |i|
    a[i + 1] += a[i]
end
puts a.max

STEP: 2 1 次元上のいもす法 2

a = [0] * 11
5.times do |i|
    l, r = gets.split.map(&:to_i)
    a[l - 1] += 1
    a[r] -= 1
end
(0..9).each do |i|
    a[i + 1] += a[i]
end
puts a.max

STEP: 3 1 次元上のいもす法 3

a = [0] * 11
n = gets.to_i
n.times do |i|
    l, r = gets.split.map(&:to_i)
    a[l - 1] += 1
    a[r] -= 1
end
(0..9).each do |i|
    a[i + 1] += a[i]
end
puts a.max

FINAL問題【1 次元上のいもす法】1 次元上のいもす法 4

n, q = gets.split.map(&:to_i)
a = [0] * (n + 1)
q.times do |i|
    l, r = gets.split.map(&:to_i)
    a[l - 1] += 1
    a[r] -= 1
end
(0...n).each do |i|
    a[i + 1] += a[i]
end
puts a.max

STEP: 1 2 次元上のいもす法 1

x_1 = [1, 2, 3, 1, 3]
y_1 = [1, 2, 3, 3, 1]
x_2 = [3, 4, 5, 3, 5]
y_2 = [3, 4, 5, 5, 3]
a = Array.new(6) { [0] * 6 }

5.times do |i|
    a[y_1[i] - 1][x_1[i] - 1] += 1
    a[y_2[i]][x_2[i]] += 1
    a[y_1[i] - 1][x_2[i]] -= 1
    a[y_2[i]][x_1[i] - 1] -= 1
end

(0..5).each do |i|
    (0..4).each do |j|
        a[i][j + 1] += a[i][j]
    end
end

(0..4).each do |i|
    (0..5).each do |j|
        a[i + 1][j] += a[i][j]
    end
end

puts a.flatten.max

STEP: 2 2 次元上のいもす法 2

array = Array.new(6) { [0] * 6 }

5.times do |i|
    a, b = gets.split.map(&:to_i)
    array[3 - 1][a - 1] += 1
    array[3][b] += 1
    array[3][a - 1] -= 1
    array[3 - 1][b] -= 1
end

(0..5).each do |i|
    (0..4).each do |j|
        array[i][j + 1] += array[i][j]
    end
end

(0..4).each do |i|
    (0..5).each do |j|
        array[i + 1][j] += array[i][j]
    end
end

puts array.flatten.max

STEP: 3 2 次元上のいもす法 3

array = Array.new(6) { [0] * 6 }

5.times do |i|
    a, b, c, d = gets.split.map(&:to_i)
    array[b - 1][a - 1] += 1
    array[d][c] += 1
    array[d][a - 1] -= 1
    array[b - 1][c] -= 1
end

(0..5).each do |i|
    (0..4).each do |j|
        array[i][j + 1] += array[i][j]
    end
end

(0..4).each do |i|
    (0..5).each do |j|
        array[i + 1][j] += array[i][j]
    end
end

puts array.flatten.max

STEP: 4 2 次元上のいもす法 4

n = gets.to_i
array = Array.new(6) { [0] * 6 }
n.times do |i|
    a, b, c, d = gets.split.map(&:to_i)
    array[b - 1][a - 1] += 1
    array[d][c] += 1
    array[d][a - 1] -= 1
    array[b - 1][c] -= 1
end

(0..5).each do |i|
    (0..4).each do |j|
        array[i][j + 1] += array[i][j]
    end
end

(0..4).each do |i|
    (0..5).each do |j|
        array[i + 1][j] += array[i][j]
    end
end

puts array.flatten.max

STEP: 5 2 次元上のいもす法 5

n, k = gets.split.map(&:to_i)
array = Array.new(n + 1) { [0] * (n + 1) }
k.times do |i|
    a, b, c, d = gets.split.map(&:to_i)
    array[b - 1][a - 1] += 1
    array[d][c] += 1
    array[d][a - 1] -= 1
    array[b - 1][c] -= 1
end

(0..n).each do |i|
    (0...n).each do |j|
        array[i][j + 1] += array[i][j]
    end
end

(0...n).each do |i|
    (0..n).each do |j|
        array[i + 1][j] += array[i][j]
    end
end

puts array.flatten.max

FINAL問題【2 次元上のいもす法】 2 次元上のいもす法 6

n, m, k = gets.split.map(&:to_i)
array = Array.new(n + 1) { [0] * (m + 1) }
k.times do |i|
    a, b, c, d = gets.split.map(&:to_i)
    array[b - 1][a - 1] += 1
    array[d][c] += 1
    array[d][a - 1] -= 1
    array[b - 1][c] -= 1
end

(0..n).each do |i|
    (0...m).each do |j|
        array[i][j + 1] += array[i][j]
    end
end

(0...n).each do |i|
    (0..m).each do |j|
        array[i + 1][j] += array[i][j]
    end
end

puts array.flatten.max

STEP: 1 区間の数え上げ 1

a = gets.split.map(&:to_i)
section_count = 0
elements_sum = 0
right = 0
(0..10).each do |left|
    while right < 10 && elements_sum + a[right] <= 15
        elements_sum += a[right]
        right += 1
    end
    section_count += right - left
    if left == right
        right += 1
    else
        elements_sum -= a[left]
    end
end
puts section_count

STEP: 2 区間の数え上げ 2

a = gets.split.map(&:to_i)
section_count = 0
elements_sum = 0
right = 0
(0..10).each do |left|
    while right < 10 && elements_sum + a[right] <= 15
        elements_sum += a[right]
        right += 1
    end
    section_count += right - left
    if left == right
        right += 1
    else
        elements_sum -= a[left]
    end
end
puts section_count

解答は区間の数え上げ 1と同じでOKです。

STEP: 3 区間の数え上げ 3

k = gets.to_i
a = gets.split.map(&:to_i)
section_count = 0
elements_sum = 0
right = 0
(0..10).each do |left|
    while right < 10 && elements_sum + a[right] <= k
        elements_sum += a[right]
        right += 1
    end
    section_count += right - left
    if left == right
        right += 1
    else
        elements_sum -= a[left]
    end
end
puts section_count

FINAL問題【区間の数え上げ】区間の数え上げ 4

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
section_count = 0
elements_sum = 0
right = 0
(0..n).each do |left|
    while right < n && elements_sum + a[right] <= k
        elements_sum += a[right]
        right += 1
    end
    section_count += right - left
    if left == right
        right += 1
    else
        elements_sum -= a[left]
    end
end
puts section_count

STEP: 1 区間の長さ 1

a = gets.split.map(&:to_i)
max_section = 0
elements_sum = 0
right = 0
(0..10).each do |left|
    while right < 10 && elements_sum + a[right] <= 15
        elements_sum += a[right]
        right += 1
    end
    max_section = [right - left, max_section].max
    if left == right
        right += 1
    else
        elements_sum -= a[left]
    end
end
puts max_section

STEP: 2 区間の長さ 2

a = gets.split.map(&:to_i)
max_section = 0
elements_sum = 0
right = 0
(0..10).each do |left|
    while right < 10 && elements_sum + a[right] <= 15
        elements_sum += a[right]
        right += 1
    end
    max_section = [right - left, max_section].max
    if left == right
        right += 1
    else
        elements_sum -= a[left]
    end
end
puts max_section

STEP: 3 区間の長さ 3

k = gets.to_i
a = gets.split.map(&:to_i)
max_section = 0
elements_sum = 0
right = 0
(0..10).each do |left|
    while right < 10 && elements_sum + a[right] <= k
        elements_sum += a[right]
        right += 1
    end
    max_section = [right - left, max_section].max
    if left == right
        right += 1
    else
        elements_sum -= a[left]
    end
end
puts max_section

FINAL問題【区間の長さ】区間の長さ 4

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
max_section = 0
elements_sum = 0
right = 0
(0..n).each do |left|
    while right < n && elements_sum + a[right] <= k
        elements_sum += a[right]
        right += 1
    end
    max_section = [right - left, max_section].max
    if left == right
        right += 1
    else
        elements_sum -= a[left]
    end
end
puts max_section