ぴったり含む長方形のrubyによる実装と、若干の解説

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  リンク