「女子大生とペアプロするだけの簡単なお仕事です！ paizaオンラインハッカソンVol.2」
https://paiza.jp/poh/paizen というものにチャレンジしてきました。※仕様やら内容は上記サイトを参照言語はなんとなくRubyで。RPGツクールで触ったことあるしね！
まずは初稿

# 仕様:
# ホーム画面の領域を「field」とする
# fieldは[縦, 横]の２次元配列
# fieldの各要素の値については、入力値に従い以下で表現される
# 0 - ウィジェット配置なし
# 1 - ウィジェット配置済み
#
# ホーム画面に配置するウィジェットの属性を「widget」とし、その配列を「widgets」とする
# widhetは[縦size, 横size]の配列
#
# 判定について
# fieldから、判定したいwidgetと同じサイズの領域を切り出し(「area」とする)、
# areaの全要素が0であればウィジェット配置可能であると判定する。
# ただしareaがはみ出る場合は判定せずにウィジェット配置不可と判定する
class Array
def to_i
self.collect{|v| v.to_i}
end
end
def scan()
gets.chomp.split(" ")
end
def toCharArray(s)
s.split('')
end
# 入力値から field/wigdets を生成する
def readInputs()
h, w = scan.to_i
field = []
h.times {
s = scan[0]
field.push toCharArray(s).to_i
}
widgets_count = scan[0].to_i
widgets = []
widgets_count.times {
widgets.push scan.to_i
}
[field, widgets]
end
# ２次元配列の部分集合を切り出す
# 領域があふれた場合はnilを返す
def getArea(field, y, x, h, w)
if y + h > field.size
return nil
end
if x + w > field[0].size
return nil
end
field[y..y+h-1].collect{|v| v[x..x+w-1]}
end
# areaの各素が全てゼロの場合はtrueを返す
def check(area)
sum = 0
area.each { |r|
r.each{|x| sum += x}
}
sum == 0
end
# MAIN
begin
field, widgets = readInputs
widgets.each {|widget|
h = widget[0]
w = widget[1]
widget_ok_sum = 0
field.size.times { |y|
field[0].size.times { |x|
area = getArea(field, y, x, h, w)
if area != nil && check(area)
widget_ok_sum += 1
end
}
}
p widget_ok_sum
}
exit
end
view raw jd.rb hosted with ❤ by GitHub
計算量がO(n^2)になっていて、データ件数が少ないと問題なく動きますが、データ量が増えてくるとうんともすんとも言わなくなりました・・・結果はこちら http://paiza.jp/poh/paizen/result/029e6a61c105d942820fae91a1755bf3

ダメダメですな＞＜
結構悩んで、結局、

  • 入力値の読み込み時に先にカウントする
  • カウント時には前後の情報を使用し、ループ回数を減らす
とざっくりこんな感じでとにかくループ回数を減らすように書き直しました。
書き直した結果がこちら。
# 仕様:
# ホーム画面の領域を「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
view raw jd.rb hosted with ❤ by GitHub
結果はこちら https://paiza.jp/poh/paizen/result/e2fe88c724b3446157910e2924ed9654
早くなったはいいけど、かなり汚い・・・orz
とりあえずこんなかんじで。