時間内には終わるようなロジックができませんでした。
自分の発表後にhas_point関数を高さでループしていたロジックを修正して、一応全テスト通りました。
それでも全テスト終了に20分かかったので点でループしようとしたのが誤りでした。
e18.rb
def has_point( d, px, py )
x, y, s, h = d
if s[0] == 0
diff = (py - y) * s[1]
return false if diff < 0
return false if h <= diff
return true if (x-diff..x+diff).include?(px)
else
diff = (px - x) * s[0]
return false if diff < 0
return false if h <= diff
return true if (y-diff..y+diff).include?(py)
end
return false
end
DIR = {
'R' => [ -1, 0, ],
'L' => [ 1, 0, ],
'T' => [ 0, 1, ],
'B' => [ 0, -1, ],
}
def solve( input )
deltas = input.split('/').map { |d|
d.scan(/(\d+),(\d+)([RLTB])(\d+)/)
x = $1.to_i
y = $2.to_i
s = DIR[$3]
h = $4.to_i
[ x, y, s, h, ]
}
x_range = deltas.flat_map { |x, y, s, h|
[ x, (s[0]==0) ? [x-(h-2)-1,x+(h-2)+1] : x+(h-1)*s[0] ].flatten
}.minmax
y_range = deltas.flat_map { |x, y, s, h|
[ y, (s[0]==0) ? y+(h-1)*s[1] : [y-(h-2)-1,y+(h-2)+1] ].flatten
}.minmax
count = 0
x_range[0].upto(x_range[1]) { |x|
y_range[0].upto(y_range[1]) { |y|
count += 1 if deltas.all? { |d| has_point( d, x, y ) }
}
}
count.to_s
end
def test( input, expected )
actual = solve( input )
if expected != actual
puts 'NG: input = %s, expected = %s, actual = %s' % [ input, expected, actual, ]
exit 1
else
puts 'OK: input = %s, actual = %s' % [ input, actual, ]
end
STDOUT.flush
end
test( "7,0R6/3,1B5", "15" )
test( "1,6L4/4,9R9", "4" )
test( "0,2R4/1,3B4", "3" )
test( "1,2L4/1,2L5", "16" )
test( "3,2L5/5,6B4", "8" )
test( "4,1B3/6,3B4", "4" )
test( "4,4R7/4,3R5", "20" )
test( "4,5R9/0,7T3", "7" )
test( "4,7T9/1,6T3", "1" )
test( "4,8B7/3,7L4", "10" )
test( "5,3L3/9,8L4", "0" )
test( "5,6B4/4,4R2", "3" )
test( "5,6B4/8,5R4", "8" )
test( "5,8B9/5,2L2", "4" )
test( "6,1L5/7,1T2", "3" )
test( "7,2B4/7,2T4", "1" )
test( "7,3T9/9,6L6", "11" )
test( "8,0R6/8,1R7", "30" )
test( "0,4R7/4,6R10", "36" )
test( "10,4L4/9,1T6", "9" )
test( "2,2T7/6,7T10", "4" )
test( "2,7R4/1,6L8 ", "2" )
test( "3,0R10/1,2T7", "7" )
test( "3,5T2/3,6B10", "2" )
test( "4,7R10/8,2T8", "6" )
test( "6,8B10/4,5B6", "36" )
test( "9,2B7/1,1B10", "6" )
test( "9,3R14/2,4R1", "1" )
test( "3,0R10/0,6B10", "54" )
test( "4,10T8/4,10T8", "64" )
test( "1,5T10/1,20B10", "56" )
test( "15,16L4/5,12L12", "4" )
test( "12,11T18/7,18R18", "34" )
test( "15,16T14/5,12L15", "44" )
test( "5,10L40/22,22B10", "100" )
test( "46,34T34/34,29T14", "30" )
test( "52,75L12/88,69T54", "0" )
test( "67,83B70/99,48T14", "52" )
test( "291,11T120/258,54B130", "424" )
test( "62,170L139/133,172R21", "441" )
test( "98,189B116/183,127R27", "240" )
test( "646,684B96/435,690R772", "0" )
test( "113,668L866/581,859L852", "158404" )
test( "309,321B162/137,420B423", "15750" )
test( "5474,6459R9089/8177,150R5120", "376996" )
test( "2399,1640B2451/1718,2100L1623", "221334" )
test( "5621,8460T7612/2715,5697L8851", "861192" )
[2017/11/06追記]
領域の共通部分のみ探索していたつもりが、していなかったので修正。
結果、2分30秒。
e18_2.rb
def has_point( d, px, py )
x, y, s, h = d
if s[0] == 0
diff = (py - y) * s[1]
return false if diff < 0
return false if h <= diff
return true if (x-diff..x+diff).include?(px)
else
diff = (px - x) * s[0]
return false if diff < 0
return false if h <= diff
return true if (y-diff..y+diff).include?(py)
end
return false
end
DIR = {
'R' => [ -1, 0, ],
'L' => [ 1, 0, ],
'T' => [ 0, 1, ],
'B' => [ 0, -1, ],
}
def solve( input )
deltas = input.split('/').map { |d|
d.scan(/(\d+),(\d+)([RLTB])(\d+)/)
x = $1.to_i
y = $2.to_i
s = DIR[$3]
h = $4.to_i
[ x, y, s, h, ]
}
x_range = deltas.map { |x, y, s, h|
[ x, (s[0]==0) ? [x-(h-2)-1,x+(h-2)+1] : x+(h-1)*s[0] ].flatten.minmax
}.transpose
y_range = deltas.map { |x, y, s, h|
[ y, (s[0]==0) ? y+(h-1)*s[1] : [y-(h-2)-1,y+(h-2)+1] ].flatten.minmax
}.transpose
count = 0
(x_range[0].max).upto(x_range[1].min) { |x|
(y_range[0].max).upto(y_range[1].min) { |y|
count += 1 if deltas.all? { |d| has_point( d, x, y ) }
}
}
count.to_s
end