情報自炊

情報を血肉にしたい

AGC033 A問題をRubyで解いた際の反省点

これまで300点問題を一回も解いたことがなかったので、解けることを目標に挑んだ。 atcoder.jp

結果はTLE。今回もアルゴリズム的にダメだったのか、と思って解説や他の方のコードを見てみたところ…あれアルゴリズムは合ってる?

ダメだったところは値の持ち方、アクセスの仕方だった。いろいろ試してみて、最低限直すべきところが分かったのでここにまとめる。

修正前(TLE)

h,w = gets.chomp.split(" ").map(&:to_i)

arr = []
hash = {}
count = 0
result = 0
h.times do |h_i|
  tmp_arr = gets.chomp.split("")
  tmp_arr.each_with_index do |a, w_i|
    if a == "#" then
      hash[[h_i, w_i]] = 0
      count += 1
    end
  end
  arr << tmp_arr
end

while count < h * w do
  keys = hash.keys
  hash = {}
  result += 1
  keys.each do |(h_i, w_i)|
    if h_i - 1 >= 0 && arr[h_i - 1][w_i] == "." then
      hash[[h_i - 1, w_i]] = result
      arr[h_i - 1][w_i] = "#"
      count += 1
    end
    if h_i + 1 < h && arr[h_i + 1][w_i] == "." then
      hash[[h_i + 1, w_i]] = result
      arr[h_i + 1][w_i] = "#"
      count += 1
    end
    if w_i - 1 >= 0 && arr[h_i][w_i - 1] == "." then
      hash[[h_i, w_i - 1]] = result
      arr[h_i][w_i - 1] = "#"
      count += 1
    end
    if w_i + 1 < w && arr[h_i][w_i + 1] == "." then
      hash[[h_i, w_i + 1]] = result
      arr[h_i][w_i + 1] = "#"
      count += 1
    end
  end
end

puts result

ダメだった点は以下の3点

  1. "."や"#"と文字列のまま扱おうとしている
    • arrの中身が"."や"#"であり、whileの中身で== "."と文字列比較をしている
  2. gets.chomp.split("")
    • 配列を作成しているのが無駄。文字列のままでもインデックスを用いてn番目の文字へのアクセスが可能
  3. keys = hash.keys
    • hashのkeyでループして配列を作成する処理が無駄

他にも無駄になりそうな処理はあったが(番兵を用いてarrの外側へアクセスしないための条件分岐を減らすとか)対応しなくても大丈夫だった。上記3つは対応しないとTLEになってしまう。

特に1番目はこれで遅くなるとは微塵も思っていなかったのでとても勉強になった(コンテスト終了後の検証でもまさかこれが遅くなっている原因とは知らず驚いた)。

今回はコードを書く前にじっくり考えることができたので、最初からこのアルゴリズム自体で挑もうと思っていた。処理時間もO(HW)だから大丈夫だろうと思った矢先のTLEだったのでどうしたものかと困ったが、コンテスト後にこうして検証して原因まで分かったのでよしとする。

Rubyで最初解いていてTLEもらっていた人が、同じアルゴリズムC++で組み直してACをもらっていたのも見かけたので、やっぱりC++有利なのかなあとは思った。でも私は何がなんでもコンテストを勝ち抜くのが目的ではなく頭の体操が目的なので、このままRubyで突き進もうと思う。速くなるテクニックが見つかれば普段のコードでも意識できると思うし。

修正後

h,w = gets.chomp.split(" ").map(&:to_i)

arr = []
keys = []
count = 0
result = 0
h.times do |h_i|
  tmp_arr = []
  str = gets.chomp
  w.times do |w_i|
    if str[w_i] == "#" then
      keys << [h_i, w_i]
      count += 1
      tmp_arr << 1
    else
      tmp_arr << 0
    end
  end
  arr << tmp_arr
end

while count < h * w do
  tmp_keys = keys
  keys = []
  result += 1
  tmp_keys.each do |(h_i, w_i)|
    if h_i - 1 >= 0 && arr[h_i - 1][w_i] == 0 then
      keys << [h_i - 1, w_i]
      arr[h_i - 1][w_i] = 1
      count += 1
    end
    if h_i + 1 < h && arr[h_i + 1][w_i] == 0 then
      keys << [h_i + 1, w_i]
      arr[h_i + 1][w_i] = 1
      count += 1
    end
    if w_i - 1 >= 0 && arr[h_i][w_i - 1] == 0 then
      keys << [h_i, w_i - 1]
      arr[h_i][w_i - 1] = 1
      count += 1
    end
    if w_i + 1 < w && arr[h_i][w_i + 1] == 0 then
      keys << [h_i, w_i + 1]
      arr[h_i][w_i + 1] = 1
      count += 1
    end
  end
end

puts result