paiza オンラインハッカソン vol.2 をやってみた

またまた Ruby でやってみました。
　

とりあえず何の工夫もないもの

誰でもすぐに考えそうな方法でやってみました。つまりは総当り。

全然ダメですね。詳しい結果はこちら。

コード。

height, width = gets.split.map(&:to_i)
@window = []
height.times {@window << gets.chomp.chars.map(&:to_i)}
num = gets.to_i
wgt_size = []
num.times {wgt_size << gets.split.map(&:to_i)}

def check(wgth, wgtw, h, w)
  wgth.times do |wh|
    wgtw.times {|ww| return false unless @window[wh + h][ww + w].zero?}
  end
  true
end

num.times do |i|
  h, w = wgt_size[i]
  co = 0
  (height - h + 1).times do |h1|
    (width - w + 1).times {|w1| co += 1 if check(h, w, h1, w1)}
  end
  puts co
end

ループが 5重になっています。これではデータの量が増えるとどうしようもないですね。
　

工夫する

それぞれのマスは空いているかいないかなので、ビット演算で判定することにします。ただし、与えられたデータは空いている場所が 0 なので、ビットを反転させて処理します。

いや、まだまだ木野ちゃん喜んでくれないですね。詳しい結果はこちら。

コード。

height, width = gets.split.map(&:to_i)
wd = []
height.times {wd << (~ gets.chomp.to_i(2) & ("1" * width).to_i(2))}
num = gets.to_i
wgt_size = []
num.times {wgt_size << gets.split.map(&:to_i)}

window = wd.inject {|r, i| r * 2 ** width + i}

num.times do
  h, w = wgt_size.shift
  if h > height or w > width
    puts 0
  else
    co = 0
    widget = 0
    h.times {widget = widget * 2 ** width + ("1" * w).to_i(2)}
    (height - h + 1).times do
      wgt = widget
      (width - w + 1).times do
        co += 1 if window & widget == widget
        widget = widget << 1    #ビットシフト
      end
      widget = wgt << width     #ビットシフト
    end
    puts co
  end
end

ループは 3重です。
　

最終形

もう少し工夫します。配置可能位置がいちばんせまいところだけ考えればいいので、最初からウィジェットの高さに応じてテーブルを作っておきます。さらにメモ化して高速化。

何とか木野ちゃん、よろこんでくれました。自分にはこれ以上考えつかないですね。詳しい結果はこちら。なお、メモ化する前の結果はこちら。いちおうすべて通っていますが、木野ちゃんのよろこび方がちがいますね。

コード。

height, width = gets.split.map(&:to_i)
wnd = []
height.times {wnd << (~ gets.chomp.to_i(2) & ("1" * width).to_i(2))}
num = gets.to_i
wgt_size = []
num.times {wgt_size << gets.split.map(&:to_i)}

table = []
height.times do |i|
  ar = []
  (height - i).times {|j| ar << wnd[j, i + 1].inject(&:&)}
  ar.delete(0)
  table << ar
end

num.times do
  memo = {}
  count = 0
  h, w = wgt_size.shift
  if h <= height and w <= width
    wid = widget = ("1" * w).to_i(2)
    table[h - 1].each do |wd|
      if memo[wd]
        co = memo[wd]
      else
        co = 0
        (width - w + 1).times do
          co += 1 if wd & widget == widget
          widget = widget << 1    #ビットシフト
        end
        memo[wd] = co
        widget = wid
      end
      count += co
    end
  end
  puts count
end