結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 poka
|
| 提出日時 | 2023-07-17 08:34:34 |
| 言語 | Julia (1.10.2) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,786 bytes |
| コンパイル時間 | 274 ms |
| コンパイル使用メモリ | 6,816 KB |
| 実行使用メモリ | 324,708 KB |
| スコア | 1,912,193 |
| 平均クエリ数 | 450.00 |
| 最終ジャッジ日時 | 2024-04-09 14:28:56 |
| 合計ジャッジ時間 | 57,443 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,126 ms
322,592 KB |
| testcase_01 | AC | 1,127 ms
324,236 KB |
| testcase_02 | AC | 1,106 ms
314,180 KB |
| testcase_03 | AC | 1,113 ms
321,296 KB |
| testcase_04 | AC | 1,110 ms
316,732 KB |
| testcase_05 | AC | 1,108 ms
318,836 KB |
| testcase_06 | AC | 1,107 ms
322,060 KB |
| testcase_07 | AC | 1,125 ms
323,064 KB |
| testcase_08 | AC | 1,105 ms
319,540 KB |
| testcase_09 | AC | 1,106 ms
319,292 KB |
| testcase_10 | AC | 1,128 ms
322,792 KB |
| testcase_11 | AC | 1,106 ms
318,228 KB |
| testcase_12 | AC | 1,118 ms
322,196 KB |
| testcase_13 | AC | 1,139 ms
323,216 KB |
| testcase_14 | AC | 1,126 ms
323,656 KB |
| testcase_15 | AC | 1,110 ms
322,092 KB |
| testcase_16 | AC | 1,133 ms
320,184 KB |
| testcase_17 | AC | 1,134 ms
323,628 KB |
| testcase_18 | AC | 1,134 ms
323,168 KB |
| testcase_19 | AC | 1,133 ms
323,744 KB |
| testcase_20 | AC | 1,121 ms
320,464 KB |
| testcase_21 | AC | 1,130 ms
322,848 KB |
| testcase_22 | AC | 1,117 ms
316,172 KB |
| testcase_23 | AC | 1,111 ms
319,756 KB |
| testcase_24 | AC | 1,139 ms
324,072 KB |
| testcase_25 | AC | 1,132 ms
324,080 KB |
| testcase_26 | AC | 1,112 ms
320,684 KB |
| testcase_27 | AC | 1,114 ms
319,936 KB |
| testcase_28 | AC | 1,119 ms
324,264 KB |
| testcase_29 | AC | 1,107 ms
315,996 KB |
| testcase_30 | AC | 1,105 ms
317,132 KB |
| testcase_31 | AC | 1,101 ms
318,624 KB |
| testcase_32 | AC | 1,117 ms
322,748 KB |
| testcase_33 | AC | 1,123 ms
324,708 KB |
| testcase_34 | AC | 1,095 ms
318,896 KB |
| testcase_35 | AC | 1,114 ms
321,956 KB |
| testcase_36 | AC | 1,093 ms
316,344 KB |
| testcase_37 | AC | 1,122 ms
323,216 KB |
| testcase_38 | AC | 1,117 ms
324,532 KB |
| testcase_39 | AC | 1,121 ms
321,104 KB |
| testcase_40 | AC | 1,118 ms
323,896 KB |
| testcase_41 | AC | 1,106 ms
321,176 KB |
| testcase_42 | AC | 1,134 ms
320,988 KB |
| testcase_43 | AC | 1,109 ms
322,168 KB |
| testcase_44 | AC | 1,130 ms
321,760 KB |
| testcase_45 | TLE | - |
| 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
const TARGET_LEVEL = 300
# const TARGET_LEVEL = 250
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, enemies_init_hp_sum)
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
enemies_init_hp_sum[i] -= enemies[i][begin].init_hp
popfirst!(enemies[i])
end
end
for enemy in new_enemies
push!(enemies[enemy.x], enemy)
counnts[enemy.x] += 1
enemies_init_hp_sum[enemy.x] += enemy.init_hp
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, enemies_init_hp_sum)
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
enemies_init_hp_sum[player.x] -= enemies[player.x][begin].init_hp
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)
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]
if enemy.y <= abs(now - target_x) + 5
push!(enemies_ys[i], enemy.y)
else
break
end
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
# 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]
enemies_init_hp_sum = zeros(Int, WIDTH)
enemies_score_sum = zeros(Int, WIDTH)
for turn in 1:MAX_TURN
new_enemies = input(env)
preprocess!(enemies, counters, new_enemies, enemies_init_hp_sum)
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
enemies_score_sum .= 0
for i in 1:WIDTH
# for j in 0:((WIDTH-1)÷2)
# enemies_score_sum[i] += enemies_init_hp_sum[mod1(i - j, WIDTH)] ÷ (j + 1)
# if j != 0
# enemies_score_sum[i] += enemies_init_hp_sum[mod1(i + j, WIDTH)] ÷ (j + 1)
# end
# end
for j in 1:WIDTH
enemies_score_sum[i] += enemies_init_hp_sum[j] ÷ (1 + abs(i - j))
end
end
target_x = -1
best_value = -1
target_enemy = Enemy(0, 0, 0)
best_used_turn = INF
t = 0.15
for enemy in cand_enemies
x = enemy.x
earn_value = enemy_evaluation1(enemy, turn, player)
use_turn = expected_turn_for_braking(player, enemies, x)
value = earn_value / use_turn + enemies_score_sum[x] * t * min(1, player.level / TARGET_LEVEL)
# value = earn_value / use_turn + enemies_score_sum[x] * t * min(1, player.level / TARGET_LEVEL)
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, enemies_init_hp_sum)
end
println(stderr, "Score: ", player.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)
end
# tests_path = joinpath(@__DIR__, "testcase")
# out_path = joinpath(@__DIR__, "testcase_out")
# total_score = 0
# for i in 1:100
# file_name = lpad(i - 1, 4, "0") * ".txt"
# sample_file = joinpath(tests_path, file_name)
# out_file = joinpath(out_path, file_name)
# redirect_stdio(stdin=sample_file, stdout=out_file) do
# env = Problem.Local()
# score = Problem.main(env)
# global total_score += score
# end
# end
# println(stderr, "Total Score: ", total_score)
end
#endregion