結果
問題 | No.168 ものさし |
ユーザー | snipsnipsnip |
提出日時 | 2015-03-28 15:44:51 |
言語 | Ruby (3.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,252 bytes |
コンパイル時間 | 59 ms |
コンパイル使用メモリ | 11,316 KB |
実行使用メモリ | 23,592 KB |
最終ジャッジ日時 | 2023-09-11 10:46:22 |
合計ジャッジ時間 | 5,373 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 296 ms
17,424 KB |
testcase_01 | WA | - |
testcase_02 | RE | - |
testcase_03 | WA | - |
testcase_04 | AC | 82 ms
15,060 KB |
testcase_05 | AC | 85 ms
15,368 KB |
testcase_06 | AC | 84 ms
15,172 KB |
testcase_07 | AC | 85 ms
15,320 KB |
testcase_08 | AC | 85 ms
15,372 KB |
testcase_09 | AC | 88 ms
15,396 KB |
testcase_10 | AC | 96 ms
15,448 KB |
testcase_11 | AC | 209 ms
17,064 KB |
testcase_12 | AC | 254 ms
21,140 KB |
testcase_13 | AC | 298 ms
23,592 KB |
testcase_14 | AC | 128 ms
23,268 KB |
testcase_15 | AC | 86 ms
15,056 KB |
testcase_16 | AC | 86 ms
15,536 KB |
testcase_17 | AC | 94 ms
15,348 KB |
testcase_18 | AC | 95 ms
15,780 KB |
testcase_19 | AC | 225 ms
23,256 KB |
testcase_20 | AC | 179 ms
23,404 KB |
testcase_21 | AC | 729 ms
23,284 KB |
testcase_22 | AC | 482 ms
23,544 KB |
コンパイルメッセージ
Syntax OK
ソースコード
require 'set' Problem168 = Struct.new(:points) do def solve @distance_cache = [] @grid = Grid.new(points) w = isqrt(squared_distance_by_index(0, points.size - 1)) / 10 longest = ((w + 1) * 10) ** 2 shortest = -1 p 10 * (1..w + 1).bsearch {|d| len = d * 10 sqlen = len ** 2 next true if longest <= sqlen next false if sqlen < shortest if minmax = reach(len, sqlen) longest = minmax[1] if minmax[1] < longest shortest = minmax[0] if shortest < minmax[0] end !!minmax } end private def isqrt(x) (1..x).bsearch {|r| x <= r ** 2 } end def reach(len, sqlen) goal = points.size - 1 stack = [0] todo = Set.new(1..goal) longest = -1 shortest = 1 / 0.0 while i = stack.pop each_neighbor(i, len, sqlen, todo) do |j, distance| longest = distance if longest < distance shortest = distance if distance < shortest return shortest, longest if j.equal?(goal) stack << j end end nil end def each_neighbor(i, len, sqlen, todo) @grid.each_neighbor(i, len) do |j| next unless todo.include?(j) distance = squared_distance_by_index(i, j) if distance <= sqlen yield j, distance todo.delete j end end end def squared_distance_by_index(ia, ib) ia, ib = ib, ia if ib < ia @distance_cache[ia * points.size + ib] ||= squared_distance(points[ia], points[ib]) end def squared_distance(a, b) ax, ay = a bx, by = b (ax - bx) ** 2 + (ay - by) ** 2 end end class Grid def initialize(points) @n = 5 @ax, @ay, @bx, @by = aabb(points) @w = @bx - @ax @h = @by - @ay @cellw = @w / @n.to_r @cellh = @h / @n.to_r @points = points @bucket_of = points.map {|pt| which_bucket pt } @buckets = Array.new(@n * @n) { [] } @bucket_of.each_with_index {|b, i| @buckets[b] << i } end def aabb(points) ax = ay = bx = by = nil points.each do |x, y| ax = x if !ax || ax > x ay = y if !ay || ay > y bx = x if !bx || bx < x by = y if !by || by < y end return ax, ay, bx, by end def which_bucket(point) x, y = point [(y - @ay) * @n / @h, @n - 1].min * @n + [(x - @ax) * @n / @w, @n - 1].min end def each_neighbor(ipoint, radius) each_neighbor_bucket(ipoint, radius) do |bucket| @buckets[bucket].each {|i| yield i } end end def each_neighbor_bucket(ipoint, radius) bw = [(radius / @cellw).ceil, @n / 2].min bh = [(radius / @cellh).ceil, @n / 2].min b = @bucket_of[ipoint] bx = b % @n yield b (1..bw).each do |dx| yield b - dx if bx >= dx yield b + dx if bx + dx < @n end (1..bh).each do |dy| if (bpy = b - dy * @n) >= 0 yield bpy (1..bw).each do |dx| yield bpy - dx if bx >= dx yield bpy + dx if bx + dx < @n end end if (bpy = b + dy * @n) < @n * @n yield bpy (1..bw).each do |dx| yield bpy - dx if bx >= dx yield bpy + dx if bx + dx < @n end end end end end Problem168.new((1..gets.to_i).map{gets.split.map(&:to_i)}).solve