for "https://paiza.jp/poh/paizen"

paizen.rb

def hit?(block, vh, vw, wh, ww)
  wh.times do |h|
    datas = block[vh+h]
    return true unless datas
    targets = datas[vw-1, ww]
    return true if targets.any?
    return true unless targets.size == ww
  end
  false
end

height, width = gets.split(' ').map(&:to_i)

block = {}
(1..height).each do |h|
  line = gets
  datas = line.chomp.chars.map{|c| c == '0' ? false : true}
  block[h] = datas unless datas.all?
end

gets.to_i.times do
  ans = 0
  wh, ww = gets.split(' ').map(&:to_i)

  (1..(height - wh + 1)).each do |vh|
    next unless block[vh]
    (1..(width - ww + 1)).each do |vw|
      next if hit?(block, vh, vw, wh, ww)
      ans += 1
    end
  end
  puts ans
end

paizen2.rb

height, width = gets.split(' ').map(&:to_i)

# 横の空き情報
wblock = Hash.new{|h, k| h[k] = Hash.new(0)}
(1..height).each do |h|
  views = gets.chomp.reverse.chars
  counter = 0
  views.each.with_index do |c, i|
    case c
    when '0'
      counter += 1
      wblock[h][width - i] = counter
    when '1'
      counter = 0
    end
  end
end

# 解析
memo = {}
gets.to_i.times do
  wh, ww = gets.split(' ').map(&:to_i)
  (puts 0; next) if (wh > height || ww > width)

  # 結果がすでにわかっているならそれを採用する
  mans = memo["#{wh}_#{ww}"]
  (puts mans; next) if mans

  ans = 0
  (1..(height - wh + 1)).each do |vh|
    (1..(width - ww + 1)).each do |vw|
      # 幅が足りない
      next if wblock[vh][vw] < ww
      # 高さ1なので確定
      (ans += 1; next) if wh == 1
      # 縦にparseして横の空き具合を調べる
      ans += 1 if ((vh+1)..(vh+wh-1)).all?{|h| wblock[h][vw] >= ww}
    end
  end

  # 結果を記録する
  memo["#{wh}_#{ww}"] = ans
  puts ans
end

paizen3.rb

def block_to_cod(block, height, width)
  cod = Hash.new{|h, k| h[k] = []}
  (1..height).each do |h|
    (1..(width)).each do |w|
      val = block[h][w]
      next if val <= 0
      cod[val] << [h, w]
    end
  end
  cod
end

height, width = gets.split(' ').map(&:to_i)

# 横の空き情報
wblock = {}
(1..height).each do |h|
  views = gets.chomp.reverse.chars
  datas = {}
  counter = 0
  views.each.with_index do |c, i|
    case c
    when '0'
      counter += 1
    when '1'
      counter = 0
    end
    datas[width - i] = counter
  end
  wblock[h] = datas
end

# 横の空き => 座標リストに変換
wcod = block_to_cod(wblock, height, width)

# 縦の空き情報
hblock = Hash.new{|h, k| h[k] = Hash.new(0)}
(1..width).each do |w|
  (1..height).each do |h|
    (h..height).each do |nh|
      d = wblock[nh][w]
      break if d <= 0
      hblock[h][w] += 1
    end
  end
end

# 縦の空き => 座標リストに変換
hcod = block_to_cod(hblock, height, width)

# 解析
memo = {}
gets.to_i.times do
  wh, ww = gets.split(' ').map(&:to_i)
  (puts 0; next) if (wh > height || ww > width)

  # 結果がすでにわかっているならそれを採用する
  mans = memo["#{wh}_#{ww}"]
  (puts mans; next) if mans

  # 調べるべき座標
  ans = 0
  if ww < wh
    # 横の方が短い場合
    wcod.keys.select{|v| v >= ww}.each do |k|
      wcod[k].each do |c|
        # 全ての横座標に対し、必要な高さが存在するか？
        bh = c.first
        next if (bh + wh - 1) > height
        bw = c.last
        ans += 1 if (bw..(bw+ww-1)).all?{|w| hblock[bh][w] >= wh}
      end
    end
  else
    # 縦の方が短い場合
    hcod.keys.select{|v| v >= wh}.each do |k|
      hcod[k].each do |c|
        # 全ての縦座標に対し、必要な幅が存在するか？
        bw = c.last
        next if (bw + ww - 1) > width
        bh = c.first
        ans += 1 if (bh..(bh+wh-1)).all?{|h| wblock[h][bw] >= ww}
      end
    end
  end

  # 結果を記録する
  memo["#{wh}_#{ww}"] = ans
  puts ans
end

paizen4.rb

height, width = gets.split(' ').map(&:to_i)

# 幅の空き情報
wblock = Hash.new{|h, k| h[k] = []}
max_width = 0
(1..height).each do |h|
  views = gets.chomp.reverse.chars
  counter = 0
  views.each.with_index do |c, i|
    case c
    when '0'
      counter += 1
      max_width = counter if counter > max_width
    when '1'
      counter = 0
    end
    wblock[width - i][h] = counter
  end
end

# 高さの空き情報
hblock = Hash.new{|h, k| h[k] = []}
max_height = 0
(1..width).each do |w|
  (1..height).each do |h|
    he = 0
    wb = wblock[w]
    (h..height).each do |nh|
      d = wb[nh]
      break if d <= 0
      he += 1
    end
    hblock[h][w] = he
    max_height = he if he > max_height
  end
end

# 対象取得
targets = Hash.new{|h, k| h[k] = []}
tickets = []
gets.to_i.times do
  wh, ww = gets.split(' ').map(&:to_i)
  tickets << "#{wh}_#{ww}"
  # 空き幅の限界を超えないものだけ
  next if ww > max_width
  next if wh > max_height
  targets[ww] << wh
end

# 解析
memo = {}
targets.each do |ww, whs|
  whs.uniq.sort.each do |wh|
    ans = 0
    (1..(height - wh + 1)).each do |vh|
      hb = hblock[vh]
      (1..(width - ww + 1)).each do |vw|
        # この座標自体が空いてない
        next if wblock[vw][vh] < ww
        next if hb[vw] < wh

        # 高さor幅が1なので確保OK
        (ans += 1; next) if (wh == 1 || ww == 1)

        # parseして空き具合を調べる
        hit = false
        if wh < ww
          fh = vh + wh - 1
          wb = wblock[vw]
          (wh-1).times do |i|
            next if wb[fh-i] >= ww
            hit = true
            break
          end
        else
          fw = vw + ww - 1
          (ww-1).times do |i|
            next if hb[fw-i] >= wh
            hit = true
            break
          end
        end
        next if hit
        ans += 1
      end
    end

    if ans > 0
      # 結果を記録する
      memo["#{wh}_#{ww}"] = ans
    else
      # これ以上の高さについて計算するだけ無駄
      break
    end
  end
end

# 最終出力
tickets.each do |key|
  puts (memo[key] || 0)
end

paizen5.rb

height, width = gets.split(' ').map(&:to_i)

# 幅の空き情報
wblock = Hash.new{|h, k| h[k] = []}
max_width = 0
(1..height).each do |h|
  views = gets.chomp.reverse.chars
  counter = 0
  views.each.with_index do |c, i|
    case c
    when '0'
      counter += 1
      max_width = counter if counter > max_width
    when '1'
      counter = 0
    end
    wblock[width - i][h] = counter
  end
end

# 高さの空き情報
hblock = Hash.new{|h, k| h[k] = []}
max_height = 0
(1..width).each do |w|
  (1..height).each do |h|
    he = 0
    wb = wblock[w]
    (h..height).each do |nh|
      d = wb[nh]
      break if d <= 0
      he += 1
    end
    hblock[h][w] = he
    max_height = he if he > max_height
  end
end

# 対象取得
targets = Hash.new{|h, k| h[k] = []}
tickets = []
gets.to_i.times do
  wh, ww = gets.split(' ').map(&:to_i)
  tickets << "#{wh}_#{ww}"
  # 空き幅の限界を超えないものだけ
  next if ww > max_width
  next if wh > max_height
  targets[ww] << wh
end

# 解析
memo = {}
targets.each do |ww, whs|
  whs.uniq.sort.each do |wh|
    ans = 0
    th = wh-1
    tw = ww-1
    if wh < ww
      (1..(width - ww + 1)).each do |vw|
        wb = wblock[vw]
        (1..(height - wh + 1)).each do |vh|
          next if wb[vh] < ww
          (ans += 1; next) if wh == 1
          next if hblock[vh][vw] < wh
          (ans += 1; next) if ww == 1

          hit = false
          fh = vh + wh - 1
          th.times do |i|
            next if wb[fh-i] >= ww
            hit = true
            break
          end
          ans += 1 unless hit
        end
      end
    else
      (1..(height - wh + 1)).each do |vh|
        hb = hblock[vh]
        (1..(width - ww + 1)).each do |vw|
          next if hb[vw] < wh
          (ans += 1; next) if ww == 1
          next if wblock[vw][vh] < ww
          (ans += 1; next) if wh == 1

          hit = false
          fw = vw + ww - 1
          tw.times do |i|
            next if hb[fw-i] >= wh
            hit = true
            break
          end
          ans += 1 unless hit
        end
      end
    end

    if ans > 0
      # 結果を記録する
      memo["#{wh}_#{ww}"] = ans
    else
      # これ以上の高さについて計算するだけ無駄
      break
    end
  end
end

# 最終出力
tickets.each do |key|
  puts (memo[key] || 0)
end

7bd496 => http://paiza.jp/poh/paizen/result/abc3618a53b7b7da07400343b7a02dae

130e413 => http://paiza.jp/poh/paizen/result/4f222df289dfbc2d4e60b75e6dc7f06d

5c5654 => http://paiza.jp/poh/paizen/result/fc7e0643997789e39ebdce0cfab5b6c8

50112e => http://paiza.jp/poh/paizen/result/c47a99d4f2c4d6cdc6bee4025ef31e7b

3deaeb => http://paiza.jp/poh/paizen/result/4395caf72d0cc1ec464bd0452a39ec60

なぜか遅くなった

a9a7789 => http://paiza.jp/poh/paizen/result/6d279a6289bb5c20a3cdd040e17b53a0

速くなったので、間引く方法を別に考えないといけない予感

b7e749 => http://paiza.jp/poh/paizen/result/625e6d4f56597399590f2ae3849262a9

テストデータ仕様を見てガード条件を入れたが、
おそらくネックがデータ構築部分に移っている

a7aa0a => http://paiza.jp/poh/paizen/result/51ab8dfff7b8597fce6bbe099ef23e29

たしかに短くなったが、ボトルネックは別なところにある

0b1c83 => http://paiza.jp/poh/paizen/result/c4504e021d8b2ce64057470c9cfe1f4a

もうちょっと根本的に計算回数を減らす方法はないか・・・

a1162f => http://paiza.jp/poh/paizen/result/dca478c337ea383a0e9bbcb02259a3a5

小手先の方法ではやはりダメ
データ構造そのものに切り込まないと削れない

25066b => http://paiza.jp/poh/paizen/result/b68d048decd2d88f57db7778e1d875d3

メモ化したのは良かったけど、まだ不足

1dd82e => http://paiza.jp/poh/paizen/result/a63bb73e7e9a3093a89fad4b41b3a06d

ver2をメモ化
こうしてみると、ver3は複雑なロジックを組んだわりに速度に寄与してない
ver2からやり直す

c909a2 => http://paiza.jp/poh/paizen/result/3dbb079041abc8a3f68cd8d9b740f051

ver2を改変
コードはシンプルになったけど遅い

fa6e40 => http://paiza.jp/poh/paizen/result/369bf59ced19959fd06a72607cdfd496

ver4
先に対象を選別してしまうことで、計算回数を減らす作戦

それ自体は悪くないけども、あまり寄与してないところを見ると、
やはりデータ構造と判断ロジックの問題か

0d2363 => http://paiza.jp/poh/paizen/result/4fd6144322ba720a5503a5c718c46e75

ver4
初めての6突破

Test case 4 : 0.88s
Test case 5 : 3.10s
Test case 6 : 11.92s

21af47 => http://paiza.jp/poh/paizen/result/19295f1c27e78ba08a8a98326d898616

Test case 6 : 8.35s

5d78a5 => http://paiza.jp/poh/paizen/result/50a8dade19d41e8d3833b2f658c90621

Test case 6 : 7.35s

219a57 => http://paiza.jp/poh/paizen/result/39a0de82f850ba3b155d60600e6474ad

Test case 6 : 5.88s
オブジェクトレベルのチューニングになってきた

f1185c => http://paiza.jp/poh/paizen/result/40c8052ed89a9f28efb21eaf4120d658

Test case 6 : 5.59s

248f7f => http://paiza.jp/poh/paizen/result/5b8db51fd04608f1c7463d268560307b

ver5
Test case 6 : 4.39s

47c8e2 => http://paiza.jp/poh/paizen/result/da003df380f521e46f8d1ae449edb06d

Test case 6 : 4.41s

dad77a => http://paiza.jp/poh/paizen/result/a57e0c23cf40a789921665b57152a61a

ついに突破
bit演算とparse回数の最適化が鍵であった

最終的な解答だけ残して削除

6eb329 => http://paiza.jp/poh/paizen/result/0a1301346eadae7ae26515e64a786e7f

evalなんて馬鹿げた手を使っていたら、そりゃ遅くなるよ(´･ω･)(･ω･｀)ﾈｰ

3650f8 => http://paiza.jp/poh/paizen/result/82967b508c0f18216f02892f36adb69d

びっくりするほど変わらなかったΣ(ﾟДﾟ)ｶﾞｰﾝ

9b15a2 => http://paiza.jp/poh/paizen/result/0ba0a0c1b970fb72525886d3abc42e15

ちょっといじったらSSSに到達(；　д )　ﾟ　ﾟ