結果

問題 No.1775 Love Triangle 2
ユーザー tomeruntomerun
提出日時 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0