#783042 (Crystal) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	tomerun
提出日時	2022-07-30 15:56:02
言語	Crystal (1.11.2)
結果	AC
実行時間	903 ms / 1,000 ms
コード長	6,012 bytes
コンパイル時間	18,577 ms
実行使用メモリ	6,952 KB
スコア	8,816,798
最終ジャッジ日時	2022-07-30 15:56:51
合計ジャッジ時間	48,581 ms
ジャッジサーバーID （参考情報）	judge11 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	903 ms 6,948 KB
testcase_01	AC	903 ms 5,616 KB
testcase_02	AC	903 ms 6,948 KB
testcase_03	AC	903 ms 5,776 KB
testcase_04	AC	903 ms 5,696 KB
testcase_05	AC	900 ms 6,948 KB
testcase_06	AC	903 ms 6,948 KB
testcase_07	AC	901 ms 6,952 KB
testcase_08	AC	902 ms 5,836 KB
testcase_09	AC	903 ms 5,580 KB
testcase_10	AC	899 ms 5,752 KB
testcase_11	AC	903 ms 5,740 KB
testcase_12	AC	900 ms 6,948 KB
testcase_13	AC	903 ms 5,824 KB
testcase_14	AC	903 ms 5,764 KB
testcase_15	AC	903 ms 6,948 KB
testcase_16	AC	903 ms 6,952 KB
testcase_17	AC	901 ms 5,772 KB
testcase_18	AC	903 ms 5,632 KB
testcase_19	AC	900 ms 5,756 KB
testcase_20	AC	903 ms 5,636 KB
testcase_21	AC	899 ms 5,644 KB
testcase_22	AC	903 ms 5,728 KB
testcase_23	AC	901 ms 6,948 KB
testcase_24	AC	901 ms 5,692 KB
testcase_25	AC	901 ms 6,952 KB
testcase_26	AC	902 ms 6,948 KB
testcase_27	AC	903 ms 5,588 KB
testcase_28	AC	903 ms 6,948 KB
testcase_29	AC	903 ms 5,840 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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, 1000000)
    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)
      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
    # M.times do |i|
    #   i.times do |j|
    #     g[i + N][j + N] = g[j + N][i + N] = dist2(stations[i], stations[j])
    #   end
    # end
    # append_size = 10
    # (N + M).times do |i|
    #   M.times do |j|
    #     g[i] += [g[i][j + N]] * append_size
    #   end
    # end
    # M.times do |i|
    #   append_size.times do
    #     g << g[i + N]
    #   end
    # end
    # path, len = two_opt(g, 1000000)
    # debug("final_len:#{len}")
    # path.map! { |v| v < N + M ? v : (v - (N + M)) // append_size + N }
    # best_res = Result.new(best_stations, path, len)

    return best_res
  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}")
    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 = 5
  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

yukicoder

結果

テストケース

ソースコード