問題 : http://mtsmfm.github.io/2016/10/01/doukaku-e08.html
実装リンク集 : http://qiita.com/mtsmfm/items/94ebd353fa3b7e608f68
真剣にワーストケースを考えるとなかなか面倒な問題のような気がしている(詳しく検討すらできていない)んだけど、テストケースはそれほど厳しくないのでテストケースを通す方針でさらりと。
ruby2.3.1p112
require "benchmark"
class Array
def x; self[0]; end
def y; self[1]; end
end
def rev(m)
m.size.times.with_object({}){ |e,o| o[m[e]]=e }
end
def fields( sq, rev_enemy )
xr,yr = 2.times.map{ |e| sq.map{ |f| f[e] }.uniq.sort }.map{ |a,b| (a..b) }
xr.each.with_object({}) do |x,o|
yr.each do |y|
o[[x,y]]=true if x!= xr.last && y != yr.last
return {} if rev_enemy[[x,y]]
end
end
end
def solve_impl( me, enemy )
rev_me = rev(me)
rev_enemy = rev(enemy)
me.size.times.with_object({}){ |ia,o|
ia.times do |ib|
a = me[ia]
b = me[ib]
next if a.x==b.x || a.y==b.y
next unless ic = rev_me[[a.x, b.y]]
next unless id =rev_me[[b.x, a.y]]
o.merge!( fields( [a,b,me[ic], me[id] ], rev_enemy ) )
end
}.size
end
def solve( src )
wb=src.split(",").map{ |b|
b.scan(/([a-z])([0-9]+)/).map{ |a,b|
[a.ord-?a.ord, b.to_i]
}
}
[ solve_impl( *wb ), solve_impl( *wb.reverse ) ].join(",")
end
$stdout.sync=true
DATA.map do |line|
/(?<num>\d+).*"(?<src>.+)".*"(?<expected>.+)"/=~line
actual = nil
tick = Benchmark.realtime{ actual = solve( src ) }
okay = actual==expected
puts( "%s %s %s->%s ( e:%s ) %f" % [ ( okay ? "ok" : "**NG**" ), num, src[0,70], actual, expected, tick ] )
okay
end.all?.tap{|x| puts( x ? "everything is ok" : "something wrong" ) }
__END__
/*0*/ test("d3d4e3e4d9h7h9j3j4j7j9,f4f6g4g5g6h5h6", "5,3")
/*1*/ test("a1,s19", "0,0")
いろいろまずい点はあるものの、1時間経った時点でのソースコード。
二重ループは combination
を使うべきだとか、Array
に x
とか勝手に生やすなとか、後置 unless の中で代入するなとか、Array
を Hash
のキーにするなとか、いろいろ。
私は Hash
を Set
代わりに使ったんだけど、どうせ重複がそれほど多くないので Array
を使って最後に uniq
した方がよかったなぁと思ったり。
あと。「-?a.ord
」は不要だった。これもなんかくやしい。
これで、手元で実行して 0.2秒弱。
ちょっともやもやしているんだけど、よしとする。
追記
のテストケースを追加すると 12秒。やっぱりダメか。
ハッシュのキーを [x,y]
ではなく [x*32+y]
にするだけで 3.3秒になるんだけど、本質的ではないよね。