AtCoder Beginer Contest 045 - D
- AtCoder Beginer Contest 045 - D すぬけ君の塗り絵 / Snuke's Coloring
- 与えられたHxWの格子に黒く塗られた場所が指定される（以下黒マス）
- 3x3の正方形で全部の場所を見ていったときに正方形に含まれる黒マスの数を数え上げる
- 黒マスの数は０～９になるはずなので、それぞれの数になる正方形をすべて答えよ
解説
考察系の問題
- シミュレーション的に解いているとTLEになりプログラムが完了しない
- 逆転の発想で黒マスが影響を与える座標をカウントする
- 黒マスが影響を与える座標は、黒マスから見て左上に最大９個あるはず、これをハッシュなどで数え上げる
Ruby的な話
- 当初答えはhash内のvalueの数え上げで出していたが、これでは3秒に間に合わない
- 提出 #8406771
- Enumerableを使う処理が大好きなのだが、競プロではこれは悪手（countはたぶん配列をフルスキャン×9回する）
(1..9).each do |n|
puts ans.count{|k,v| v==n}
end
- ほかの人のコードを見てこのように変えた
ans = Array.new(10,0) sum.each_value do |value| ans[value] += 1 end ans[0] = (H-2)*(W-2) - sum.length puts ans