結果

問題 No.5007 Steiner Space Travel
ユーザー tomeruntomerun
提出日時 2022-07-30 16:49:02
言語 Crystal
(1.11.2)
結果
AC  
実行時間 903 ms / 1,000 ms
コード長 7,122 bytes
コンパイル時間 19,060 ms
実行使用メモリ 6,952 KB
スコア 8,909,170
最終ジャッジ日時 2022-07-30 16:49:51
合計ジャッジ時間 45,906 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 903 ms
6,948 KB
testcase_01 AC 902 ms
6,948 KB
testcase_02 AC 900 ms
6,952 KB
testcase_03 AC 902 ms
6,952 KB
testcase_04 AC 899 ms
5,592 KB
testcase_05 AC 902 ms
6,952 KB
testcase_06 AC 902 ms
6,952 KB
testcase_07 AC 902 ms
5,760 KB
testcase_08 AC 901 ms
6,952 KB
testcase_09 AC 903 ms
5,756 KB
testcase_10 AC 903 ms
5,784 KB
testcase_11 AC 900 ms
6,948 KB
testcase_12 AC 903 ms
5,828 KB
testcase_13 AC 899 ms
5,772 KB
testcase_14 AC 902 ms
5,660 KB
testcase_15 AC 902 ms
5,624 KB
testcase_16 AC 902 ms
6,948 KB
testcase_17 AC 902 ms
5,788 KB
testcase_18 AC 903 ms
5,596 KB
testcase_19 AC 900 ms
5,664 KB
testcase_20 AC 899 ms
5,756 KB
testcase_21 AC 903 ms
5,596 KB
testcase_22 AC 901 ms
6,952 KB
testcase_23 AC 903 ms
5,692 KB
testcase_24 AC 902 ms
6,948 KB
testcase_25 AC 902 ms
5,820 KB
testcase_26 AC 902 ms
5,660 KB
testcase_27 AC 903 ms
6,948 KB
testcase_28 AC 903 ms
6,948 KB
testcase_29 AC 901 ms
5,796 KB
権限があれば一括ダウンロードができます

ソースコード

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, 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
    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
    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.5
        stations[mi] = Pos.new(RND.rand(801) + 100, RND.rand(801) + 100)
      else
        range = time_ratio < 0.8 ? 40 : 8
        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]
        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
          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)
      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
    # 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
0