問題 http://nabetani.sakura.ne.jp/hena/orde02pire/
実装リンク集 http://qiita.com/Nabetani/items/8d7691e9bb7655c3b990
です。
で。
実装方針はいくつかあって。
一番簡単に書けるのは、長方形を全部列挙するものだと思う。
ciel さん( http://qiita.com/cielavenir/items/70e54825ffbdf6ff6a6a )の最初の実装がそういう感じ。
ciel さんが書いている通りこれは遅くて（とはいえ、このアルゴリズムを選んだひとの中では非常に速いほうだと思う）やや残念な感じだけど、ruby でルーズに書いても数分で終わるので、アリだと思う。
速いのは
- x 座標については、点の位置を見ながら可能性のある範囲を全て列挙する
- y 座標については、尺取り法を使う
というような実装。もちろん、これと同等の方法がたくさんあると思う。
もっといいのがあるかもしれない。
ぜんぜん綺麗に書けてないけど、私の実装は以下のとおり：
require "benchmark"
require "pp"
require "pry"
XY = [*?0..?9,*?A..?Z,*?a..?z]
WH=XY.size
# 尺取り法
# @param x0 左端
# @param x1 右端
# @param ys 点がある y 座標の一覧
# @param poses 点の位置のリスト
# @param delta 点の位置に対して境界をどうするかを示す整数
# @param ifsame 同値だった場合に増やすか減らすかを示す整数
def inchworm( x0, x1, ys, n, poses, r, delta, ifsame )
xr=((x0+delta)..(x1-delta))
return if poses.count{ |pos| xr===pos[0] }<n
poses_x = poses.select{ |pos| xr===pos[0] }
indices=[0,0]
while( indices.max<ys.size ) do
y0,y1=ys[indices[0]]+delta,ys[indices[1]]-delta
yr=(y0..y1)
#↓の c の計算で ciel さんのようにすると速くなる
c=poses_x.count{ |pos|yr===pos[1] }
if c<n
indices[1]+=1
elsif n<c
indices[0]+=1
else
r.push( (x1-x0+1-delta*2)*(y1-y0+1) )
indices[ifsame]+=1
end
end
end
# 最小サイズを取ってくる
def minsize( n, poses )
xs,ys=[0,1].map{ |xy|
poses.flat_map{ |pos| [pos[xy]] }.sort.uniq
}
xs.repeated_combination(2).with_object([]) { |(x0,x1), r|
# ここで ys と poses を絞ると速くなるけどサボった
inchworm( x0, x1, ys, n, poses, r, 0, 0 )
}.min
end
# 最大サイズを取ってくる
def maxsize( n, poses )
xs,ys=[0,1].map{ |xy|
( poses.flat_map{ |pos| [pos[xy]] }+[-1,WH] ).sort.uniq
}
xs.repeated_combination(2).with_object([]) { |(x0,x1), r|
inchworm( x0, x1, ys, n, poses, r, 1, 1 )
}.max
end
def solve( src )
sn, spos = src.split(":")
n=sn.to_i
poses = spos.split(",").map{ |s| s.chars.map{ |xy| XY.index(xy) } }
ms=minsize(n,poses)
return "-" unless ms
[ms, maxsize(n,poses)].join(",")
end
if $0==__FILE__
$stdout.sync=true
r=Benchmark.realtime do
DATA.map{ |line|
num, src, e0 = line.split(/\s+/)
expected = e0.split(",").sort_by(&:to_i).join(",")
actual = nil
tick = Benchmark.realtime{ actual = solve(src) }
ok=actual==expected
if ok
puts( "ok %s : %s / %f" % [ num, actual, tick ] )
else
puts("**NG** %s : %s / %s / %f" % [ num, expected, actual, tick ] )
end
ok
}.all?(&:itself).tap{ |x| puts( x ? "Everything is okay!" : "something wrong..." ) }
end
puts( "%f msec" % (r*1000) )
end
__END__
x 0:00 - リンク
y 10:00 - リンク
0 3:Oh,Be,AF,in,eG,ir,l5,Q8,mC,7T,Ty,tT 108,1920 リンク
1 3:00,zz,0z,z0 - リンク
46 11:lQ,EN,vO,tn,qO,F3,9k,K2,UC,P0,XY,DB,QO,ps,hy,fl,Dt,ex,Vc,vF,Pf,Vk,uo,Xc,Sh,KE,9g,3H,l6 658,1995 リンク
いつもどおりテストデータは省略。
最大を求めるための尺取りと最小を求めるための尺取りをひとつにまとめてみたんだけど、わかりにくくなったような気も。
尺取り法について簡単に説明すると。
区間$[a,b]$ に対して $f([a,b])$ という関数があって、$P⊂Q$ なら、$f(P)≦f(Q)$ である。
定数 $K$ がある。
$f([a,b])=K$ となるような $a, b$ を考えて、$b-a$ の最大値または最小値を求めたい。
というような場合に役に立つ。$a, b$ は離散的とする。
$a$, $b$ の取りうる最小値、たとえば$[0,0]$からスタートする。で、以下を繰り返す。
- $f([a,b])<K$ なら、$b$ を増やす。
- $K<f([a,b])$ なら、$a$ を増やす。
- $f([a,b])=K$ の場合。最大値がほしいなら $b$ を増やす。最小値がほしいなら $a$ を増やす。
$f([a,b])=K$ になったときに最小値または最大値の候補として記録すれば良い。
かんたんでしょ？
ところで。
尺取り法は英語で inchworm method ？