結果
問題 | No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
START_TIME = Time.utc.to_unix_msTL = 1980N = 50K = 50RND = Random.new(3)macro debug(msg){% if flag?(:local) %}STDERR.puts({{msg}}){% end %}endclass Resultgetter :score, :b, :m, :edef initialize(@score : Float64, @b : Array(Int32), @m : Array(Int32), @e : Array(Int32))endendclass Solver@ts : Array(Int32)@us : Array(Int32)def initializeread_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])endenddef sim_200(b, m, e)p = 0d = 1a = b200.times dop += dif p == a * dd *= -1a = {m, a - e}.maxendendreturn p, denddef sim_k(i, m)K.times do |j|t = (@ts[j] - 200) % (m * 4)p = @pos_200[i]d = @dir_200[i]t.times dop += dif p == m * dd *= -1endend@pos_ts[j][i] = pt = (@us[j] - 200) % (m * 4)p = @pos_200[i]d = @dir_200[i]t.times dop += dif p == m * dd *= -1endend@pos_us[j][i] = pendenddef solvecur_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-4final_cooler = 1e-2cooler = initial_coolerturn = 0begin_time = Time.utc.to_unix_mstotal_time = TL - (begin_time - START_TIME)while trueturn += 1if (turn & 0x3F) == 0elapsed = Time.utc.to_unix_ms - begin_timeif elapsed > total_timedebug("total_turn:#{turn} score:#{best_res.score} norm_score:#{best_res.score * 20_000_000 / (N * (N - 1)) * 10_000_000 / 50}")breakendratio = elapsed / total_timecooler = Math.exp(Math.log(initial_cooler) * (1.0 - ratio) + Math.log(final_cooler) * ratio)endch_i = RND.rand(N)nb = RND.rand(12) + 1if nb == @b[ch_i]nb += 1endnm = RND.rand(nb) + 1 # nb == 1 ? 1 : RND.rand(2) + nb - 1ne = 1 # RND.rand(2) + 1old = {@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]endsim_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 = scorets_ss = new_ts_ss@b[ch_i] = nb@m[ch_i] = nm@e[ch_i] = neif best_res.score < scorebest_res = Result.new(score, @b.dup, @m.dup, @e.dup)endelse@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]endendendreturn best_resenddef accept(diff, cooler)return true if diff >= 0v = cooler * diffreturn false if v < -8return RND.rand < Math.exp(v)enddef calc_scoresum0 = 0.0sum1 = 0.0ts_ss = Array.new(K, 0.0)K.times do |i|sum = 0.0N.times do |j|j.times do |k|sum += (@pos_ts[i][j] - @pos_ts[i][k]).abs / (@b[j] + @b[k])endendts_ss[i] = sumsum0 += summin = 1 << 20max = -(1 << 20)N.times do |j|min = {min, @pos_us[i][j]}.minmax = {max, @pos_us[i][j]}.maxendsum1 += 1.0 / (((max - min) * 0.05) ** 0.5 + 1)end# debug([sum0, sum1, sum0 * sum1])return sum0 * sum1, ts_ssenddef calc_score_diff(ch_i, old_pos, old_b, new_b, ts_ss)sum0 = 0.0sum1 = 0.0new_ts_ss = Array.new(K, 0.0)K.times do |i|sum = ts_ss[i]min = 1 << 20max = -(1 << 20)N.times do |j|min = {min, @pos_us[i][j]}.minmax = {max, @pos_us[i][j]}.maxnext if j == ch_isum += (@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)endnew_ts_ss[i] = sumsum0 += sumsum1 += 1.0 / (((max - min) * 0.05) ** 0.5 + 1)end# debug([sum0, sum1, sum0 * sum1])return sum0 * sum1, new_ts_ssendendsolver = Solver.newres = solver.solveN.times do |i|puts "#{res.b[i]} #{{res.b[i], res.m[i]}.min} #{res.e[i]}"end