結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー tomerun
提出日時 2022-10-14 23:07:36
言語 Crystal
(1.14.0)
結果
AC  
実行時間 1,918 ms / 2,000 ms
コード長 3,567 bytes
コンパイル時間 17,168 ms
実行使用メモリ 6,952 KB
スコア 1,034,744,975,720,968
最終ジャッジ日時 2022-10-14 23:09:42
合計ジャッジ時間 122,104 ms
ジャッジサーバーID
(参考情報)
judge10 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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

START_TIME = Time.utc.to_unix_ms
TL = 1900
N = 50
K = 50
RND = Random.new(2)
macro debug(msg)
{% if flag?(:local) %}
STDERR.puts({{msg}})
{% end %}
end
class Result
getter :score, :b, :m, :e
def initialize(@score : Int64, @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(1) + 1 }
@m = Array(Int32).new(N) { |i| {RND.rand(2) + 1, @b[i]}.min }
@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(N) { Array.new(K, 0) }
@pos_us = Array(Array(Int32)).new(N) { Array.new(K, 0) }
N.times do |i|
sim_k(i)
end
end
def sim_200(b, m, e)
m = {b, m}.min
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)
K.times do |j|
t = (@ts[j] - 200) % (@m[i] * 4)
p = @pos_200[i]
d = @dir_200[i]
t.times do
p += d
if p == @m[i] * d
d *= -1
end
end
@pos_ts[i][j] = p
t = (@us[j] - 200) % (@m[i] * 4)
p = @pos_200[i]
d = @dir_200[i]
t.times do
p += d
if p == @m[i] * d
d *= -1
end
end
@pos_us[i][j] = p
end
end
def solve
best_res = Result.new(calc_score(), @b.dup, @m.dup, @e.dup)
buf_pos_ts = Array.new(K, 0)
buf_pos_us = Array.new(K, 0)
turn = 0
while true
turn += 1
if (turn & 0x3F) == 0
if Time.utc.to_unix_ms - START_TIME > TL
debug("total_turn:#{turn} score:#{best_res.score}")
break
end
end
ch_i = RND.rand(N)
nb = RND.rand(13) + 1
nm = {RND.rand(13) + 1, nb}.min
ne = 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[ch_i][i]
buf_pos_us[i] = @pos_us[ch_i][i]
end
sim_k(ch_i)
score = calc_score()
if best_res.score < score
debug("score:#{score} at turn #{turn}")
@b[ch_i] = nb
@m[ch_i] = nm
@e[ch_i] = ne
best_res = Result.new(score, @b.dup, @m.dup, @e.dup)
else
@pos_200[ch_i] = old[0]
@dir_200[ch_i] = old[1]
K.times do |i|
@pos_ts[ch_i][i] = buf_pos_ts[i]
@pos_us[ch_i][i] = buf_pos_us[i]
end
end
end
return best_res
end
def calc_score
sum0 = 0i64
sum1 = 0i64
K.times do |i|
sum = 0.0
N.times do |j|
j.times do |k|
sum += (@pos_ts[j][i] - @pos_ts[k][i]).abs / (@b[j] + @b[k])
end
end
sum0 += (sum * 20_000_000 / (N * (N - 1))).round.to_i
min = 1 << 20
max = -(1 << 20)
N.times do |j|
min = {min, @pos_us[j][i]}.min
max = {max, @pos_us[j][i]}.max
end
sum1 += (10_000_000 / (((max - min) * 0.05) ** 0.5 + 1)).round.to_i
end
debug([sum0, sum1, sum0 * sum1])
return sum0 * sum1
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