競プロ学習記録#1_Rubyのeachが遅いなんて知らなかったよ……

Rubyをメイン武器に競プロを1年くらいやってきましたが、長らくレートが停滞していて悲しいので、しっかり勉強して水色を目指したい。学習記録をつけよう！そんなnoteです。

がんばるぞい！

Frog 2 - Educational DP Contest B問題

DPわからないのいい加減にやばい、こんなんだからレートが上がらない、DPを倒すぞ！！！と強い気持ちでEducational DP Contestに取り組んだらB問題で足をくじかれた。問題はこちら。

動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

上の丁寧な解説記事を参考に基本的なDPを理解し、早速実践だと挑んだ2問目、TLE地獄……

はじめに書いたコードはこれ。

n,k = gets.chomp.split.map(&:to_i)
hs = gets.chomp.split.map(&:to_i)
dp = Array.new(n,10**18)
dp[0] = 0
(0..n-1).each do|i|
 (1..k).each do |j|
   dp[i+j] = [dp[i+j], dp[i] + (hs[i] - hs[i+j]).abs].min if i+j < n
 end
end
puts dp[n-1]

がっ・・・・・・・駄目っ・・・・・・・！通らない・・・・・・！

制約から最大の計算量は10^7、これが鬼門でRubyじゃ工夫を凝らさないと2secに収まらないとのこと……

今回重かった箇所はループを(0..n-1).eachで処理しているところと、最小値を配列を生成して処理をしているところで、そこを修正したらギリギリ2secに収まって通すことが出来ました。

n,k = gets.chomp.split.map(&:to_i)
hs = gets.chomp.split.map(&:to_i)
dp = Array.new(n,10**18)
dp[0] = 0
0.upto(n-1) do|i|
 1.upto(k) do |j|
   if i+j < n && dp[i+j] > dp[i] + (hs[i] - hs[i+j]).abs
     dp[i+j] = dp[i] + (hs[i] - hs[i+j]).abs
   end
 end
end
puts dp[n-1]

配列を生成すると重いよ、というのはググるとまあまあ色々な人が言及していたんですが、今回はそれだけだと通らず、通している人はループ処理を(n-1).timesや0.upto(n-1)で行っていることに気がついてようやく通せました。

eachがtimesやuptoと比べて遅いのは全く知らなかった……え、ホント？

気になってググってもあまり参考になるものがなく、かなり昔の記事しか見つからなかった。

rubyのループ(loop, each, while, for)の速度のベンチマーク - 僕のYak Shavingは終わらない

これを見ても別にeachとtimesに差はなさそう……自分でベンチマークを取ってみても、

                 user     system      total        real
each         0.310000   0.000000   0.310000 (  0.304696)
upto         0.330000   0.000000   0.330000 (  0.332380)
times        0.260000   0.000000   0.260000 (  0.266535)

といった感じ。ベンチマークのコードはこんな感じ。

require 'benchmark'

Benchmark.bm 10 do |r|
 r.report "each" do
   (0..10**5).each do |i|
     (0..100).each do |j|
       i > j
     end
   end
 end
 r.report "upto" do
   0.upto(10**5) do |i|
     0.upto(100) do |j|
       i > j
     end
   end
 end
 r.report "times" do
   (10**5).times do |i|
     (100).times do |j|
       i > j
     end
   end
 end

何もわからん、なんかしらんけどeachをuptoにしたら通った。

ベンチマークの書き方こうしたらいいとか、これは誰々が言ってたとかあったらぜひ教えて下さい、競プロ何もわからん。