オフラインリアルタイムどう書くE18の回答(2回目)

どう書くの後で書いた省メモリのO(n)版とO(1)版。
テストは省略。

O(1)のほうはangel_p_57さんの回答を参考にしています。

2つの三角形が含まれるxの値からyの最大最小を計算しています。

e18_a1.rb

def get_x_candidate( p, d, h )
  buf = [ p, ]
  if d == 0
    buf << p - h
    buf << p + h
  else
    buf << p + h * d
  end
  buf
end

def get_y_minmax( t, px )
  p, d, h = t
  if d.real == 0
    diff = (px - p.real).abs
    [ p.imag + h * d.imag, p.imag + diff * d.imag, ].sort
  else
    diff = (px - p.real) * d.real
    [ p.imag-diff, p.imag+diff, ]
  end
end

def solve( input )
  triangles = input.split('/').map { |s|
    /(?<x>\d+),(?<y>\d+)(?<d>[RLTB])(?<h>\d+)/ =~ s
    [ Complex(x, y), Complex('1i')**('LTRB'.index(d)), h.to_i-1, ]
  }
  x_range = triangles.map { |p, d, h|
    get_x_candidate( p.real, d.real, h ).minmax
  }.transpose

  x_range[0].max.upto(x_range[1].min).inject(0) { |sum, x|
    y_range = triangles.map { |t|
      get_y_minmax( t, x )
    }.transpose
    size = y_range[1].min - y_range[0].max
    (size >= 0) ? (sum + size + 1) : sum
  }.to_s
end

直角三角形を2つずつに分解して、組み合わせで共通部分を計算しています。

e18_a2.rb

I = Complex('1i')

def calc_tri( h )
  raise if h < 0
  (h+2)*(h+1)/2
end

def calc_same_dir( base_h, x, y, h )
  calc_x, calc_y, calc_h = x, y, h
  if calc_x < 0
    calc_h += calc_x
    calc_x = 0
  end
  if calc_y < 0
    calc_h += calc_y
    calc_y = 0
  end
  calc_h = base_h - calc_x - calc_y if calc_h > base_h - calc_x - calc_y
  return 0 if calc_h < 0
  calc_tri( calc_h )
end

def calc_reverse_dir( base_h, x, y, h )
  calc_x, calc_y, calc_h = x, y, h
  if calc_x > base_h
    calc_h -= calc_x - base_h
    calc_x = base_h
  end
  if calc_y > base_h
    calc_h -= calc_y - base_h
    calc_y = base_h
  end
  return 0 if calc_x < 0 or calc_y < 0 or calc_h < 0
  calc_h = calc_x + calc_y if calc_h > calc_x + calc_y
  ret = calc_tri( calc_h )
  ret -= calc_tri( calc_h - calc_x - 1 ) if calc_x < calc_h
  ret -= calc_tri( calc_h - calc_y - 1 ) if calc_y < calc_h
  ret -= calc_tri( calc_x + calc_y - base_h - 1 ) if base_h < calc_x + calc_y
  ret
end

def calc_alternate_dir( base_h, x, y, h )
  calc_x, calc_y, calc_h = x, y, h
  if calc_y < 0
    calc_h += calc_y
    calc_y = 0
  end
  if calc_x + calc_y > base_h
    calc_h -= calc_x + calc_y - base_h
    calc_x = base_h - calc_y
  end
  return 0 if calc_x < 0 or calc_y > base_h or calc_h < 0
  calc_h = base_h - calc_y + calc_x if calc_y + calc_h - calc_x > base_h
  ret = calc_tri( calc_h )
  ret -= calc_tri( calc_h - calc_x - 1 ) if calc_x - calc_h < 0
  if base_h < calc_x + calc_y + calc_h
    dh = calc_x + calc_y + calc_h - base_h
    if dh == 1
      ret -= calc_tri( 0 )
    elsif dh.even?
      ret -= calc_tri( dh/2 - 1 ) * 2
    else
      ret -= calc_tri( (dh+1)/2 - 1 )
      ret -= calc_tri( dh/2 - 1 )
    end
  end
  ret
end

def count( t1, t2 )
  npos = (t2[0] - t1[0]) * t1[1].conj
  nd = t2[1] * t1[1].conj
  case nd
  when 1
    calc_same_dir( t1[2], npos.real, npos.imag, t2[2] )
  when -1
    calc_reverse_dir( t1[2], npos.real, npos.imag, t2[2] )
  when I
    calc_alternate_dir( t1[2], npos.real, npos.imag, t2[2] )
  when -I
    calc_alternate_dir( t1[2], npos.imag, npos.real, t2[2] )
  else
    raise
  end
end

def solve( input )
  triangles = input.split('/').map { |s|
    /(?<x>\d+),(?<y>\d+)(?<d>[RLTB])(?<h>\d+)/ =~ s
    pos, d, h = [ Complex(x,y), I**('LTRB'.index(d)), h.to_i-1, ]
    center = pos + d * h
    sd = d * I
    [ [ center, -1*d, h, ], [ center+sd, sd, h-1, ], ]
  }

  sum = 0
  triangles[0].each { |t1|
    triangles[1].each { |t2|
      sum += count( t1, t2 )
    }
  }
  sum.to_s
end