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