【AtCoder-Ruby】累積和をマスターする
累積和を何も考えずに書けるようにする！ を自分なりに理解する。
考え方
サンプル実装
puts "L R N" puts "a1 a2 a3 a4 .. aN" puts puts "input: " L, R, N = gets.strip.split.map(&:to_i) a = gets.strip.split.map(&:to_i) # 累積和の初期化 s = Array.new(N + 1) {0} N.times do |i| s[i + 1] = a[i] + s[i] end puts "ans: #{s[R] - s[L - 1]}"
$ ruby cumulative_sum.rb L R N a1, a2, a3, a4, .. an input: 3 5 7 1 2 3 4 5 6 7 ans: 12
練習問題
ABC122 C - GeT AC を解いてみる。
問題文
A, C, G, T からなる長さ N の文字列 S が与えられます。
以下の Q 個の問いに答えてください。
- 問 i ( 1 ≤ i ≤ Q): 整数 l i , r i ( 1 ≤ l i < r i ≤ N) が与えられる。 S の先頭から l i 文字目から r i 文字目までの (両端含む) 部分文字列を考える。この文字列に AC は部分文字列として何回現れるか。
考え方
回答
N, Q = gets.strip.split.map(&:to_i) S = gets.strip lr = Q.times.map { gets.strip.split.map(&:to_i) } a = Array.new(N + 1) {0} N.times do |i| a[i + 1] = S[i..(i+1)].eql?('AC') ? a[i] + 1 : a[i] end lr.each do |l, r| puts a[r - 1] - a[l - 1] end
考察
2次元の累積和は一旦概念だけ理解。
あとで実装する。
