結果

問題 No.5017 Tool-assisted Shooting
ユーザー pokapoka
提出日時 2023-07-17 00:28:13
言語 Julia
(1.10.2)
結果
AC  
実行時間 1,123 ms / 2,000 ms
コード長 8,196 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 6,816 KB
実行使用メモリ 323,736 KB
スコア 3,899,821
平均クエリ数 1000.00
最終ジャッジ日時 2024-04-09 14:26:39
合計ジャッジ時間 115,782 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,096 ms
320,984 KB
testcase_01 AC 1,095 ms
321,492 KB
testcase_02 AC 1,074 ms
320,652 KB
testcase_03 AC 1,103 ms
320,928 KB
testcase_04 AC 1,086 ms
321,196 KB
testcase_05 AC 1,080 ms
320,276 KB
testcase_06 AC 1,097 ms
322,220 KB
testcase_07 AC 1,086 ms
323,248 KB
testcase_08 AC 1,075 ms
321,852 KB
testcase_09 AC 1,077 ms
320,012 KB
testcase_10 AC 1,088 ms
322,600 KB
testcase_11 AC 1,090 ms
322,144 KB
testcase_12 AC 1,083 ms
322,568 KB
testcase_13 AC 1,093 ms
322,180 KB
testcase_14 AC 1,107 ms
323,276 KB
testcase_15 AC 1,082 ms
322,236 KB
testcase_16 AC 1,091 ms
321,304 KB
testcase_17 AC 1,106 ms
321,920 KB
testcase_18 AC 1,092 ms
322,604 KB
testcase_19 AC 1,099 ms
322,424 KB
testcase_20 AC 1,089 ms
320,712 KB
testcase_21 AC 1,082 ms
322,080 KB
testcase_22 AC 1,075 ms
321,332 KB
testcase_23 AC 1,090 ms
320,460 KB
testcase_24 AC 1,096 ms
321,044 KB
testcase_25 AC 1,101 ms
322,096 KB
testcase_26 AC 1,085 ms
323,308 KB
testcase_27 AC 1,099 ms
320,300 KB
testcase_28 AC 1,102 ms
321,576 KB
testcase_29 AC 1,088 ms
322,320 KB
testcase_30 AC 1,089 ms
320,448 KB
testcase_31 AC 1,104 ms
320,716 KB
testcase_32 AC 1,117 ms
320,888 KB
testcase_33 AC 1,116 ms
322,492 KB
testcase_34 AC 1,107 ms
322,860 KB
testcase_35 AC 1,104 ms
320,680 KB
testcase_36 AC 1,098 ms
319,748 KB
testcase_37 AC 1,104 ms
320,660 KB
testcase_38 AC 1,112 ms
322,468 KB
testcase_39 AC 1,110 ms
323,044 KB
testcase_40 AC 1,093 ms
322,076 KB
testcase_41 AC 1,085 ms
323,372 KB
testcase_42 AC 1,105 ms
322,440 KB
testcase_43 AC 1,109 ms
323,348 KB
testcase_44 AC 1,105 ms
320,564 KB
testcase_45 AC 1,091 ms
320,596 KB
testcase_46 AC 1,111 ms
323,244 KB
testcase_47 AC 1,091 ms
322,016 KB
testcase_48 AC 1,113 ms
322,344 KB
testcase_49 AC 1,092 ms
320,176 KB
testcase_50 AC 1,094 ms
323,736 KB
testcase_51 AC 1,102 ms
322,356 KB
testcase_52 AC 1,108 ms
322,260 KB
testcase_53 AC 1,091 ms
322,944 KB
testcase_54 AC 1,093 ms
321,452 KB
testcase_55 AC 1,078 ms
320,928 KB
testcase_56 AC 1,094 ms
322,128 KB
testcase_57 AC 1,078 ms
320,388 KB
testcase_58 AC 1,090 ms
323,292 KB
testcase_59 AC 1,090 ms
321,104 KB
testcase_60 AC 1,102 ms
322,472 KB
testcase_61 AC 1,087 ms
322,888 KB
testcase_62 AC 1,079 ms
322,448 KB
testcase_63 AC 1,098 ms
320,616 KB
testcase_64 AC 1,096 ms
322,864 KB
testcase_65 AC 1,123 ms
323,016 KB
testcase_66 AC 1,090 ms
320,896 KB
testcase_67 AC 1,080 ms
321,524 KB
testcase_68 AC 1,091 ms
321,644 KB
testcase_69 AC 1,098 ms
322,964 KB
testcase_70 AC 1,095 ms
323,036 KB
testcase_71 AC 1,100 ms
320,028 KB
testcase_72 AC 1,090 ms
322,572 KB
testcase_73 AC 1,098 ms
320,368 KB
testcase_74 AC 1,097 ms
320,908 KB
testcase_75 AC 1,107 ms
320,852 KB
testcase_76 AC 1,100 ms
320,520 KB
testcase_77 AC 1,108 ms
321,496 KB
testcase_78 AC 1,091 ms
319,780 KB
testcase_79 AC 1,090 ms
321,664 KB
testcase_80 AC 1,099 ms
322,712 KB
testcase_81 AC 1,087 ms
322,140 KB
testcase_82 AC 1,096 ms
322,700 KB
testcase_83 AC 1,089 ms
322,616 KB
testcase_84 AC 1,090 ms
321,056 KB
testcase_85 AC 1,098 ms
322,676 KB
testcase_86 AC 1,094 ms
322,236 KB
testcase_87 AC 1,101 ms
320,432 KB
testcase_88 AC 1,102 ms
323,480 KB
testcase_89 AC 1,101 ms
322,988 KB
testcase_90 AC 1,094 ms
322,836 KB
testcase_91 AC 1,101 ms
321,340 KB
testcase_92 AC 1,078 ms
322,276 KB
testcase_93 AC 1,103 ms
320,792 KB
testcase_94 AC 1,085 ms
321,916 KB
testcase_95 AC 1,093 ms
320,444 KB
testcase_96 AC 1,107 ms
320,020 KB
testcase_97 AC 1,105 ms
321,548 KB
testcase_98 AC 1,106 ms
323,380 KB
testcase_99 AC 1,094 ms
322,600 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

module Problem

const WIDTH = 25
const HEIGHT = 60
const MAX_TURN = 1000
const TIME_LIMIT = 1.65
const MIN_PERCENT = 1
const MAX_PERCENT = 8
const INF = 1 << 30

mutable struct Local
    row::Int
    inputs::Vector{String}
end
function Local()
    inputs = readlines()
    Local(2, inputs)
end

struct Server end

readint(::Server) = parse(Int, readline())
readints(::Server) = parse.(Int, readline() |> split)

function readint(l::Local)
    n = parse(Int, l.inputs[l.row])
    l.row += 1
    n
end

function readints(l::Local)
    nums = parse.(Int, split(l.inputs[l.row]))
    l.row += 1
    nums
end


mutable struct Player
    x::Int
    level::Int
    breaking_power_total::Int
    score::Int
end
function Player()
    Player(12 + 1, 1, 0, 0)
end


mutable struct Enemy
    init_hp::Int
    now_hp::Int
    power::Int
    x::Int
    y::Int
end
function Enemy(init_hp, power, x0)
    Enemy(init_hp, init_hp, power, x0 + 1, HEIGHT)
end

mutable struct AppearanceCounter
    appear_count::Int
    no_appear_count::Int
    percent::Float64
end
function AppearanceCounter()
    AppearanceCounter(0, 0, 5.0)
end
function percentage(counter::AppearanceCounter)
    p = counter.appear_count / (counter.appear_count + counter.no_appear_count) * 100
    p = max(MIN_PERCENT, p)
    p = min(MAX_PERCENT, p)
    p
end

function preprocess!(enemies::Vector{Vector{Enemy}}, counters::Vector{AppearanceCounter}, new_enemies)
    counnts = [0 for _ in 1:WIDTH]
    for i in 1:WIDTH
        for j in eachindex(enemies[i])
            enemies[i][j].y -= 1
        end
        if !isempty(enemies[i]) && enemies[i][begin].y == 0
            popfirst!(enemies[i])
        end
    end
    for enemy in new_enemies
        push!(enemies[enemy.x], enemy)
        counnts[enemy.x] += 1
    end
    for i in 1:WIDTH
        if counnts[i] > 0
            counters[i].appear_count += 1
        else
            counters[i].no_appear_count += 1
        end
    end
end

function postprocess!(enemies::Vector{Vector{Enemy}}, player::Player)
    if !isempty(enemies[player.x])
        enemies[player.x][begin].now_hp -= player.level
        if enemies[player.x][begin].now_hp <= 0
            player.score += enemies[player.x][begin].init_hp
            player.breaking_power_total += enemies[player.x][begin].power
            player.level = 1 + player.breaking_power_total ÷ 100
            popfirst!(enemies[player.x])
        end
    end
end

function diff(a, b)
    (a - b)^2
end

function update_percentages!(counters::Vector{AppearanceCounter}, probabilities, turn)
    t = turn / MAX_TURN
    for i in 1:WIDTH
        old_p = probabilities[i]
        expected_p = percentage(counters[i])
        probabilities[i] = old_p
        probabilities[i] += old_p * (1 - t) + expected_p * t
    end
end


function enemy_evaluation1(enemy::Enemy, turn, player::Player)
    target_level = 70
    t = min(1, player.level / target_level)
    value = enemy.power * (1 - t) + enemy.init_hp * t
    value
end

function approach_turn_simple(player::Player, enemies::Vector{Vector{Enemy}}, target_x)
    turn = 0
    now = player.x

    enemies_ys = [Int[] for _ in 1:WIDTH]
    for i in 1:WIDTH
        for enemy in enemies[i]
            push!(enemies_ys[i], enemy.y)
        end
    end

    while now != target_x
        dirs = if mod(now - target_x, WIDTH) < mod(target_x - now, WIDTH)
            [-1, 0, 1]
        elseif mod(now - target_x, WIDTH) > mod(target_x - now, WIDTH)
            [1, 0, -1]
        else
            break
        end
        can_move = false
        for dir in dirs
            next = now + dir
            if next < 1
                next += WIDTH
            elseif next > WIDTH
                next -= WIDTH
            end
            while !isempty(enemies_ys[next]) && enemies_ys[next][begin] < turn + 1
                popfirst!(enemies_ys[next])
            end
            if isempty(enemies_ys[next])
                now = next
                turn += 1
                can_move = true
                break
            else
                enemy_y = enemies_ys[next][begin]
                if enemy_y != turn + 1
                    now = next
                    turn += 1
                    can_move = true
                    break
                end
            end
        end
        if !can_move
            return INF
        end
    end

    turn

end

function expected_turn_for_braking(player::Player, enemies::Vector{Vector{Enemy}}, target_x)
    turn = 0
    approach_turn = approach_turn_simple(player, enemies, target_x)
    if approach_turn == INF
        return INF
    end
    turn = approach_turn
    # # 移動して攻撃も移動せず攻撃も使うターンは変わらない
    # if turn > 0
    #     turn -= 1
    # end
    braking_turn = (enemies[target_x][begin].now_hp + (player.level - 1)) ÷ player.level
    turn += braking_turn
    turn -= 1
    # yが以下の場合は壊せない経過ターン
    # よくわからないけどバグ対策で1引いた
    if turn >= enemies[target_x][begin].y - 1
        turn = INF
    end
    turn
end


function main(env)
    player = Player()
    enemies = [Enemy[] for _ in 1:WIDTH]
    counters = [AppearanceCounter() for _ in 1:WIDTH]
    probabilities = [4.5 for _ in 1:WIDTH]
    for turn in 1:MAX_TURN
        new_enemies = input(env)
        preprocess!(enemies, counters, new_enemies)
        update_percentages!(counters, probabilities, turn)

        cand_enemies = Enemy[]
        for i in 1:WIDTH
            if !isempty(enemies[i])
                push!(cand_enemies, enemies[i][begin])
            end
        end

        target_x = -1
        best_value = -1
        target_enemy = Enemy(0, 0, 0)
        best_used_turn = INF
        for enemy in cand_enemies
            x = enemy.x
            earn_value = enemy_evaluation1(enemy, turn, player)
            use_turn = expected_turn_for_braking(player, enemies, x)
            if use_turn == INF
                continue
            end
            if use_turn + turn > MAX_TURN
                continue
            end
            value = earn_value / use_turn
            if best_value < value
                best_value = value
                target_x = x
                target_enemy = enemy
                best_used_turn = use_turn
            end
        end

        dirs = if mod(player.x - target_x, WIDTH) < mod(target_x - player.x, WIDTH)
            ["L", "S", "R"]
        elseif mod(player.x - target_x, WIDTH) > mod(target_x - player.x, WIDTH)
            ["R", "S", "L"]
        else
            ["S", "L", "R"]
        end

        for dir in dirs
            now = player.x
            if dir == "L"
                now -= 1
                if now < 1
                    now += WIDTH
                end
            elseif dir == "R"
                now += 1
                if now > WIDTH
                    now -= WIDTH
                end
            end
            if !isempty(enemies[now]) && enemies[now][begin].y <= 2
                continue
            else
                println(dir)
                player.x = now
                break
            end
        end

        # println("# target_x: ", target_x)
        # println("# best_value: ", best_value)
        # println("# player: ", player.level, " ", player.x)
        # println("# enemy: ", target_enemy.now_hp, " ", target_enemy.x)
        # println("# best_used_turn: ", best_used_turn)
        # println("# dirs: ", dirs)

        postprocess!(enemies, player)

    end

    println(stderr, "Score: ", player.score)
end



function input(env)
    n = readint(env)
    if n == -1
        exit()
    end
    new_enemies = [Enemy(readints(env)...) for _ in 1:n]
    new_enemies
end

end

#region run probblem
if abspath(PROGRAM_FILE) == @__FILE__
    env = Problem.Server()
    Problem.main(env)
else
    tests_path = joinpath(@__DIR__, "in")
    file_name = "0002.txt"
    sample_file = joinpath(tests_path, file_name)
    out_path = joinpath(@__DIR__, "out")
    out_file = joinpath(out_path, file_name)
    redirect_stdio(stdin=sample_file, stdout=out_file) do
        env = Problem.Local()
        Problem.main(env)
    end
end
#endregion
0