結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 poka
|
| 提出日時 | 2023-07-16 18:10:11 |
| 言語 | Julia (1.10.2) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,984 bytes |
| コンパイル時間 | 115 ms |
| コンパイル使用メモリ | 6,944 KB |
| 実行使用メモリ | 323,176 KB |
| スコア | 371,722 |
| 平均クエリ数 | 100.00 |
| 最終ジャッジ日時 | 2024-04-09 14:20:19 |
| 合計ジャッジ時間 | 16,707 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,136 ms
323,120 KB |
| testcase_01 | AC | 1,152 ms
323,176 KB |
| testcase_02 | AC | 1,115 ms
322,712 KB |
| testcase_03 | AC | 1,140 ms
322,992 KB |
| testcase_04 | AC | 1,127 ms
320,576 KB |
| testcase_05 | AC | 1,124 ms
321,852 KB |
| testcase_06 | AC | 1,131 ms
322,844 KB |
| testcase_07 | AC | 1,138 ms
322,524 KB |
| testcase_08 | AC | 1,122 ms
321,580 KB |
| testcase_09 | AC | 1,127 ms
322,776 KB |
| testcase_10 | TLE | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
ソースコード
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, enemies::Vector{Vector{Enemy}})
# t = turn / MAX_TURN
target_level = 120
t = min(1, player.level / target_level)
# value = if player.level <= target_level
# enemy.power * (1 - t) + enemy.init_hp * t
# else
# enemy.init_hp
# end
next_power = 0
next_init_hp = 0
rate1 = 0.2
if length(enemies[enemy.x]) > 1
next_power = enemies[enemy.x][2].power * rate1
next_init_hp = enemies[enemy.x][2].init_hp * rate1
end
prev = mod1(enemy.x - 1, WIDTH)
next = mod1(enemy.x + 1, WIDTH)
rate2 = 0.1
if !isempty(enemies[prev])
next_power += enemies[prev][begin].power * rate2
next_init_hp += enemies[prev][begin].init_hp * rate2
end
if !isempty(enemies[next])
next_power += enemies[next][begin].power * rate2
next_init_hp += enemies[next][begin].init_hp * rate2
end
value = (enemy.power + next_power) * (1 - t) + (enemy.init_hp + next_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
if turn >= enemies[target_x][begin].y
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, enemies)
use_turn = expected_turn_for_braking(player, enemies, x)
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 = "0000.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)
# @profview Problem.main(env)
end
end
#endregion