結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー tomerun
提出日時 2022-10-15 00:38:28
言語 Crystal
(1.14.0)
結果
AC  
実行時間 1,986 ms / 2,000 ms
コード長 5,035 bytes
コンパイル時間 20,325 ms
実行使用メモリ 6,952 KB
スコア 1,469,920,803,057,454
最終ジャッジ日時 2022-10-15 00:40:39
合計ジャッジ時間 129,286 ms
ジャッジサーバーID
(参考情報)
judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

START_TIME = Time.utc.to_unix_ms
TL = 1980
N = 50
K = 50
RND = Random.new(3)
macro debug(msg)
{% if flag?(:local) %}
STDERR.puts({{msg}})
{% end %}
end
class Result
getter :score, :b, :m, :e
def initialize(@score : Float64, @b : Array(Int32), @m : Array(Int32), @e : Array(Int32))
end
end
class Solver
@ts : Array(Int32)
@us : Array(Int32)
def initialize
read_line
@ts = read_line.split.map(&.to_i)
@us = read_line.split.map(&.to_i)
@b = Array(Int32).new(N) { RND.rand(11) + 1 }
@m = Array(Int32).new(N) { |i| @b[i] }
@e = Array(Int32).new(N) { RND.rand(2) + 1 }
@pos_200 = Array(Int32).new(N, 0)
@dir_200 = Array(Int32).new(N, 1)
N.times do |i|
@pos_200[i], @dir_200[i] = sim_200(@b[i], @m[i], @e[i])
end
@pos_ts = Array(Array(Int32)).new(K) { Array.new(N, 0) }
@pos_us = Array(Array(Int32)).new(K) { Array.new(N, 0) }
N.times do |i|
sim_k(i, @m[i])
end
end
def sim_200(b, m, e)
p = 0
d = 1
a = b
200.times do
p += d
if p == a * d
d *= -1
a = {m, a - e}.max
end
end
return p, d
end
def sim_k(i, m)
K.times do |j|
t = (@ts[j] - 200) % (m * 4)
p = @pos_200[i]
d = @dir_200[i]
t.times do
p += d
if p == m * d
d *= -1
end
end
@pos_ts[j][i] = p
t = (@us[j] - 200) % (m * 4)
p = @pos_200[i]
d = @dir_200[i]
t.times do
p += d
if p == m * d
d *= -1
end
end
@pos_us[j][i] = p
end
end
def solve
cur_score, ts_ss = calc_score()
best_res = Result.new(cur_score, @b.dup, @m.dup, @e.dup)
buf_pos_ts = Array.new(K, 0)
buf_pos_us = Array.new(K, 0)
initial_cooler = 1e-4
final_cooler = 1e-2
cooler = initial_cooler
turn = 0
begin_time = Time.utc.to_unix_ms
total_time = TL - (begin_time - START_TIME)
while true
turn += 1
if (turn & 0x3F) == 0
elapsed = Time.utc.to_unix_ms - begin_time
if elapsed > total_time
debug("total_turn:#{turn} score:#{best_res.score} norm_score:#{best_res.score * 20_000_000 / (N * (N - 1)) * 10_000_000 / 50}")
break
end
ratio = elapsed / total_time
cooler = Math.exp(Math.log(initial_cooler) * (1.0 - ratio) + Math.log(final_cooler) * ratio)
end
ch_i = RND.rand(N)
nb = RND.rand(12) + 1
if nb == @b[ch_i]
nb += 1
end
nm = RND.rand(nb) + 1 # nb == 1 ? 1 : RND.rand(2) + nb - 1
ne = 1 # RND.rand(2) + 1
old = {@pos_200[ch_i], @dir_200[ch_i]}
@pos_200[ch_i], @dir_200[ch_i] = sim_200(nb, nm, ne)
K.times do |i|
buf_pos_ts[i] = @pos_ts[i][ch_i]
buf_pos_us[i] = @pos_us[i][ch_i]
end
sim_k(ch_i, nm)
score, new_ts_ss = calc_score_diff(ch_i, buf_pos_ts, @b[ch_i], nb, ts_ss)
if accept(score - cur_score, cooler)
debug("score:#{score} at turn #{turn}")
cur_score = score
ts_ss = new_ts_ss
@b[ch_i] = nb
@m[ch_i] = nm
@e[ch_i] = ne
if best_res.score < score
best_res = Result.new(score, @b.dup, @m.dup, @e.dup)
end
else
@pos_200[ch_i] = old[0]
@dir_200[ch_i] = old[1]
K.times do |i|
@pos_ts[i][ch_i] = buf_pos_ts[i]
@pos_us[i][ch_i] = buf_pos_us[i]
end
end
end
return best_res
end
def accept(diff, cooler)
return true if diff >= 0
v = cooler * diff
return false if v < -8
return RND.rand < Math.exp(v)
end
def calc_score
sum0 = 0.0
sum1 = 0.0
ts_ss = Array.new(K, 0.0)
K.times do |i|
sum = 0.0
N.times do |j|
j.times do |k|
sum += (@pos_ts[i][j] - @pos_ts[i][k]).abs / (@b[j] + @b[k])
end
end
ts_ss[i] = sum
sum0 += sum
min = 1 << 20
max = -(1 << 20)
N.times do |j|
min = {min, @pos_us[i][j]}.min
max = {max, @pos_us[i][j]}.max
end
sum1 += 1.0 / (((max - min) * 0.05) ** 0.5 + 1)
end
# debug([sum0, sum1, sum0 * sum1])
return sum0 * sum1, ts_ss
end
def calc_score_diff(ch_i, old_pos, old_b, new_b, ts_ss)
sum0 = 0.0
sum1 = 0.0
new_ts_ss = Array.new(K, 0.0)
K.times do |i|
sum = ts_ss[i]
min = 1 << 20
max = -(1 << 20)
N.times do |j|
min = {min, @pos_us[i][j]}.min
max = {max, @pos_us[i][j]}.max
next if j == ch_i
sum += (@pos_ts[i][j] - @pos_ts[i][ch_i]).abs / (@b[j] + new_b)
sum -= (@pos_ts[i][j] - old_pos[i]).abs / (@b[j] + old_b)
end
new_ts_ss[i] = sum
sum0 += sum
sum1 += 1.0 / (((max - min) * 0.05) ** 0.5 + 1)
end
# debug([sum0, sum1, sum0 * sum1])
return sum0 * sum1, new_ts_ss
end
end
solver = Solver.new
res = solver.solve
N.times do |i|
puts "#{res.b[i]} #{{res.b[i], res.m[i]}.min} #{res.e[i]}"
end
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0