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 | |
(1..count).each{|c| wm[c] += 1} | |
else | |
count = 0 | |
end | |
end | |
val = (val << 1) | |
end | |
end | |
# 最終結果 | |
tickets.each do |key| | |
puts memo[key.first][key.last] | |
end |
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
3deaeb => http://paiza.jp/poh/paizen/result/4395caf72d0cc1ec464bd0452a39ec60 なぜか遅くなった |
This comment has been minimized.
This comment has been minimized.
a9a7789 => http://paiza.jp/poh/paizen/result/6d279a6289bb5c20a3cdd040e17b53a0 速くなったので、間引く方法を別に考えないといけない予感 |
This comment has been minimized.
This comment has been minimized.
b7e749 => http://paiza.jp/poh/paizen/result/625e6d4f56597399590f2ae3849262a9 テストデータ仕様を見てガード条件を入れたが、 |
This comment has been minimized.
This comment has been minimized.
a7aa0a => http://paiza.jp/poh/paizen/result/51ab8dfff7b8597fce6bbe099ef23e29 たしかに短くなったが、ボトルネックは別なところにある |
This comment has been minimized.
This comment has been minimized.
0b1c83 => http://paiza.jp/poh/paizen/result/c4504e021d8b2ce64057470c9cfe1f4a もうちょっと根本的に計算回数を減らす方法はないか・・・ |
This comment has been minimized.
This comment has been minimized.
a1162f => http://paiza.jp/poh/paizen/result/dca478c337ea383a0e9bbcb02259a3a5 小手先の方法ではやはりダメ |
This comment has been minimized.
This comment has been minimized.
25066b => http://paiza.jp/poh/paizen/result/b68d048decd2d88f57db7778e1d875d3 メモ化したのは良かったけど、まだ不足 |
This comment has been minimized.
This comment has been minimized.
1dd82e => http://paiza.jp/poh/paizen/result/a63bb73e7e9a3093a89fad4b41b3a06d ver2をメモ化 |
This comment has been minimized.
This comment has been minimized.
c909a2 => http://paiza.jp/poh/paizen/result/3dbb079041abc8a3f68cd8d9b740f051 ver2を改変 |
This comment has been minimized.
This comment has been minimized.
fa6e40 => http://paiza.jp/poh/paizen/result/369bf59ced19959fd06a72607cdfd496 ver4 それ自体は悪くないけども、あまり寄与してないところを見ると、 |
This comment has been minimized.
This comment has been minimized.
0d2363 => http://paiza.jp/poh/paizen/result/4fd6144322ba720a5503a5c718c46e75 ver4 Test case 4 : 0.88s |
This comment has been minimized.
This comment has been minimized.
21af47 => http://paiza.jp/poh/paizen/result/19295f1c27e78ba08a8a98326d898616 Test case 6 : 8.35s |
This comment has been minimized.
This comment has been minimized.
5d78a5 => http://paiza.jp/poh/paizen/result/50a8dade19d41e8d3833b2f658c90621 Test case 6 : 7.35s |
This comment has been minimized.
This comment has been minimized.
219a57 => http://paiza.jp/poh/paizen/result/39a0de82f850ba3b155d60600e6474ad Test case 6 : 5.88s |
This comment has been minimized.
This comment has been minimized.
f1185c => http://paiza.jp/poh/paizen/result/40c8052ed89a9f28efb21eaf4120d658 Test case 6 : 5.59s |
This comment has been minimized.
This comment has been minimized.
248f7f => http://paiza.jp/poh/paizen/result/5b8db51fd04608f1c7463d268560307b ver5 |
This comment has been minimized.
This comment has been minimized.
47c8e2 => http://paiza.jp/poh/paizen/result/da003df380f521e46f8d1ae449edb06d Test case 6 : 4.41s |
This comment has been minimized.
This comment has been minimized.
dad77a => http://paiza.jp/poh/paizen/result/a57e0c23cf40a789921665b57152a61a ついに突破 |
This comment has been minimized.
This comment has been minimized.
最終的な解答だけ残して削除 |
This comment has been minimized.
This comment has been minimized.
6eb329 => http://paiza.jp/poh/paizen/result/0a1301346eadae7ae26515e64a786e7f evalなんて馬鹿げた手を使っていたら、そりゃ遅くなるよ(´・ω・)(・ω・`)ネー |
This comment has been minimized.
This comment has been minimized.
3650f8 => http://paiza.jp/poh/paizen/result/82967b508c0f18216f02892f36adb69d びっくりするほど変わらなかったΣ(゚Д゚)ガーン |
This comment has been minimized.
This comment has been minimized.
9b15a2 => http://paiza.jp/poh/paizen/result/0ba0a0c1b970fb72525886d3abc42e15 ちょっといじったらSSSに到達(; д ) ゚ ゚ |
This comment has been minimized.
parrot-studio commentedApr 16, 2014
7bd496 => http://paiza.jp/poh/paizen/result/abc3618a53b7b7da07400343b7a02dae