結果

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

ソースコード

diff # 

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

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 = 0.3
  turn = 0
  while true
    if (turn & 0xFFF) == 0
      cur_time = Time.utc.to_unix_ms
      if cur_time > tl
        debug("turn: #{turn}")
        break
      end
    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