kunst1080/jd.rb

## jd.rb
# 仕様:
#  ホーム画面の領域を「field」とする。
#  fieldは[縦][横]の２次元配列。
#  fieldの各マスについて、配置できるウィジェットの高さ毎の最大横幅を持を格納した２次元配列を「fmap」とし、
#  縦幅と最大横幅ごとに配置可能なマスの数を集計したものを「wctable」とする。
#
#  ホーム画面に配置するウィジェットの属性を「widget」とし、その配列を「widgets」とする。
#
#  判定について
#    fieldのマスに対し、widgetをいくつ配置できるか判定する
#
# データ構造:
#    field[y][x] = 0 or 1
#    fmap[y][x] = {:max_height => n, widget_height => max_widget_width..}
#    wctable[widget_height][max_widget_width] = count
#    widget = [widget_height, widget_width]

def scanField()
    head = $stdin.readline.split
    h = head[0].to_i
    w = head[1].to_i
    field = $stdin.read(h * (w.succ)).split("\n").map do |row|
        row.split("").map(&:to_i)
    end

    fmap = []
    (h-1).downto(0).each do |y|
        fmap[y] = []
        (w-1).downto(0).each do |x|
            fmap[y][x] = searchMaxWidthes(
                field[y][x],
                fmap[y][x+1],
                if fmap[y+1] != nil && fmap[y+1][x][:max_height] != nil then
                    fmap[y+1][x][:max_height] else 0 end,
                h - y)
        end
    end
    fmap
end

def searchMaxWidthes(value, right_value, bottom_max_height, count_y)
    hs = {}
    if value == 1
        hs[:max_height] = 0
    elsif right_value == nil || right_value[:max_height] == 0
        max_height = bottom_max_height + 1
        hs = fillMap(max_height, 1)
        hs[:max_height] = max_height
    else
        max_height = bottom_max_height + 1
        hs = headPlusMap(right_value, max_height)
        hs[:max_height] = max_height
    end
    hs
end

def fillMap(size, value)
    hs = {}
    (1..size).each do |i|
        hs[i] = value
    end
    hs
end

def headPlusMap(srcMap, size)
    hs = {}
    (1..size).each do |i|
        if srcMap[i] == nil
            hs[i] = 1
        else
            hs[i] = srcMap[i] + 1
        end
    end
    hs
end

def scanWidgets()
    n = $stdin.readline.chomp.to_i
    widgets = Array.new(n)
    lines = $stdin.read.split
    offset = 0
    n.times {|i|
        widgets[i] = [
            lines[offset].to_i,
            lines[offset.succ].to_i
        ]
        offset = offset.succ.succ
    }
    widgets
end

def countWidgets(fmap)
    wctable = []
    fmap.each do |row|
        row.each do |cell|
            (1..cell[:max_height]).each do |h|
                max_widget_width = cell[h]
                wctable[h] = [] if wctable[h] == nil
                if wctable[h][max_widget_width] == nil
                    wctable[h][max_widget_width] = 1
                else
                    wctable[h][max_widget_width] += 1
                end
            end
        end
    end
    wctable
end

# MAIN
begin
    fmap = scanField
    widgets = scanWidgets
    wctable = countWidgets(fmap)

    result = ""
    widgets.each do |widget|
        widget_height, widget_width = widget
        count = 0
        max_widget_width = 0
        max_widget_width = wctable[widget_height].size if wctable[widget_height] != nil
        (widget_width..max_widget_width).each do |w|
            count += wctable[widget_height][w] if wctable[widget_height][w] != nil
        end
        result << count.to_s << "\n"
    end
    print result
end
	# 仕様:
	# ホーム画面の領域を「field」とする。
	# fieldは[縦][横]の２次元配列。
	# fieldの各マスについて、配置できるウィジェットの高さ毎の最大横幅を持を格納した２次元配列を「fmap」とし、
	# 縦幅と最大横幅ごとに配置可能なマスの数を集計したものを「wctable」とする。
	#
	# ホーム画面に配置するウィジェットの属性を「widget」とし、その配列を「widgets」とする。
	#
	# 判定について
	# fieldのマスに対し、widgetをいくつ配置できるか判定する
	#
	# データ構造:
	# field[y][x] = 0 or 1
	# fmap[y][x] = {:max_height => n, widget_height => max_widget_width..}
	# wctable[widget_height][max_widget_width] = count
	# widget = [widget_height, widget_width]

	def scanField()
	head = $stdin.readline.split
	h = head[0].to_i
	w = head[1].to_i
	field = $stdin.read(h * (w.succ)).split("\n").map do \|row\|
	row.split("").map(&:to_i)
	end

	fmap = []
	(h-1).downto(0).each do \|y\|
	fmap[y] = []
	(w-1).downto(0).each do \|x\|
	fmap[y][x] = searchMaxWidthes(
	field[y][x],
	fmap[y][x+1],
	if fmap[y+1] != nil && fmap[y+1][x][:max_height] != nil then
	fmap[y+1][x][:max_height] else 0 end,
	h - y)
	end
	end
	fmap
	end

	def searchMaxWidthes(value, right_value, bottom_max_height, count_y)
	hs = {}
	if value == 1
	hs[:max_height] = 0
	elsif right_value == nil \|\| right_value[:max_height] == 0
	max_height = bottom_max_height + 1
	hs = fillMap(max_height, 1)
	hs[:max_height] = max_height
	else
	max_height = bottom_max_height + 1
	hs = headPlusMap(right_value, max_height)
	hs[:max_height] = max_height
	end
	hs
	end

	def fillMap(size, value)
	hs = {}
	(1..size).each do \|i\|
	hs[i] = value
	end
	hs
	end

	def headPlusMap(srcMap, size)
	hs = {}
	(1..size).each do \|i\|
	if srcMap[i] == nil
	hs[i] = 1
	else
	hs[i] = srcMap[i] + 1
	end
	end
	hs
	end

	def scanWidgets()
	n = $stdin.readline.chomp.to_i
	widgets = Array.new(n)
	lines = $stdin.read.split
	offset = 0
	n.times {\|i\|
	widgets[i] = [
	lines[offset].to_i,
	lines[offset.succ].to_i
	]
	offset = offset.succ.succ
	}
	widgets
	end

	def countWidgets(fmap)
	wctable = []
	fmap.each do \|row\|
	row.each do \|cell\|
	(1..cell[:max_height]).each do \|h\|
	max_widget_width = cell[h]
	wctable[h] = [] if wctable[h] == nil
	if wctable[h][max_widget_width] == nil
	wctable[h][max_widget_width] = 1
	else
	wctable[h][max_widget_width] += 1
	end
	end
	end
	end
	wctable
	end

	# MAIN
	begin
	fmap = scanField
	widgets = scanWidgets
	wctable = countWidgets(fmap)

	result = ""
	widgets.each do \|widget\|
	widget_height, widget_width = widget
	count = 0
	max_widget_width = 0
	max_widget_width = wctable[widget_height].size if wctable[widget_height] != nil
	(widget_width..max_widget_width).each do \|w\|
	count += wctable[widget_height][w] if wctable[widget_height][w] != nil
	end
	result << count.to_s << "\n"
	end
	print result
	end