paiza POH Vol.4 野田さん攻略

procon paiza ruby

解答

#!/usr/bin/env ruby

file = $stdin
lines = file.readlines
file.close

t, n = lines[0].split.map{|x| x.to_i}
m_list = lines[1, n].map{|x| x.to_i}

max_sum = sum = m_list[0, t].inject(0){|sum, x| sum + x}

for i in t..n - 1
  sum += -m_list[i - t] + m_list[i]
  max_sum = [max_sum, sum].max
end
  
puts max_sum

結果

コードの覚え書き

  • 3番目のみ計算量を考慮して差分だけ計算するようにした

解説を読んでのメモ

  • しゃくとり法というらしい。累積和はあんまり道具として身についていないな。