parrot-studio/paizen.rb

## 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 = {}
max_width = 0
(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
      max_width = counter if counter > max_width
    when '1'
      counter = 0
    end
    datas[width - i] = counter
  end
  wblock[h] = datas
end

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

# 対象取得
targets = []
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 << [wh, ww]
end

# 解析
memo = {}
targets.each do |t|
  wh, ww = t

  # すでにわかっているなら飛ばす
  next if memo["#{wh}_#{ww}"]

  ans = 0
  (1..(height - wh + 1)).each do |vh|
    (1..(width - ww + 1)).each do |vw|
      # この座標自体が空いてない
      next if wblock[vh][vw] < ww
      next if hblock[vh][vw] < wh
      # 高さor幅が1なので確保OK
      (ans += 1; next) if (wh == 1 || ww == 1)

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

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

# 最終出力
tickets.each do |key|
  puts (memo[key] || 0)
end
	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
	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
	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
	height, width = gets.split(' ').map(&:to_i)

	# 幅の空き情報
	wblock = {}
	max_width = 0
	(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
	max_width = counter if counter > max_width
	when '1'
	counter = 0
	end
	datas[width - i] = counter
	end
	wblock[h] = datas
	end

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

	# 対象取得
	targets = []
	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 << [wh, ww]
	end

	# 解析
	memo = {}
	targets.each do \|t\|
	wh, ww = t

	# すでにわかっているなら飛ばす
	next if memo["#{wh}_#{ww}"]

	ans = 0
	(1..(height - wh + 1)).each do \|vh\|
	(1..(width - ww + 1)).each do \|vw\|
	# この座標自体が空いてない
	next if wblock[vh][vw] < ww
	next if hblock[vh][vw] < wh
	# 高さor幅が1なので確保OK
	(ans += 1; next) if (wh == 1 \|\| ww == 1)

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

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

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