オフラインリアルタイムどう書く E18 の実装例 #Ruby

問題 : http://nabetani.sakura.ne.jp/hena/orde18twintri/
実装リンク集 : https://qiita.com/Nabetani/items/891d07f4d645ec00ce9a

三角形をすべて含む矩形の面積を S として、
O(S)ぐらい、O(√S)ぐらい、, O(1)ぐらい、の３つの戦略がある。

私は O(S)ぐらいと O(√S)ぐらいの２つを実装した。

まずは O(S)ぐらいの、遅い方から。

ruby

class Triangle
  def initialize( s )
    x,y,@dir,h=s.scan( /(\d+)\,(\d+)([RLTB])(\d+)/ ).to_a.flatten
    @x,@y,@h = [x,y,h].map(&:to_i)
  end
  def ranges
    [ [@x-@h, @x+@h], [@y-@h, @y+@h] ]
  end
  def include?(x,y)
    dx = x - @x
    dy = y - @y
    case @dir
    when "R"
      0<=-dx && -dx<@h && dy.abs <= dx.abs
    when "L"
      0<=dx && dx<@h && dy.abs <= dx.abs
    when "T"
      0<=dy && dy<@h && dx.abs <= dy.abs
    when "B"
      0<=-dy && -dy<@h && dx.abs <= dy.abs
    else
      raise "unexpected"
    end
  end
end

def  solve_impl( a, b )
  axr, ayr = a.ranges
  bxr, byr = b.ranges
  count=0
  ([ayr[0],byr[0]].max..[ayr[1],byr[1]].min).each do |y|
    ([axr[0],bxr[0]].max..[axr[1],bxr[1]].min).each do |x|
      count += 1 if a.include?(x,y) && b.include?(x,y)
    end
  end
  count
end

def solve( src )
  ts = src.split("/").map{ |s| Triangle.new( s ) }
  solve_impl( *ts ).to_s
end

DATA.each do |line|
  num, src, expected = line.split(/\s+/)
  actual = solve( src )
  okay = actual==expected
  puts( [(okay ? "ok" : "**NG**"), src, actual, expected ].join(" ") )
end

__END__
0 7,0R6/3,1B5 15  
1 1,6L4/4,9R9 4 
2 0,2R4/1,3B4 3 
3 1,2L4/1,2L5 16  
46 5621,8460T7612/2715,5697L8851  861192

三角形に含まれていそうなマス目を全部舐める作戦。
手元のマシンで1分弱。

ranges の返す値を工夫すると倍ぐらい速くなりそうだけど、気にしない気にしない。

続いて O(√S) ぐらいの実装。手元のマシンで1秒弱。

ruby

class Triangle
  def initialize( src )
    sx,sy,@dir,sh=src.scan( /(\d+)\,(\d+)([RLTB])(\d+)/ ).to_a.flatten
    x,y,h = [sx,sy,sh].map(&:to_i)
    @top=x+y*1i
    @height = (h-1)*{"R"=>-1, "L"=>1, "T"=>1i, "B"=>-1i}[@dir]
  end

  def xrange
    if @height.real==0
      (@top.real-@height.imag.abs)..(@top.real+@height.imag.abs)
    else
      r = [@top.real, @top.real + @height.real]
      r.min .. r.max
    end
  end

  def y_at(x)
    dx = x - @top.real
    case @dir
    when "R"
      return [] unless (@height.real..0)===dx
      [ @top.imag - dx.abs, @top.imag + dx.abs ]
    when "L"
      return [] unless (0..@height.real)===dx
      [ @top.imag - dx.abs, @top.imag + dx.abs ]
    when "B"
      return [] unless dx.abs <= @height.imag.abs
      [@top.imag - @height.imag.abs, @top.imag - dx.abs]
    when "T"
      return [] unless dx.abs <= @height.imag.abs
      [@top.imag+dx.abs, @top.imag + @height.imag.abs ]
    else
      raise "unexpected"
    end
  end
end

def solve_impl(tris)
  xrange = tris.map{ |t| t.xrange.minmax }.flatten.minmax
  xrange.min.upto(xrange.max).sum{ |x|
    y0, y1 = tris.map{ |t| t.y_at(x) }.sort
    if y0.empty? || y1.empty?
      0
    else
      r = [y1.first, 1+[y1.last, y0.last].min]
      r==r.sort ? r[1]-r[0] : 0
    end
  }.to_s
end

def solve( src )
  tris = src.split("/").map{ |t| Triangle.new(t) }
  solve_impl( tris ).to_s
end

DATA.map{ |line|
  num, src, expected = line.split(/\s+/)
  actual = solve( src )
  okay = expected==actual
  puts( [(okay ? "ok" : "**NG**"), src, actual, expected ].join(" / ") )
  okay
}.all?.tap{ |ok|
  puts( ok ? "everything is okay" : "**SOMETHING WRONG***" )
}
__END__
0   7,0R6/3,1B5   15
1   1,6L4/4,9R9   4
2   0,2R4/1,3B4   3
3   1,2L4/1,2L5   16
46  5621,8460T7612/2715,5697L8851   861192

積分する感じ。

      r = [y1.first, 1+[y1.last, y0.last].min]
      r==r.sort ? r[1]-r[0] : 0

の部分がなかなかぱっと書けないところだけど、これがちゃんと書ければ O(√S)ぐらいになる。

O(1) の実装は

三角形の辺と辺の交点を求める
求めた交点と三角形の頂点を合わせて「イベント点」とする
イベント点を x 座標順にソートする
イベント点を通る y軸に平行な線で、図形を分割する
各図形は台形または三角形になるので、その面積を計算して合計する

という戦略なんだけど、実装するのがめんどくさそうなので今のところ書いていない。