結果

問題 No.5007 Steiner Space Travel
ユーザー tomerun
提出日時 2022-07-30 15:12:38
言語 Crystal
(1.14.0)
結果
AC  
実行時間 903 ms / 1,000 ms
コード長 6,308 bytes
コンパイル時間 19,225 ms
実行使用メモリ 5,868 KB
スコア 8,558,418
最終ジャッジ日時 2022-07-30 15:13:27
合計ジャッジ時間 47,340 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

START_TIME = Time.utc.to_unix_ms
TL = 900
N = 100
M = 8
M0 = (ENV["M0"]? || 91).to_i
INF = 1 << 29
RND = Random.new(2)
struct Pos
property :r, :c
def initialize(@r : Int32, @c : Int32)
end
end
macro debug(msg)
{% if flag?(:local) %}
STDERR.puts({{msg}})
{% end %}
end
macro debugf(format_string, *args)
{% if flag?(:local) %}
STDERR.printf({{format_string}}, {{*args}})
{% end %}
end
def crash(msg, caller_line = __LINE__)
puts "[ERROR] line #{caller_line}: #{msg}"
exit
end
macro assert(cond, msg = "", caller_line = __LINE__)
{% if flag?(:local) %}
if !({{cond}})
crash({{msg}}, {{caller_line}})
end
{% end %}
end
class Result
property :lines, :score
def initialize(@station : Array(Pos), @path : Array(Int32), @score : Int32)
end
def to_s(io)
@station.each do |s|
io << s.r << " " << s.c << "\n"
end
io << @path.size << "\n"
@path.each do |i|
if i >= N
io << 2 << " " << i - N + 1 << "\n"
else
io << 1 << " " << i + 1 << "\n"
end
end
io
end
end
RES_EMPTY = Result.new([] of Pos, [] of Int32, 1 << 30)
def dist2(p0, p1)
return (p0.r - p1.r) ** 2 + (p0.c - p1.c) ** 2
end
class Solver
def initialize(@ps : Array(Pos))
end
def solve(timelimit)
g = Array.new(N) { Array.new(N, 0) }
N.times do |i|
i.times do |j|
g[i][j] = g[j][i] = dist2(@ps[i], @ps[j]) * 25
end
end
base_path, len = two_opt(g, 100000)
best_stations = Array.new(M) { Pos.new(0, 0) }
stations = best_stations.dup
best_res = Result.new(best_stations, base_path.dup, len)
M.times { g << Array.new(N + M, 0) }
N.times { |i| g[i] += [0] * M }
M.times do |i|
stations[i] = Pos.new(RND.rand(801) + 100, RND.rand(801) + 100)
N.times do |j|
g[j][i + N] = g[i + N][j] = dist2(stations[i], @ps[j]) * 5
end
end
turn = 0
begin_time = Time.utc.to_unix_ms
worst_time = 0
while true
if begin_time + worst_time > timelimit
debug("total turn:#{turn}")
break
end
time_ratio = (timelimit - begin_time) / (timelimit - START_TIME)
# M.times do |i|
# M.times do |j|
# g[i + N][j + N] = g[i + N][j + N] = dist2(stations[i], stations[j])
# end
# end
mi = RND.rand(M)
os = stations[mi]
if time_ratio < 0.5
stations[mi] = Pos.new(RND.rand(801) + 100, RND.rand(801) + 100)
else
range = 40
nr = stations[mi].r + RND.rand(range * 2 + 1) - range
nr = 0 if nr < 0
nr = 1000 if nr > 1000
nc = stations[mi].c + RND.rand(range * 2 + 1) - range
nc = 0 if nc < 0
nc = 1000 if nc > 1000
stations[mi] = Pos.new(nr, nc)
end
N.times do |j|
g[j][mi + N] = g[mi + N][j] = dist2(stations[mi], @ps[j]) * 5
end
sum = 0
path = [0]
N.times do |i|
cp = base_path[i]
np = base_path[i + 1]
st = -1
dist = g[cp][np]
M.times do |j|
nd = g[cp][j + N] + g[j + N][np]
if nd < dist
dist = nd
st = j
end
end
sum += dist
if st != -1
path << st + N
end
path << np
end
if sum <= best_res.score
debug("best_score:#{sum} turn:#{turn}")
best_stations = stations.dup
best_res = Result.new(best_stations, path, sum)
else
stations[mi] = os
N.times do |j|
g[j][mi + N] = g[mi + N][j] = dist2(stations[mi], @ps[j]) * 5
end
end
after_time = Time.utc.to_unix_ms
worst_time = {worst_time, after_time - begin_time}.max
begin_time = after_time
turn += 1
end
return best_res
end
def solve_sa(timelimit, len)
initial_cooler = 1.0
final_cooler = 10.0
cooler = initial_cooler
turn = 0
begin_time = Time.utc.to_unix_ms
total_time = timelimit - begin_time
while true
if (turn & 0xF) == 0
cur_time = Time.utc.to_unix_ms
if cur_time > timelimit
debug("turn: #{turn}")
break
end
ratio = (cur_time - begin_time) / total_time
cooler = initial_cooler + (final_cooler - initial_cooler) * ratio
end
new_v = eval(new_hist)
if accept(new_v - cur_v, cooler)
debug("new_v:#{new_v} hist:#{new_hist[0, 16]}")
end
turn += 1
end
return Result.new(best_lines.flatten, cur_v)
end
def two_opt(g, max_turn)
n = g.size
path = n.times.to_a + [0]
score = n.times.sum { |i| g[path[i]][path[i + 1]] }
initial_cooler = 0.000001
final_cooler = 0.0001
cooler = initial_cooler
max_turn.times do |turn|
if (turn & 0xF) == 0
ratio = turn / max_turn
cooler = initial_cooler + (final_cooler - initial_cooler) * ratio
end
pos1 = RND.rand(n - 1) + 1
pos2 = RND.rand(n - 2) + 1
if pos2 >= pos1
pos2 += 1
else
pos1, pos2 = pos2, pos1
end
diff = g[path[pos1 - 1]][path[pos2]] + g[path[pos1]][path[pos2 + 1]] - g[path[pos1 - 1]][path[pos1]] - g[path[pos2]][path[pos2 + 1]]
if accept(diff, cooler)
score += diff
# debug("score:#{score} turn:#{turn}")
while pos1 < pos2
path[pos1], path[pos2] = path[pos2], path[pos1]
pos1 += 1
pos2 -= 1
end
end
end
sum = 0
n.times do |i|
sum += g[path[i]][path[i + 1]]
end
debug("2opt:#{score} #{sum}")
return path, score
end
def accept(diff, cooler)
return true if diff <= 0
v = -diff * cooler
return false if v < -8
# return false
return RND.rand < Math.exp(v)
end
end
def main
read_line
ps = Array.new(N) do
a, b = read_line.split.map(&.to_i)
Pos.new(a, b)
end
solver = Solver.new(ps)
part = 1
best_res = RES_EMPTY
part.times do |i|
res = solver.solve(START_TIME + TL * (i + 1) // part)
if res.score < best_res.score
best_res = res
end
end
print best_res
{% if flag?(:local) %}
final_score = (1_000_000_000 / (1000 + best_res.score ** 0.5)).round.to_i
STDERR.puts("final_score:#{final_score}")
{% end %}
end
main
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0