結果

問題 No.5017 Tool-assisted Shooting
ユーザー tomeruntomerun
提出日時 2023-07-16 18:51:00
言語 Crystal
(1.11.2)
結果
AC  
実行時間 1,737 ms / 2,000 ms
コード長 6,842 bytes
コンパイル時間 17,211 ms
コンパイル使用メモリ 261,904 KB
実行使用メモリ 24,372 KB
スコア 4,563,143
平均クエリ数 1000.00
最終ジャッジ日時 2023-07-16 18:52:54
合計ジャッジ時間 91,830 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 639 ms
24,072 KB
testcase_01 AC 927 ms
23,388 KB
testcase_02 AC 340 ms
23,988 KB
testcase_03 AC 720 ms
23,364 KB
testcase_04 AC 488 ms
23,592 KB
testcase_05 AC 468 ms
23,628 KB
testcase_06 AC 554 ms
23,616 KB
testcase_07 AC 649 ms
24,288 KB
testcase_08 AC 408 ms
24,000 KB
testcase_09 AC 453 ms
23,460 KB
testcase_10 AC 814 ms
24,348 KB
testcase_11 AC 344 ms
24,012 KB
testcase_12 AC 575 ms
24,216 KB
testcase_13 AC 865 ms
24,012 KB
testcase_14 AC 978 ms
23,424 KB
testcase_15 AC 637 ms
23,388 KB
testcase_16 AC 437 ms
23,988 KB
testcase_17 AC 774 ms
23,844 KB
testcase_18 AC 601 ms
23,844 KB
testcase_19 AC 768 ms
23,988 KB
testcase_20 AC 636 ms
23,460 KB
testcase_21 AC 693 ms
24,072 KB
testcase_22 AC 344 ms
24,324 KB
testcase_23 AC 430 ms
23,568 KB
testcase_24 AC 957 ms
24,324 KB
testcase_25 AC 873 ms
24,312 KB
testcase_26 AC 635 ms
23,616 KB
testcase_27 AC 469 ms
24,336 KB
testcase_28 AC 906 ms
24,048 KB
testcase_29 AC 321 ms
23,856 KB
testcase_30 AC 258 ms
24,012 KB
testcase_31 AC 500 ms
23,472 KB
testcase_32 AC 940 ms
23,652 KB
testcase_33 AC 1,061 ms
23,568 KB
testcase_34 AC 473 ms
23,772 KB
testcase_35 AC 589 ms
23,544 KB
testcase_36 AC 397 ms
23,352 KB
testcase_37 AC 785 ms
24,288 KB
testcase_38 AC 812 ms
23,976 KB
testcase_39 AC 688 ms
24,276 KB
testcase_40 AC 846 ms
23,652 KB
testcase_41 AC 655 ms
23,484 KB
testcase_42 AC 963 ms
23,568 KB
testcase_43 AC 600 ms
24,348 KB
testcase_44 AC 798 ms
24,060 KB
testcase_45 AC 700 ms
23,772 KB
testcase_46 AC 756 ms
23,556 KB
testcase_47 AC 355 ms
23,532 KB
testcase_48 AC 774 ms
23,436 KB
testcase_49 AC 481 ms
23,352 KB
testcase_50 AC 718 ms
24,348 KB
testcase_51 AC 682 ms
24,360 KB
testcase_52 AC 721 ms
24,012 KB
testcase_53 AC 637 ms
23,532 KB
testcase_54 AC 837 ms
23,568 KB
testcase_55 AC 516 ms
23,376 KB
testcase_56 AC 582 ms
24,324 KB
testcase_57 AC 386 ms
24,372 KB
testcase_58 AC 699 ms
24,060 KB
testcase_59 AC 1,243 ms
24,012 KB
testcase_60 AC 691 ms
23,568 KB
testcase_61 AC 477 ms
23,844 KB
testcase_62 AC 413 ms
24,288 KB
testcase_63 AC 730 ms
23,544 KB
testcase_64 AC 857 ms
23,988 KB
testcase_65 AC 1,737 ms
23,544 KB
testcase_66 AC 745 ms
23,976 KB
testcase_67 AC 631 ms
24,216 KB
testcase_68 AC 734 ms
23,328 KB
testcase_69 AC 525 ms
23,988 KB
testcase_70 AC 585 ms
24,060 KB
testcase_71 AC 682 ms
24,264 KB
testcase_72 AC 447 ms
23,400 KB
testcase_73 AC 703 ms
24,324 KB
testcase_74 AC 306 ms
24,000 KB
testcase_75 AC 747 ms
23,664 KB
testcase_76 AC 822 ms
23,988 KB
testcase_77 AC 972 ms
23,592 KB
testcase_78 AC 861 ms
23,484 KB
testcase_79 AC 617 ms
23,376 KB
testcase_80 AC 752 ms
24,288 KB
testcase_81 AC 550 ms
24,072 KB
testcase_82 AC 515 ms
23,988 KB
testcase_83 AC 557 ms
23,616 KB
testcase_84 AC 881 ms
23,436 KB
testcase_85 AC 800 ms
24,000 KB
testcase_86 AC 631 ms
24,276 KB
testcase_87 AC 578 ms
23,364 KB
testcase_88 AC 958 ms
23,772 KB
testcase_89 AC 838 ms
23,664 KB
testcase_90 AC 1,007 ms
24,288 KB
testcase_91 AC 1,588 ms
23,484 KB
testcase_92 AC 352 ms
23,256 KB
testcase_93 AC 822 ms
23,580 KB
testcase_94 AC 359 ms
23,328 KB
testcase_95 AC 802 ms
23,424 KB
testcase_96 AC 825 ms
23,376 KB
testcase_97 AC 715 ms
23,988 KB
testcase_98 AC 721 ms
24,000 KB
testcase_99 AC 711 ms
23,388 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
    @spawn_cnt_bonus = Array(Float64).new(W, 0.0)
    @near_bonus = Array(Float64).new(H, 0.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
      W.times do |i|
        p = (@spawn_cnt[i] + 40) / (@turn + 1000)
        @spawn_cnt_bonus[i] = p * 0.001 * (@turn ** 1.5)
      end
      H.times do |i|
        @near_bonus[i] = 0.0005 / (i + 1) * (@turn ** 1.8)
      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 < 700 ? e.p : e.ih
        eff = (sum - need * 0.2) / (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
        if eff > best_v * 0.75
          {-1, 1}.each do |nmove|
            best_v = {best_v, sim_move(@px, need, sum, exp, best_v, nmove, 1)}.max
          end
        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
      first = true
      (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 < 700 ? e.p : e.ih
          eff = (sum - (ny + need) * 0.2) / (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 <= 1 && eff > best_v * 0.75
            {-1, 1}.each do |nmove|
              best_v = {best_v, sim_move(nx, ny + need, sum, exp, best_v, nmove, depth + 1)}.max
            end
          end
          if first
            first = false
            if e.h <= exp_o // 100
              sum_o += @turn < 700 ? e.p : e.ih
              exp_o += e.p
            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
0