Skip to content

Instantly share code, notes, and snippets.

@parrot-studio parrot-studio/paizen.rb
Last active Aug 29, 2015

Embed
What would you like to do?
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
@parrot-studio

This comment has been minimized.

@parrot-studio

This comment has been minimized.

@parrot-studio

This comment has been minimized.

@parrot-studio

This comment has been minimized.

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 16, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 16, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 16, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 17, 2014

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

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2014

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 23, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 23, 2014

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 25, 2014

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

evalなんて馬鹿げた手を使っていたら、そりゃ遅くなるよ(´・ω・)(・ω・`)ネー

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 25, 2014

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

びっくりするほど変わらなかったΣ(゚Д゚)ガーン

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

commented Apr 25, 2014

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

ちょっといじったらSSSに到達(; д ) ゚ ゚

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.