Skip to content

Instantly share code, notes, and snippets.

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

 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 = {} (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 # 解析 gets.to_i.times do ans = 0 wh, ww = gets.split(' ').map(&:to_i) (puts ans; next) if (wh > height || ww > width) (1..(height - wh + 1)).each do |vh| (1..(width - ww + 1)).each do |vw| # この座標自体が横に空いてない next if wblock[vh][vw] < ww # 高さ1なので確保OK (ans += 1; next) if wh == 1 # 縦にparseして横の空き具合を調べる hit = false (wh-1).times do |i| next if wblock[vh+i+1][vw] >= ww hit = true break end next if hit ans += 1 end end 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) # 解析 gets.to_i.times do wh, ww = gets.split(' ').map(&:to_i) (puts 0; next) if (wh > height || ww > width) # 調べるべき座標 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 puts ans end
Owner Author

Owner Author

Owner Author

Owner Author

Owner Author

parrot-studio commented Apr 16, 2014

 なぜか遅くなった
Owner Author

parrot-studio commented Apr 16, 2014

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

parrot-studio commented Apr 16, 2014

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

parrot-studio commented Apr 17, 2014

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

parrot-studio commented Apr 17, 2014

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

parrot-studio commented Apr 17, 2014

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

parrot-studio commented Apr 17, 2014

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

parrot-studio commented Apr 17, 2014

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

parrot-studio commented Apr 17, 2014

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

parrot-studio commented Apr 17, 2014

 ver4 先に対象を選別してしまうことで、計算回数を減らす作戦 それ自体は悪くないけども、あまり寄与してないところを見ると、 やはりデータ構造と判断ロジックの問題か
Owner Author

parrot-studio commented Apr 18, 2014

 ver4 初めての6突破 Test case 4 : 0.88s Test case 5 : 3.10s Test case 6 : 11.92s
Owner Author

parrot-studio commented Apr 18, 2014

 Test case 6 : 8.35s
Owner Author

parrot-studio commented Apr 18, 2014

 Test case 6 : 7.35s
Owner Author

parrot-studio commented Apr 18, 2014

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

parrot-studio commented Apr 18, 2014

 Test case 6 : 5.59s
Owner Author

parrot-studio commented Apr 18, 2014

 ver5 Test case 6 : 4.39s
Owner Author

parrot-studio commented Apr 18, 2014

 Test case 6 : 4.41s
Owner Author

parrot-studio commented Apr 23, 2014

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

parrot-studio commented Apr 23, 2014

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

parrot-studio commented Apr 25, 2014

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

parrot-studio commented Apr 25, 2014

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

parrot-studio commented Apr 25, 2014

 ちょっといじったらSSSに到達(；　д )　ﾟ　ﾟ
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.