LoginSignup
0
0

More than 5 years have passed since last update.

オフラインリアルタイムどう書くE32の回答

Posted at

残念ながら参加できませんでしたが、解きました。
3時間以上かかっています、またかなり汚いコードになってしまいました。

xがreal、yがimagの複素数で点と、線の方向を示しています。
linesは線が重なったら1つの線としてマージした結果、
crossは線と線の交点です。
crossの組み合わせで4点とって四角か判定していますが、
ちゃんとやれば組み合わせを使う必要はないです。

実行時間はヘボノートPCで2秒程度でした。

e32.rb
def get_cross_impl( p1, d1, p2, d2 )
  x = p1.real
  y = p2.imag
  return nil unless (p2.real..(p2+d2).real).include?(x)
  return nil unless (p1.imag..(p1+d1).imag).include?(y)
  Complex(x, y)
end

def get_cross( p1, d1, p2, d2 )
  if d1.real == 0
    get_cross_impl( p1, d1, p2, d2 )
  else
    get_cross_impl( p2, d2, p1, d1 )
  end
end

def add_line( lines, cross, blp, bld )
  lines.each { |cp, cd|
    if (bld * cd).imag == 0
      next
    end
    c = get_cross( blp, bld, cp, cd )
    cross << c if c
  }
  dup_line = lines.select { |cp, cd|
    if bld.real == 0 && cd.real == 0 && blp.real == cp.real
      range = (blp.imag..(blp+bld).imag)
      range.include?(cp.imag) || range.include?((cp+cd).imag)
    elsif bld.imag == 0 && cd.imag == 0 && blp.imag == cp.imag
      range = (blp.real..(blp+bld).real)
      range.include?(cp.real) || range.include?((cp+cd).real)
    else
      false
    end
  }
  if dup_line.length != 0
    dup_line.each { |a| lines.delete(a) }
    dup_line << [ blp, bld, ]
    (aminx, aminy, amaxx, amaxy) = dup_line.map { |cp, cd|
      [ cp.real, cp.imag, (cp+cd).real, (cp+cd).imag, ]
    }.transpose
    np = Complex(aminx.min, aminy.min)
    nd = Complex(amaxx.max, amaxy.max) - np
    lines << [ np, nd, ]
  else
    lines << [ blp, bld, ]
  end
end

def include_line?( lines, start, dir )
  lines.any? { |cp, cd|
    next false if (dir * cd).imag != 0
    if dir.real == 0 && start.real == cp.real
      next cp.imag <= start.imag && (cp+cd).imag >= (start+dir).imag
    end
    if dir.imag == 0 && start.imag == cp.imag
      next cp.real <= start.real && (cp+cd).real >= (start+dir).real
    end
    false
  }
end

def is_square(lines, ul, ur, dl, dr)
  return false if ul.real != ur.real
  return false if dl.real != dr.real
  return false if (ur - ul) != (dr - dl)
  return false unless include_line?(lines, ul, (ur-ul))
  return false unless include_line?(lines, dl, (dr-dl))
  return false if ul.imag != dl.imag
  return false if ur.imag != dr.imag
  return false if (dl - ul) != (dr - ur)
  return false unless include_line?(lines, ul, (dl-ul))
  return false unless include_line?(lines, ur, (dr-ur))
  true
end

def is_dirty(sq, point, dir)
  if dir.real == 0 && (sq[0].real+1..sq[0].real+sq[1]-1).include?(point.real)
    return (point.imag..(point+dir).imag-1).include?(sq[0].imag) ||
      (point.imag+1..(point+dir).imag).include?(sq[0].imag+sq[2]) ||
      (sq[0].imag..sq[0].imag+sq[2]-1).include?(point.imag) ||
      (sq[0].imag+1..sq[0].imag+sq[2]).include?((point+dir).imag)
  end
  if dir.imag == 0 && (sq[0].imag+1..sq[0].imag+sq[2]-1).include?(point.imag)
    return (point.real..(point+dir).real-1).include?(sq[0].real) ||
      (point.real+1..(point+dir).real).include?(sq[0].real+sq[1]) ||
      (sq[0].real..sq[0].real+sq[1]-1).include?(point.real) ||
      (sq[0].real+1..sq[0].real+sq[1]).include?((point+dir).real)
  end
  false
end

def solve( input )
  lines = []
  cross = []
  input.split('/').each { |s|
    (l, u, r, d) = s.each_char.map { |c| c.to_i(36) }
    lu = Complex(l, u)
    ru = Complex(r, u)
    ld = Complex(l, d)
    rd = Complex(r, d)
    [ [lu, ru,], [lu, ld,], [ru, rd,], [ld, rd,], ].each { |p1, p2|
      add_line( lines, cross, p1, p2-p1 )
    }
  }
  cross = cross.uniq.sort { |l, r|
    (l.real <=> r.real) * 2 + (l.imag <=> r.imag)
  }
  sqs = cross.combination(4).each_with_object([]) { |(ul, ur, dl, dr), a|
    next unless is_square(lines, ul, ur, dl, dr)
    a << [ ul, (dl - ul).real, (ur - ul).imag, ]
  }
  sqs = sqs.select { |sq|
    lines.none? { |point, dir|
      is_dirty(sq, point, dir)
    }
  }
  sqs.map { |sq| sq[1] * sq[2] }.sort.join(',')
end

DATA.each { |line|
  /\/\*(?<no>\d+)\*\/ test\( "(?<input>.+)", "(?<expected>.+)" \);/ =~ line
  actual = solve( input )
  if expected != actual
    puts 'NG[%s] : input = %s, expected = %s, actual = %s' % [ no, input, expected, actual, ]
    exit 1
  else
    puts 'OK[%s]' % [ no, ]
  end
}

__END__
/*0*/ test( "43gw/d7qq/mlop", "8,57" );
/*1*/ test( "034a", "28" );
/*2*/ test( "06qr/8pnq", "15" );
/*3*/ test( "c1th/b2qy", "210" );
/*4*/ test( "c8wz/gbsg/i0xd", "20" );
/*5*/ test( "97uv/2g5x/eihv", "39,51" );
/*6*/ test( "254d/2jvu/mjvu", "16,99,220" );
/*7*/ test( "ggiu/ggzu/g5ig", "22,28,238" );
/*8*/ test( "jbnc/i7xe/i7je/icje", "2,4,5" );
/*9*/ test( "3cey/0fzo", "27,33,99,110,189" );
/*10*/ test( "00ab/p0zd/0ofz/87rs", "8,12,28" );
/*11*/ test( "1dsy/2d9s/2s9y", "21,42,105,399" );
/*12*/ test( "28db/d0lm/d1i8/l0w5", "33,35,55" );
/*13*/ test( "3aen/4fir/1lev", "2,20,40,48,60" );
/*14*/ test( "j7ou/3rms/m4vs", "3,10,16,42,60" );
/*15*/ test( "336a/3rkw/jlor/3akw", "6,21,24,85" );
/*16*/ test( "21om/87bv/67cv", "9,15,18,27,30,45" );
/*17*/ test( "4hhx/056u/4rvu", "6,20,33,39,42,110" );
/*18*/ test( "b0sh/pgxt/88lq/amux", "3,20,35,44,90" );
/*19*/ test( "c0hc/h6md/fdmk/4cfj", "2,35,49,60,77" );
/*20*/ test( "0liz/ilvz/0lvr/0rvz", "78,104,108,144" );
/*21*/ test( "81ib/q1zb/8cir/qczr", "90,100,135,150" );
/*22*/ test( "h7t8/t8ye/g8he/hetz", "6,12,30,72,252" );
/*23*/ test( "b5qy/o6qc/21tb/qoyu/b5eu", "2,10,18,48,57" );
/*24*/ test( "eajn/jkln/j8ua/nkun/u4wy", "6,21,22,60,65" );
/*25*/ test( "wwzz/nfuw/nfzz/41vw/l1r2/nfrg", "4,6,9,17" );
/*26*/ test( "46rb/t6xb/m7zk/4hrj/thxj", "4,8,10,16,20,36" );
/*27*/ test( "olwx/ogul/ogwx/ogux/agux", "10,24,30,72,238" );
/*28*/ test( "b7un/c3hv/fiyo/h6xm", "2,10,12,13,16,20,52,143" );
/*29*/ test( "d6qa/o4qr/tcur/9bto", "2,4,6,8,15,26,39,44,195" );
/*30*/ test( "2lsx/54hf/k3yi/8dhw/bhny", "3,12,18,24,33,60,66" );
/*31*/ test( "apcx/a8pv/7uwx/a2c8/c8pu", "2,4,9,10,12,13,34,286" );
/*32*/ test( "7yjz/jywz/7ejz/j5wy/bejz/jewy", "4,8,13,80,117,160,260" );
/*33*/ test( "d0wk/5dqu/6lqs/77ae/f4mq/56bm", "3,4,5,7,14,18,28,35,49,63" );
/*34*/ test( "d4gn/94in/d4rs/94xu/97xn", "6,9,12,18,27,32,48,64,70,96,144" );
/*35*/ test( "l5wh/wdxn/60xs/c5fd/jpwx/mgqx", "4,9,10,12,15,18,20,24,30,32" );
/*36*/ test( "5178/58xk/uixk/71u8/71uk/71ui/51ui", "4,6,14,20,30,46,161,230" );
/*37*/ test( "m8sp/mosp/2imp/i8sp/2isp/i8si/misp/iosp", "4,6,24,36,40,60,112" );
/*38*/ test( "34d5/253k/f4m5/m5rk/2o3u/3udy/fumy/moru", "6,7,10,15,28,30,40,75" );
/*39*/ test( "2ilw/mbnc/n9wj/9dmy/6qwy/2ekh/9dkh", "1,6,11,18,21,33,72,80,90,96" );
/*40*/ test( "j0le/10uo/q6ue/jeqt/jelf/l6xf", "2,4,5,27,28,32,35,36,40,54,63,432" );
/*41*/ test( "j4mu/31r5/qeyf/0f5h/r0v5/00qi/j5kf/jlru", "3,4,8,9,10,10,20,27,45,52" );
/*42*/ test( "g8kc/dbuv/gbkc/dbgv/evuw/dbui/d8kw", "1,4,6,9,10,12,21,24,39,52,70,130" );
/*43*/ test( "apry/a0ry/a0hx/60hp/6xhy/a0hp/a0hy/6phy/6phx", "4,7,32,56,90,100,175,250" );
/*44*/ test( "1eok/33by/d0kz/1rnw", "10,10,12,12,14,15,16,21,24,35,40,42,48,49,56,88,98" );
/*45*/ test( "0qbs/6cws/l6xj/659q/03lc/bclp/96dj/96wc", "10,12,13,14,14,21,24,42,48,66,77" );
/*46*/ test( "q8sr/98yu/clyn/s8yl/9lqr/0rsu/0l9m/0n9u", "4,8,9,12,26,27,28,36,42,57,78,221" );
/*47*/ test( "5sjy/jbsy/8dgp/gkvp/gdvh/jhvp/i2vk", "3,4,6,8,9,12,15,15,18,27,36,45,81,84,96" );
/*48*/ test( "42va/10nf/23l6/c2uw/3hpo/4ofu/m7sv", "3,5,6,8,8,15,18,20,21,24,27,32,48,50,63,70" );
/*49*/ test( "84lj/10j1/wcxd/ljnl/1njx/01xd/00x1/81wq/1c8q", "1,1,4,7,11,14,18,21,33,70,78,117,126" );
/*50*/ test( "kfvg/76vq/136d/6gvq/6g7q/137g/7dmz/63m6/m3vz", "2,3,9,10,27,45,50,81,81,90,105,135,150" );
/*51*/ test( "4eht/38jt/jeym/htjv/eeyv/eejt/3myv/h1jt/hejm", "4,6,7,12,14,14,16,21,22,24,70,80,120,135" );
/*52*/ test( "smuz/04c7/28zc/83ri/cihu/8flm/masw/8ivo", "2,4,6,8,10,10,12,16,16,20,22,24,24,30,30,36,39,48" );
/*53*/ test( "7fuu/17fd/6cpg/fghu/ahnt/adww/rhxz/4hxl/0pby", "1,2,2,2,3,3,4,4,4,5,8,8,9,10,12,12,12,12,15,15,16,16,20,24,27,30,32,48" );
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0