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?
height, width = gets.split(' ').map(&:to_i)
# bitとして扱う
lines = []
(1..height).each do |h|
lines << gets.chomp.to_i(2)
end
# 対象を解析
targets = {}
tickets = []
gets.to_i.times do
wh, ww = gets.split(' ').map(&:to_i)
tickets << [ww, wh]
targets[ww] = true if ww <= width
end
# 盤面をparse
memo = Hash.new{|h,k| h[k] = Hash.new(0)}
targets.keys.each do |tw|
wm = memo[tw]
val = ("1" * tw).to_i(2)
(width - tw + 1).times do
count = 0
height.times do |vi|
if lines[vi] & val == 0
count += 1
else
(1..count).each{|c| wm[c] += (count - c + 1)} if count > 0
count = 0
end
end
(1..count).each{|c| wm[c] += (count - c + 1)} if count > 0
val = (val << 1)
end
end
# 最終結果
tickets.each do |key|
puts memo[key.first][key.last]
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

parrot-studio commented Apr 16, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 16, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 16, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio 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

parrot-studio commented Apr 17, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 17, 2014

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

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio 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

parrot-studio commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio 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

parrot-studio commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 18, 2014

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio 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

parrot-studio commented Apr 23, 2014

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 25, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio commented Apr 25, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

parrot-studio 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.