白黒陣取りゲーム

• 問題：http://mtsmfm.github.io/2016/10/01/doukaku-e08.html
• 累積和を取る問題例 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098
  • こんな風に既出ですので、別にしえるさんメソッドというわけではないです…
• いもす法 http://imoz.jp/algorithms/imos_method.html
• いもす法の15言語による実践例 http://qiita.com/cielavenir/items/f5c3fcc0553ce0751b29

---

• 計算量を減らす工夫をいろいろしてます。O(HW+min(nC3,HW²))となりましょうか。
  • ならしでだいたいO(nHW)になりました(間違ってるかもしれませんが…)
• とりあえず、ideoneで0.1秒になったようです。http://ideone.com/cFZZXQ

tyama_henae08.rb

# !/usr/bin/env ruby
# http://mtsmfm.github.io/2016/10/01/doukaku-e08.html
# http://qiita.com/mtsmfm/items/94ebd353fa3b7e608f68

H=W=19
while gets
	# 要素が0..18の数値2つ(x座標,y座標)からなる配列
	a=$_.chomp.split(',').map{|e|e.scan(/[a-z]\d+/).map{|f|[f[0].ord-97,f[1..-1].to_i-1]}.sort}
	h=a.map{|e|Hash[*e.flat_map{|(x,y)|[x+y*W,1]}]}
	puts 2.times.map{|i|
		#相手のフィールド：駒を配置して累積和を取る
		#cf: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098
		opponent=(H+1).times.map{[0]*(W+1)}
		a[i^1].each{|x,y|opponent[y+1][x+1]=1}
		(H+1).times.map{|y|W.times.map{|x|opponent[y][x+1]+=opponent[y][x]}}
		H.times.map{|y|(W+1).times.map{|x|opponent[y+1][x]+=opponent[y][x]}}

if false
		#自分の駒を列挙するには方法が2つある
		#1:3点を列挙して、矩形をなすもう1点の存在を判定する
		#2:x座標の2つ組とy座標の2つ組をそれぞれ列挙して、4点の存在を判定する
		#今回は、列挙する個数が少ない方を自動で選択するようにした
		#(テストケースに依存するが、今回は0.6sから0.5sに高速化)
		xl,yl=a[i].transpose.map{|e|e.uniq.sort}
		f = if a[i].size*(a[i].size+1)*(a[i].size+2)/6 < xl.size*(xl.size+1)*yl.size*(yl.size+1)/4
			Enumerator.new{|y|
				a[i].combination(3){|b|
					if b[0][0]==b[1][0] && b[0][1]==b[2][1] && h[i][b[2][0]+b[1][1]*W]
						y<<[b[1][0],b[2][0]+1,b[2][1],b[1][1]+1]
					end
				}
			}
		else
			Enumerator.new{|y|
				xl.combination(2).to_a.product(yl.combination(2).to_a).each{|(w1,w2),(h1,h2)|
					if h[i][w1+h1*W] && h[i][w1+h2*W] && h[i][w2+h1*W] && h[i][w2+h2*W]
						y<<[w1,w2+1,h1,h2+1]
					end
				}
			}
		end
else
		#cia_ranaさんのアルゴリズムを再現してみました
		#https://bitbucket.org/snippets/cia_rana/aoqqq/e08
		f = Enumerator.new{|z|
			st=0
			a[i].chunk{|x,y|x}.each{|k,v|
				st+=v.size
				(v.size-1).times{|j|
					same_y=a[i][st..-1].select{|x0,y0|y0==v[j][1]}
					(j+1...v.size).each{|k|
						if q=same_y.find{|x0,y0|h[i][x0+v[k][1]*W]}
							z<<[v[j][0],q[0]+1,v[j][1],v[k][1]+1]
						end
					}
				}
			}
		}
end

		#4点が存在することを確認したら、最後に、内部に相手の駒がないことを確認し、陣地に加える
		#陣地の管理はいもす法( http://imoz.jp/algorithms/imos_method.html )を用いる
		#cf: http://qiita.com/cielavenir/items/f5c3fcc0553ce0751b29 (paiza poh5 4b)
		imos=(H+1).times.map{[0]*(W+1)}
		f.each{|w1,w2,h1,h2|
			if opponent[h1][w1]-opponent[h1][w2]-opponent[h2][w1]+opponent[h2][w2]==0
				imos[h1+1][w1+1]+=1
				imos[h1+1][w2]-=1
				imos[h2][w1+1]-=1
				imos[h2][w2]+=1
			end
		}
		(H+1).times.map{|y|W.times.map{|x|imos[y][x+1]+=imos[y][x]}}
		H.times.map{|y|(W+1).times.map{|x|imos[y+1][x]+=imos[y][x]}}
		r=0
		(H+1).times.map{|y|(W+1).times.map{|x|r+=1 if imos[y][x]>0}}
		r
	}*','
	STDOUT.flush
end