START_TIME = Time.utc.to_unix_ms TL = (ENV["TL"]? || 1000).to_i INF = 1 << 28 H = 60 W = 25 RND = Random.new(2) macro debug(msg) {% if flag?(:trace) %} STDERR.puts({{msg}}) {% end %} end macro debugf(format_string, *args) {% if flag?(:trace) %} STDERR.printf({{format_string}}, {{*args}}) {% end %} end def crash(msg, caller_line = __LINE__) STDERR.puts "[ERROR] line #{caller_line}: #{msg}" exit end macro assert(cond, msg = "", caller_line = __LINE__) {% if flag?(:local) %} if !({{cond}}) crash({{msg}}, {{caller_line}}) end {% end %} end record Spawn, h : Int32, p : Int32, x : Int32 class Enemy property :h getter :p, :ih def initialize(@h : Int32, @p : Int32) @ih = @h end end class OnlineJudge def input n = read_line.to_i return nil if n == -1 return Array.new(n) do h, p, x = read_line.split.map(&.to_i) Spawn.new(h, p, x) end end def output(dir) puts "SRL"[dir] STDOUT.flush end end class LocalJudge @p : Array(Int32) def initialize @p = read_line.split.map(&.to_i) @enemies = Array(Array(Enemy?)).new(W) { Array(Enemy?).new(H, nil) } @player = 12 @exp = 0 @turn = 0 @defeat = false @score = 0 end def input W.times do |i| @enemies[i][0..(H - 2)] = @enemies[i][1..] @enemies[i][-1] = nil end if @enemies[@player][0] @defeat = true end if @defeat debug("defeat at turn #{@turn}") return nil end n = read_line.to_i ret = [] of Spawn n.times do h, p, x = read_line.split.map(&.to_i) @enemies[x][H - 1] = Enemy.new(h, p) ret << Spawn.new(h, p, x) end @turn += 1 return ret end def output(dir) @player += dir + W @player %= W if @enemies[@player][0] @defeat = true else 1.upto(H - 1) do |i| if e = @enemies[@player][i] e.h -= @exp // 100 + 1 if e.h <= 0 @exp += e.p @score += e.ih @enemies[@player][i] = nil end break end end end end def print printf("score=%d\n", @score) end end ##################### # end of template/lib ##################### main def main judge = OnlineJudge.new {% if flag?(:local) %} judge = LocalJudge.new {% end %} solver = Solver.new(judge) solver.solve {% if flag?(:local) %} judge.as(LocalJudge).print {% end %} end class Solver(Judge) def initialize(@judge : Judge) @es = Array(Array(Enemy?)).new(W) { Array(Enemy?).new(H, nil) } @px = 12 @exp = 0 @atk = 1 @turn = 0 @score = 0 @spawn_cnt = Array(Int32).new(W, 0) end def solve 1000.times do ss = @judge.input if !ss debug("score:#{@exp}") return end W.times do |x| @es[x].rotate!(1) @es[x][H - 1] = nil end ss.each do |s| @es[s.x][H - 1] = Enemy.new(s.h, s.p) @spawn_cnt[s.x] += 1 end move = select_move() @px = mv(@px, move) if @es[@px][0].nil? 1.upto(H - 1) do |y| if e = @es[@px][y] debug("attack (#{@px},#{y}) #{e.h}->#{e.h - @atk}") e.h -= @atk if e.h <= 0 @exp += e.p @score += e.ih @atk = 1 + @exp // 100 @es[@px][y] = nil end break end end end @judge.output(move) @turn += 1 end debug("score:#{@score}") end def spawn_cnt_bonus(x) p = (@spawn_cnt[x] + 40) / (@turn + 1000) return p * 0.001 * (@turn ** 1.5) end def near_bonus(y) return 0.0005 / (y + 1) * (@turn ** 1.8) end def select_move debug("x:#{@px}") best_v = 0.0 best_move = 0 need = 0 sum = 0 exp = @exp + 100 1.upto(H - 1) do |ey| if e = @es[@px][ey] need += (e.h + exp // 100 - 1) // (exp // 100) break if need > ey dy_b = 0.0 if exp < 2000 && exp // 100 != (exp + e.p) // 100 dy_b = -0.9 end exp += e.p sum += @turn < 800 ? e.p : e.ih eff = sum / (0 + need + dy_b) eff += spawn_cnt_bonus(@px) eff += near_bonus(ey) if eff > best_v best_v = eff best_move = 0 debug("best_v:#{eff} #{@px} 0 0") end {-1, 1}.each do |nmove| best_v = {best_v, sim_move(@px, need, sum, exp, best_v, nmove, 1)}.max end end end {-1, 1}.each do |move| v = sim_move(@px, 0, 0, @exp + 100, best_v, move, 0) if v > best_v best_v = v best_move = move end end return best_move end def sim_move(nx, ny, sum_o, exp_o, best_v, move, depth) return 0.0 if ny > H - 10 nx = mv(nx, move) return 0.0 if @es[nx][ny] || @es[nx][ny + 1] && @es[nx][ny + 1].not_nil!.h > exp_o // 100 while ny < H - 10 need = 0 sum = sum_o exp = exp_o (ny + 1).upto(H - 1) do |ey| if e = @es[nx][ey] need += (e.h + exp // 100 - 1) // (exp // 100) break if need > ey - ny dy_b = 0.0 if exp < 2000 && exp // 100 != (exp + e.p) // 100 dy_b = -0.9 end exp += e.p sum += @turn < 800 ? e.p : e.ih eff = sum / (ny + need + dy_b) eff += spawn_cnt_bonus(nx) eff += near_bonus(ey) if eff > best_v best_v = eff # debug("best_v:#{eff} #{nx} #{ny} #{move}") end if depth <= 0 {-1, 1}.each do |nmove| best_v = {best_v, sim_move(nx, ny + need, sum, exp, best_v, nmove, depth + 1)}.max end end end end ny += 1 if @es[nx][ny] break end nnx = mv(nx, move) next if @es[nnx][ny] || @es[nnx][ny + 1] && @es[nnx][ny + 1].not_nil!.h > exp_o // 100 nx = nnx end return best_v end def mv(x, d) x += d if x == -1 return W - 1 elsif x == W return 0 else return x end end end