結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
START_TIME = Time.utc.to_unix_msTL = 900N = 100M = 8M0 = (ENV["M0"]? || 91).to_iINF = 1 << 29RND = Random.new(2)struct Posproperty :r, :cdef initialize(@r : Int32, @c : Int32)endendmacro debug(msg){% if flag?(:local) %}STDERR.puts({{msg}}){% end %}endmacro debugf(format_string, *args){% if flag?(:local) %}STDERR.printf({{format_string}}, {{*args}}){% end %}enddef crash(msg, caller_line = __LINE__)puts "[ERROR] line #{caller_line}: #{msg}"exitendmacro assert(cond, msg = "", caller_line = __LINE__){% if flag?(:local) %}if !({{cond}})crash({{msg}}, {{caller_line}})end{% end %}endclass Resultproperty :lines, :scoredef initialize(@station : Array(Pos), @path : Array(Int32), @score : Int32)enddef to_s(io)@station.each do |s|io << s.r << " " << s.c << "\n"endio << @path.size << "\n"@path.each do |i|if i >= Nio << 2 << " " << i - N + 1 << "\n"elseio << 1 << " " << i + 1 << "\n"endendioendendRES_EMPTY = Result.new([] of Pos, [] of Int32, 1 << 30)def dist2(p0, p1)return (p0.r - p1.r) ** 2 + (p0.c - p1.c) ** 2endclass Solverdef initialize(@ps : Array(Pos))enddef 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]) * 25endendbase_path, len = two_opt(g, 100000)best_stations = Array.new(M) { Pos.new(0, 0) }stations = best_stations.dupbest_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]) * 5endendturn = 0begin_time = Time.utc.to_unix_msworst_time = 0while trueif begin_time + worst_time > timelimitdebug("total turn:#{turn}")breakendtime_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# endmi = RND.rand(M)os = stations[mi]if time_ratio < 0.5stations[mi] = Pos.new(RND.rand(801) + 100, RND.rand(801) + 100)elserange = 40nr = stations[mi].r + RND.rand(range * 2 + 1) - rangenr = 0 if nr < 0nr = 1000 if nr > 1000nc = stations[mi].c + RND.rand(range * 2 + 1) - rangenc = 0 if nc < 0nc = 1000 if nc > 1000stations[mi] = Pos.new(nr, nc)endN.times do |j|g[j][mi + N] = g[mi + N][j] = dist2(stations[mi], @ps[j]) * 5endsum = 0path = [0]N.times do |i|cp = base_path[i]np = base_path[i + 1]st = -1dist = g[cp][np]M.times do |j|nd = g[cp][j + N] + g[j + N][np]if nd < distdist = ndst = jendendsum += distif st != -1path << st + Nendpath << npendif sum <= best_res.scoredebug("best_score:#{sum} turn:#{turn}")best_stations = stations.dupbest_res = Result.new(best_stations, path, sum)elsestations[mi] = osN.times do |j|g[j][mi + N] = g[mi + N][j] = dist2(stations[mi], @ps[j]) * 5endendafter_time = Time.utc.to_unix_msworst_time = {worst_time, after_time - begin_time}.maxbegin_time = after_timeturn += 1endreturn best_resenddef solve_sa(timelimit, len)initial_cooler = 1.0final_cooler = 10.0cooler = initial_coolerturn = 0begin_time = Time.utc.to_unix_mstotal_time = timelimit - begin_timewhile trueif (turn & 0xF) == 0cur_time = Time.utc.to_unix_msif cur_time > timelimitdebug("turn: #{turn}")breakendratio = (cur_time - begin_time) / total_timecooler = initial_cooler + (final_cooler - initial_cooler) * ratioendnew_v = eval(new_hist)if accept(new_v - cur_v, cooler)debug("new_v:#{new_v} hist:#{new_hist[0, 16]}")endturn += 1endreturn Result.new(best_lines.flatten, cur_v)enddef two_opt(g, max_turn)n = g.sizepath = n.times.to_a + [0]score = n.times.sum { |i| g[path[i]][path[i + 1]] }initial_cooler = 0.000001final_cooler = 0.0001cooler = initial_coolermax_turn.times do |turn|if (turn & 0xF) == 0ratio = turn / max_turncooler = initial_cooler + (final_cooler - initial_cooler) * ratioendpos1 = RND.rand(n - 1) + 1pos2 = RND.rand(n - 2) + 1if pos2 >= pos1pos2 += 1elsepos1, pos2 = pos2, pos1enddiff = 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 < pos2path[pos1], path[pos2] = path[pos2], path[pos1]pos1 += 1pos2 -= 1endendendsum = 0n.times do |i|sum += g[path[i]][path[i + 1]]enddebug("2opt:#{score} #{sum}")return path, scoreenddef accept(diff, cooler)return true if diff <= 0v = -diff * coolerreturn false if v < -8# return falsereturn RND.rand < Math.exp(v)endenddef mainread_lineps = Array.new(N) doa, b = read_line.split.map(&.to_i)Pos.new(a, b)endsolver = Solver.new(ps)part = 1best_res = RES_EMPTYpart.times do |i|res = solver.solve(START_TIME + TL * (i + 1) // part)if res.score < best_res.scorebest_res = resendendprint best_res{% if flag?(:local) %}final_score = (1_000_000_000 / (1000 + best_res.score ** 0.5)).round.to_iSTDERR.puts("final_score:#{final_score}"){% end %}endmain