結果
| 問題 | No.5017 Tool-assisted Shooting |
| コンテスト | |
| ユーザー |
 poka
|
| 提出日時 | 2023-07-17 08:34:34 |
| 言語 | Julia (2.11.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 45 TLE * 1 -- * 54 |
ソースコード
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