結果

問題 No.1775 Love Triangle 2
ユーザー tomerun
提出日時 2021-12-05 17:55:54
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 3,211 bytes
コンパイル時間 14,926 ms
コンパイル使用メモリ 296,060 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-07 08:38:54
合計ジャッジ時間 674,983 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 WA * 75
権限があれば一括ダウンロードができます

ソースコード

diff # 

START_TIME     = Time.utc.to_unix_ms
TL             = 7500
INF            = 1 << 28
RND            = Random.new(2)
INITIAL_COOLER = 0.1
FINAL_COOLER   = 1.0

macro debug(msg)
  {% if flag?(:local) %}
    STDERR.puts({{msg}})
  {% end %}
end

main

def main
  n, m = read_line.split.map(&.to_i)
  x, y, z = read_line.split.map { |i| i.to_i - 1 }
  g = Array.new(n) { [false] * n }
  m.times do
    a, b = read_line.split.map(&.to_i)
    g[a - 1][b - 1] = g[b - 1][a - 1] = true
  end
  puts solve(x, y, z, g, START_TIME + TL)
end

def solve(x, y, z, g, tl)
  n = g.size
  wait = (0...n).select { |i| ![x, y, z].includes?(i) }
  best_ans = INF
  ratio_pena = 1
  score_pena = 3
  ps = [x, y, z]
  cooler = INITIAL_COOLER
  turn = 0
  begin_time = Time.utc.to_unix_ms
  while true
    if (turn & 0xFFF) == 0
      break if best_ans == n
      cur_time = Time.utc.to_unix_ms
      if cur_time > tl
        debug("turn: #{turn}")
        break
      end
      ratio = (cur_time - begin_time) / (tl - begin_time)
      cooler = Math.exp((1.0 - ratio) * INITIAL_COOLER + ratio * FINAL_COOLER)
    end
    pos = RND.rand(ps.size)
    if ps[pos] == x || ps[pos] == y || ps[pos] == z
      ope = 1
    else
      ope = RND.rand(3)
    end
    np = pos == ps.size - 1 ? 0 : pos + 1
    case ope
    when 0 # remove
      diff_pena = 0
      diff_pena -= 1 if g[ps[pos]][ps[np]]
      diff_pena -= 1 if g[ps[pos]][ps[pos - 1]]
      diff_pena += 1 if g[ps[pos - 1]][ps[np]]
      diff = diff_pena * ratio_pena - 1
      if accept(diff, cooler)
        score_pena += diff_pena
        wait << ps[pos]
        ps.delete_at(pos)
        if score_pena == 0 && ps.size < best_ans
          best_ans = ps.size
        end
        debug("remove #{score_pena} #{ps.size} #{turn}")
        debug("#{ps}")
      end
    when 1 # insert
      next if wait.empty?
      ip = RND.rand(wait.size)
      ins = wait[ip]
      diff_pena = 0
      diff_pena -= 1 if g[ps[pos]][ps[np]]
      diff_pena += 1 if g[ins][ps[np]]
      diff_pena += 1 if g[ins][ps[pos]]
      diff = diff_pena * ratio_pena + 1
      if accept(diff, cooler)
        score_pena += diff_pena
        wait[ip], wait[-1] = wait[-1], wait[ip]
        wait.pop
        ps.insert(pos + 1, ins)
        if score_pena == 0 && ps.size < best_ans
          best_ans = ps.size
        end
        debug("insert #{score_pena} #{ps.size} #{turn}")
        debug("#{ps}")
      end
    when 2 # swap
      next if wait.empty?
      ip = RND.rand(wait.size)
      ins = wait[ip]
      diff_pena = 0
      diff_pena -= 1 if g[ps[pos]][ps[np]]
      diff_pena -= 1 if g[ps[pos]][ps[pos - 1]]
      diff_pena += 1 if g[ins][ps[np]]
      diff_pena += 1 if g[ins][ps[pos - 1]]
      diff = diff_pena * ratio_pena
      if accept(diff, cooler)
        score_pena += diff_pena
        wait[ip] = ps[pos]
        ps[pos] = ins
        if score_pena == 0 && ps.size < best_ans
          best_ans = ps.size
        end
        debug("swap #{score_pena} #{ps.size} #{turn}")
        debug("#{ps}")
      end
    end
    turn += 1
  end
  return best_ans == INF ? -1 : best_ans
end

def accept(diff, cooler)
  return true if diff <= 0
  v = -diff * cooler
  return RND.rand < Math.exp(v)
end
0