結果

問題 No.1775 Love Triangle 2
ユーザー tomeruntomerun
提出日時 2021-12-05 17:40:10
言語 Crystal
(1.11.2)
結果
WA  
実行時間 -
コード長 2,941 bytes
コンパイル時間 21,807 ms
コンパイル使用メモリ 257,664 KB
実行使用メモリ 5,300 KB
最終ジャッジ日時 2023-09-21 14:33:18
合計ジャッジ時間 707,525 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7,502 ms
4,588 KB
testcase_01 AC 7,503 ms
4,580 KB
testcase_02 AC 7,502 ms
4,596 KB
testcase_03 AC 7,503 ms
4,660 KB
testcase_04 AC 7,503 ms
4,768 KB
testcase_05 AC 7,503 ms
4,676 KB
testcase_06 AC 7,503 ms
4,684 KB
testcase_07 AC 7,502 ms
5,064 KB
testcase_08 AC 7,503 ms
4,632 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 7,502 ms
5,200 KB
testcase_18 AC 7,503 ms
4,824 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 7,503 ms
4,672 KB
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 WA -
testcase_65 WA -
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 WA -
testcase_72 WA -
testcase_73 WA -
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 WA -
testcase_79 WA -
testcase_80 WA -
testcase_81 WA -
testcase_82 WA -
testcase_83 WA -
testcase_84 WA -
testcase_85 WA -
testcase_86 WA -
testcase_87 WA -
testcase_88 WA -
testcase_89 WA -
権限があれば一括ダウンロードができます

ソースコード

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