#892119 (Crystal) No.5017 Tool-assisted Shooting

• 問題: No.5017 Tool-assisted Shooting
• ユーザー: tomerun
• 提出日時: 2023-07-16 15:31:21
• 言語: Crystal (1.11.2)
• 結果: AC
• 実行時間: 87 ms / 2,000 ms
• コード長: 5,018 bytes
• コンパイル時間: 21,185 ms
• コンパイル使用メモリ: 256,516 KB
• 実行使用メモリ: 24,480 KB
• スコア: 4,068,126
• 平均クエリ数: 1000.00
• 最終ジャッジ日時: 2023-07-16 15:31:54
• 合計ジャッジ時間: 32,356 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	87 ms; 23,520 KB
testcase_01	AC	65 ms; 23,376 KB
testcase_02	AC	63 ms; 23,532 KB
testcase_03	AC	64 ms; 23,844 KB
testcase_04	AC	63 ms; 23,832 KB
testcase_05	AC	62 ms; 24,036 KB
testcase_06	AC	66 ms; 23,532 KB
testcase_07	AC	65 ms; 24,396 KB
testcase_08	AC	64 ms; 23,436 KB
testcase_09	AC	63 ms; 23,664 KB
testcase_10	AC	65 ms; 23,388 KB
testcase_11	AC	62 ms; 24,372 KB
testcase_12	AC	64 ms; 24,372 KB
testcase_13	AC	63 ms; 23,640 KB
testcase_14	AC	63 ms; 23,628 KB
testcase_15	AC	63 ms; 23,520 KB
testcase_16	AC	65 ms; 23,388 KB
testcase_17	AC	64 ms; 23,520 KB
testcase_18	AC	64 ms; 23,532 KB
testcase_19	AC	64 ms; 23,628 KB
testcase_20	AC	64 ms; 24,324 KB
testcase_21	AC	64 ms; 23,388 KB
testcase_22	AC	62 ms; 23,364 KB
testcase_23	AC	63 ms; 23,628 KB
testcase_24	AC	64 ms; 24,024 KB
testcase_25	AC	63 ms; 23,424 KB
testcase_26	AC	63 ms; 24,024 KB
testcase_27	AC	62 ms; 23,640 KB
testcase_28	AC	64 ms; 24,348 KB
testcase_29	AC	63 ms; 23,556 KB
testcase_30	AC	66 ms; 24,372 KB
testcase_31	AC	63 ms; 23,544 KB
testcase_32	AC	65 ms; 24,024 KB
testcase_33	AC	68 ms; 23,844 KB
testcase_34	AC	66 ms; 24,060 KB
testcase_35	AC	64 ms; 23,676 KB
testcase_36	AC	64 ms; 23,832 KB
testcase_37	AC	63 ms; 23,844 KB
testcase_38	AC	63 ms; 23,652 KB
testcase_39	AC	63 ms; 24,408 KB
testcase_40	AC	63 ms; 23,532 KB
testcase_41	AC	63 ms; 24,336 KB
testcase_42	AC	64 ms; 24,024 KB
testcase_43	AC	62 ms; 24,012 KB
testcase_44	AC	67 ms; 23,652 KB
testcase_45	AC	63 ms; 24,048 KB
testcase_46	AC	64 ms; 24,264 KB
testcase_47	AC	62 ms; 24,264 KB
testcase_48	AC	62 ms; 23,520 KB
testcase_49	AC	62 ms; 23,376 KB
testcase_50	AC	62 ms; 24,024 KB
testcase_51	AC	63 ms; 24,372 KB
testcase_52	AC	63 ms; 23,628 KB
testcase_53	AC	63 ms; 23,832 KB
testcase_54	AC	65 ms; 24,048 KB
testcase_55	AC	63 ms; 23,844 KB
testcase_56	AC	63 ms; 24,372 KB
testcase_57	AC	63 ms; 23,412 KB
testcase_58	AC	63 ms; 23,424 KB
testcase_59	AC	63 ms; 23,424 KB
testcase_60	AC	63 ms; 23,856 KB
testcase_61	AC	62 ms; 23,532 KB
testcase_62	AC	62 ms; 23,628 KB
testcase_63	AC	63 ms; 23,424 KB
testcase_64	AC	63 ms; 23,832 KB
testcase_65	AC	66 ms; 24,480 KB
testcase_66	AC	63 ms; 24,012 KB
testcase_67	AC	62 ms; 23,388 KB
testcase_68	AC	63 ms; 24,024 KB
testcase_69	AC	63 ms; 24,348 KB
testcase_70	AC	64 ms; 23,700 KB
testcase_71	AC	63 ms; 23,640 KB
testcase_72	AC	62 ms; 24,024 KB
testcase_73	AC	64 ms; 24,348 KB
testcase_74	AC	62 ms; 23,424 KB
testcase_75	AC	64 ms; 23,364 KB
testcase_76	AC	64 ms; 23,424 KB
testcase_77	AC	64 ms; 23,424 KB
testcase_78	AC	63 ms; 23,388 KB
testcase_79	AC	63 ms; 23,400 KB
testcase_80	AC	63 ms; 23,412 KB
testcase_81	AC	65 ms; 23,376 KB
testcase_82	AC	63 ms; 23,664 KB
testcase_83	AC	65 ms; 24,012 KB
testcase_84	AC	63 ms; 23,640 KB
testcase_85	AC	64 ms; 24,000 KB
testcase_86	AC	63 ms; 24,036 KB
testcase_87	AC	63 ms; 24,036 KB
testcase_88	AC	64 ms; 23,412 KB
testcase_89	AC	63 ms; 23,376 KB
testcase_90	AC	64 ms; 24,012 KB
testcase_91	AC	64 ms; 24,372 KB
testcase_92	AC	64 ms; 23,544 KB
testcase_93	AC	65 ms; 24,024 KB
testcase_94	AC	62 ms; 24,048 KB
testcase_95	AC	63 ms; 23,664 KB
testcase_96	AC	64 ms; 24,012 KB
testcase_97	AC	63 ms; 24,012 KB
testcase_98	AC	63 ms; 23,652 KB
testcase_99	AC	63 ms; 24,012 KB

ソースコード

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

  def initialize(@h : Int32, @p : Int32)
  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
  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
            @enemies[@player][i] = nil
          end
          break
        end
      end
    end
  end

  def print
    printf("score=%d\n", @exp)
  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
    @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
              @atk = 1 + @exp // 100
              @es[@px][y] = nil
            end
            break
          end
        end
      end
      @judge.output(move)
      @turn += 1
    end
    debug("score:#{@exp}")
  end

  def spawn_cnt_bonus(x)
    p = (@spawn_cnt[x] + 4) / (@turn + 100)
    return p * 1
  end

  def select_move
    debug("x:#{@px}")
    best_v = 0.0
    best_move = 0
    1.upto(H - 1) do |ey|
      if e = @es[@px][ey]
        need = (e.h + @atk - 1) // @atk
        if need <= ey - 0
          eff = e.p / (0 + need + 1)
          eff += spawn_cnt_bonus(@px)
          if eff > best_v
            best_v = eff
            best_move = 0
            debug("best_v:#{eff} #{@px} 0 0")
          end
        end
        break
      end
    end

    {-1, 1}.each do |move|
      nx = mv(@px, move)
      next if @es[nx][0] || @es[nx][1] && @es[nx][1].not_nil!.h > @atk
      ny = 0
      while nx != @px && ny < H - 3
        (ny + 1).upto(H - 1) do |ey|
          if e = @es[nx][ey]
            need = (e.h + @atk - 1) // @atk
            if need <= ey - ny
              eff = e.p / (ny + need + 1)
              eff += spawn_cnt_bonus(nx)
              if eff > best_v
                best_v = eff
                best_move = move
                debug("best_v:#{eff} #{nx} #{ny} #{move}")
              end
            end
            break
          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 > @atk
        nx = nnx
      end
    end
    return best_move
  end

  def mv(x, d)
    x += d
    if x == -1
      return W - 1
    elsif x == W
      return 0
    else
      return x
    end
  end
end