競技プログラミング rubyでの処理速度向上

Question

プログラミングの腕を磨くべく、AtCoderといった競技プログラミングの問題に対する解答を実装しています。
(初心者なのでまだACになるのに時間がかかります)

例えばある問題に対して下記の様なコードを提出した結果、
テストケース16シナリオのうち、13シナリオがAC(OK)、3シナリオがタイムオーバーとなります。
(最初はもう少しタイムオーバーシナリオがあったのですが、for文をwhile文にしたりして改善していきました)
ですが、ここらへんで詰まっています。

「ここの書き方をこうすれば改善できるよ！」といった助言を頂ければ幸いです。

matrix = gets.chomp.split(' ')
line = readlines
len = line.length

i = 0
while i < len
  line[i] = line[i].split(' ').map(&:to_i)
  i += 1
end

answer = Array.new(matrix[0].to_i*matrix[1].to_i, 0)
h_sum = Array.new(matrix[1].to_i,0)
tmp_h = 0
while tmp_h < matrix[1].to_i
  tmp_w = 0
  while tmp_w < matrix[0].to_i
    h_sum[tmp_h] += line[tmp_w][tmp_h]
    tmp_w += 1
  end
  tmp_h += 1
end

i = 0
w_sum = 0
cnt = 0
while i < line.length
  h_word = ""
  w_sum = line[i].sum
  j = 0
  while j < line[i].length
    answer[cnt] = h_sum[j] - line[i][j] + w_sum
    h_word = "#{h_word} #{answer[(i*matrix[1].to_i)+j]}"
    cnt += 1
    j += 1
  end
  puts h_word
  i += 1
end

Answer 1

競技プログラミングで時間が不足する場合、以下のどれかのようなことが考えられます。

• なにかのミスで時間を浪費している
• オーダーを減らすよう、アルゴリズムから考え直す必要がある
• （Rubyで提出できる以上可能性は薄いですが）他言語で解かないと時間的に間に合わない

いずれにしても、問題に即して考える必要があります。「for文をwhile文にしたり」といった小手先の対応で改善できる幅とはレベルが違います。

Answer 2

小手先を並べます
前提ですが、 lineで入力されるデータは matrix のサイズに過不足ない 前提で書きます。そこが危ういなら、line読んだ所で確認してください

入る前に、line はいただけません。lines にしましょう。

まず、matrix = gets.chomp.split(' ') は line と同じように map(&:to_i) しておきましょう。

tmp_h = 0 から始まる９行は line の各列の合計をh_sumにいれているのですから lineの行列を入れ替えたものを作って ｔ_lines = line.transpose
h_sum = t_lines.map(&:sum)

２つ目の二重loopはそう単純ではないですが、いくつか
answer[cnt] と answer[(i*matrix[1].to_i)+j] が使われてますが、これ同じものですよね。同じものを違う表現するのは高速化以前に間違いの元なので。で、それ以前に、 answer ってここでしか使っていないのですね。でしたら配列にする必要はないので、answer で良いでしょう

内側のloopで String h_word を作り直してるのが気になります。これだと新しいobjectを作って古いのを捨てている。ので時間が掛かる。
内側をwhileではなく
h_word = line[i].map.with_index{|clmn,j| h_sum[j] - line[i][j] + w_sum }.join(' ')

「まず、matrix = gets.chomp.split(' ') は、、、」は不要でしたね。loopで使わなくなったから。line読み終わった所で捨てても良いもののようです。

蛇足
Arrayの要素を全部舐めるときは forやwhileでindexを変えていくのではなく each を使ったほうが「全部舐めるのね」とわかるのでプログラム追うコストが下がります。そうでないと、どこからどこまで読むのだろうか、頭と尻はどうやって決めるのだろうか など余分な妄想が片隅に浮かんで。。。
スピードが早いかどうかは分かりませんが 。

Answer 3

AtCoderのどの問題かわからないので制約がわからないのですが、
計算量はmatrix[0].to_i * matrix[1].to_i （表示されてる文字数？）程度なので、
アルゴリズムは問題ないと思います。

Rubyは入出力で時間が食われるので、
puts h_word で毎回出力するのではなく、
ループ中に配列や文字列に<<で末尾に追加し、まとめたのを最後に1回で出力してみたはいかがでしょうか