#783388 (Crystal) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: tomerun
• 提出日時: 2022-07-30 17:54:05
• 言語: Crystal (1.14.0)
• 結果: AC
• 実行時間: 988 ms / 1,000 ms
• コード長: 8,367 bytes
• コンパイル時間: 19,345 ms
• 実行使用メモリ: 6,952 KB
• スコア: 8,922,539
• 最終ジャッジ日時: 2022-07-30 17:54:57
• 合計ジャッジ時間: 51,713 ms
• ジャッジサーバーID （参考情報）: judge15 / judge10

ファイルパターン	結果
other	AC * 30

ソースコード

START_TIME = Time.utc.to_unix_ms
TL         = 930
N          = 100
M          =   8
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 :path, :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, N.times.to_a + [0])
    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
    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
    best_mi = Array.new(N, -1)
    best_mi_buf = Array.new(N, -1)
    turn = 0
    begin_time = Time.utc.to_unix_ms
    init_time = begin_time
    worst_time = 0
    while true
      if begin_time + worst_time > timelimit
        debug("total turn:#{turn}")
        break
      end
      time_ratio = 1.0 - (timelimit - begin_time) / (timelimit - init_time)
      mi = RND.rand(M)
      os = stations[mi]
      if time_ratio < 0.8
        stations[mi] = Pos.new(RND.rand(801) + 100, RND.rand(801) + 100)
      else
        range = time_ratio < 0.9 ? 20 : 4
        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
      M.times do |j|
        g[j + N][mi + N] = g[mi + N][j + N] = dist2(stations[mi], stations[j])
      end

      sum = 0
      path = [0]
      N.times do |i|
        cp = base_path[i]
        np = base_path[i + 1]
        st = -1
        dist = g[cp][np]
        if best_mi[i] == mi
          M.times do |j|
            nd = g[cp][j + N] + g[j + N][np]
            if nd < dist
              dist = nd
              st = j
            end
          end
        elsif best_mi[i] == -1
          nd = g[cp][mi + N] + g[mi + N][np]
          if nd < dist
            st = mi
          end
        else
          nd = g[cp][mi + N] + g[mi + N][np]
          if nd < g[cp][best_mi[i] + N] + g[best_mi[i] + N][np]
            st = mi
          else
            st = best_mi[i]
          end
        end
        best_mi_buf[i] = st

        if st != -1
          msi = -1
          M.times do |j|
            next if j == st
            if g[cp][j + N] + g[j + N][st + N] < g[cp][st + N]
              msi = j
              break
            end
          end
          if msi != -1
            sum += g[path[-1]][msi + N]
            path << msi + N
          end
          sum += g[path[-1]][st + N]
          path << st + N
          msi = -1
          M.times do |j|
            next if j == st
            if g[st + N][j + N] + g[j + N][np] < g[st + N][np]
              msi = j
              break
            end
          end
          if msi != -1
            sum += g[path[-1]][msi + N]
            path << msi + N
          end
        end
        sum += g[path[-1]][np]
        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)
        best_mi, best_mi_buf = best_mi_buf, best_mi
      else
        stations[mi] = os
        N.times do |j|
          g[j][mi + N] = g[mi + N][j] = dist2(stations[mi], @ps[j]) * 5
        end
        M.times do |j|
          g[j + N][mi + N] = g[mi + N][j + N] = dist2(stations[mi], stations[j])
        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
    cnt = best_res.path.tally
    append_size = {1, M.times.max_of { |i| cnt[i + N] }}.max
    debug("append_size:#{append_size}")
    (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
    last_path = [] of Int32
    used = Array.new(N + M, 0)
    best_res.path.each do |v|
      if used[v] == 0 || v == 0
        last_path << v
        used[v] += 1
      else
        last_path << N + M + append_size * (v - N) + used[v] - 1
        used[v] += 1
        if used[v] == cnt[v]
          while used[v] <= append_size
            last_path << N + M + append_size * (v - N) + used[v] - 1
            used[v] += 1
          end
        end
      end
    end

    debug("last_path.size:#{last_path.size}")
    debug("g.size:#{g.size} g.each.min:#{g.min_of { |row| row.size }}")
    path, len = two_opt(g, 1000000, last_path)
    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, initial_path)
    n = g.size
    path = initial_path.dup
    score = (path.size - 1).times.sum { |i| g[path[i]][path[i + 1]] }
    initial_cooler = 0.000001
    final_cooler = 0.0001
    cooler = initial_cooler
    best_score = score
    best_path = path
    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
        if score < best_score
          best_score = score
          best_path = path.dup
        end
        # debug("score:#{score} turn:#{turn}")
        while pos1 < pos2
          path[pos1], path[pos2] = path[pos2], path[pos1]
          pos1 += 1
          pos2 -= 1
        end
      end
    end
    debug("2opt:#{best_score}")
    return best_path, best_score
  end

  def accept(diff, cooler)
    return true if diff <= 0
    v = -diff * cooler
    return false if v < -8
    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