結果
問題 | No.5017 Tool-assisted Shooting |
ユーザー |
|
提出日時 | 2023-07-16 18:55:06 |
言語 | Julia (2.11.2) |
結果 |
TLE
|
実行時間 | - |
コード長 | 8,888 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 6,944 KB |
実行使用メモリ | 324,304 KB |
スコア | 1,435,846 |
平均クエリ数 | 370.00 |
最終ジャッジ日時 | 2024-04-09 14:22:43 |
合計ジャッジ時間 | 49,840 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 37 TLE * 1 -- * 62 |
ソースコード
module Problemconst WIDTH = 25const HEIGHT = 60const MAX_TURN = 1000const TIME_LIMIT = 1.65const MIN_PERCENT = 1const MAX_PERCENT = 8const INF = 1 << 30mutable struct Localrow::Intinputs::Vector{String}endfunction Local()inputs = readlines()Local(2, inputs)endstruct Server endreadint(::Server) = parse(Int, readline())readints(::Server) = parse.(Int, readline() |> split)function readint(l::Local)n = parse(Int, l.inputs[l.row])l.row += 1nendfunction readints(l::Local)nums = parse.(Int, split(l.inputs[l.row]))l.row += 1numsendmutable struct Playerx::Intlevel::Intbreaking_power_total::Intscore::Intendfunction Player()Player(12 + 1, 1, 0, 0)endmutable struct Enemyinit_hp::Intnow_hp::Intpower::Intx::Inty::Intendfunction Enemy(init_hp, power, x0)Enemy(init_hp, init_hp, power, x0 + 1, HEIGHT)endmutable struct AppearanceCounterappear_count::Intno_appear_count::Intpercent::Float64endfunction AppearanceCounter()AppearanceCounter(0, 0, 5.0)endfunction percentage(counter::AppearanceCounter)p = counter.appear_count / (counter.appear_count + counter.no_appear_count) * 100p = max(MIN_PERCENT, p)p = min(MAX_PERCENT, p)pendfunction preprocess!(enemies::Vector{Vector{Enemy}}, counters::Vector{AppearanceCounter}, new_enemies)counnts = [0 for _ in 1:WIDTH]for i in 1:WIDTHfor j in eachindex(enemies[i])enemies[i][j].y -= 1endif !isempty(enemies[i]) && enemies[i][begin].y == 0popfirst!(enemies[i])endendfor enemy in new_enemiespush!(enemies[enemy.x], enemy)counnts[enemy.x] += 1endfor i in 1:WIDTHif counnts[i] > 0counters[i].appear_count += 1elsecounters[i].no_appear_count += 1endendendfunction postprocess!(enemies::Vector{Vector{Enemy}}, player::Player)if !isempty(enemies[player.x])enemies[player.x][begin].now_hp -= player.levelif enemies[player.x][begin].now_hp <= 0player.score += enemies[player.x][begin].init_hpplayer.breaking_power_total += enemies[player.x][begin].powerplayer.level = 1 + player.breaking_power_total ÷ 100popfirst!(enemies[player.x])endendendfunction diff(a, b)(a - b)^2endfunction update_percentages!(counters::Vector{AppearanceCounter}, probabilities, turn)t = turn / MAX_TURNfor i in 1:WIDTHold_p = probabilities[i]expected_p = percentage(counters[i])probabilities[i] = old_pprobabilities[i] += old_p * (1 - t) + expected_p * tendendfunction enemy_evaluation1(enemy::Enemy, turn, player::Player, enemies)target_level = 120t = min(1, player.level / target_level)next_power = 0next_init_hp = 0rate1 = 0.1if length(enemies[enemy.x]) > 1next_power = enemies[enemy.x][2].power * rate1next_init_hp = enemies[enemy.x][2].init_hp * rate1endprev = enemy.xnext = enemy.xfor i in 1:3prev = mod1(prev - 1, WIDTH)next = mod1(next + 1, WIDTH)rate2 = 0.2r3 = 0.5if !isempty(enemies[prev])next_power += enemies[prev][begin].power * rate2 * (r3)^(i - 1)next_init_hp += enemies[prev][begin].init_hp * rate2 * (r3)^(i - 1)endif !isempty(enemies[next])next_power += enemies[next][begin].power * rate2 * (r3)^(i - 1)next_init_hp += enemies[next][begin].init_hp * rate2 * (r3)^(i - 1)endendvalue = (enemy.power + next_power) * (1 - t) + (enemy.init_hp + next_init_hp) * tvalueendfunction approach_turn_simple(player::Player, enemies::Vector{Vector{Enemy}}, target_x)turn = 0now = player.xenemies_ys = [Int[] for _ in 1:WIDTH]for i in 1:WIDTHfor enemy in enemies[i]push!(enemies_ys[i], enemy.y)endendwhile now != target_xdirs = 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]elsebreakendcan_move = falsefor dir in dirsnext = now + dirif next < 1next += WIDTHelseif next > WIDTHnext -= WIDTHendwhile !isempty(enemies_ys[next]) && enemies_ys[next][begin] < turn + 1popfirst!(enemies_ys[next])endif isempty(enemies_ys[next])now = nextturn += 1can_move = truebreakelseenemy_y = enemies_ys[next][begin]if enemy_y != turn + 1now = nextturn += 1can_move = truebreakendendendif !can_movereturn INFendendturnendfunction expected_turn_for_braking(player::Player, enemies::Vector{Vector{Enemy}}, target_x)turn = 0approach_turn = approach_turn_simple(player, enemies, target_x)if approach_turn == INFreturn INFendturn = approach_turn# # 移動して攻撃も移動せず攻撃も使うターンは変わらない# if turn > 0# turn -= 1# endbraking_turn = (enemies[target_x][begin].now_hp + (player.level - 1)) ÷ player.levelturn += braking_turnturn -= 1# yが以下の場合は壊せない経過ターン# よくわからないけどバグ対策で1引いたif turn >= enemies[target_x][begin].y - 1turn = INFendturnendfunction 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_TURNnew_enemies = input(env)preprocess!(enemies, counters, new_enemies)update_percentages!(counters, probabilities, turn)cand_enemies = Enemy[]for i in 1:WIDTHif !isempty(enemies[i])push!(cand_enemies, enemies[i][begin])endendtarget_x = -1best_value = -1target_enemy = Enemy(0, 0, 0)best_used_turn = INFfor enemy in cand_enemiesx = enemy.xearn_value = enemy_evaluation1(enemy, turn, player, enemies)use_turn = expected_turn_for_braking(player, enemies, x)value = earn_value / use_turnif best_value < valuebest_value = valuetarget_x = xtarget_enemy = enemybest_used_turn = use_turnendenddirs = 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"]endfor dir in dirsnow = player.xif dir == "L"now -= 1if now < 1now += WIDTHendelseif dir == "R"now += 1if now > WIDTHnow -= WIDTHendendif !isempty(enemies[now]) && enemies[now][begin].y <= 2continueelseprintln(dir)player.x = nowbreakendend# 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)endprintln(stderr, "Score: ", player.score)endfunction input(env)n = readint(env)if n == -1exit()endnew_enemies = [Enemy(readints(env)...) for _ in 1:n]new_enemiesendend#region run probblemif abspath(PROGRAM_FILE) == @__FILE__env = Problem.Server()Problem.main(env)elsetests_path = joinpath(@__DIR__, "in")file_name = "0001.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) doenv = Problem.Local()Problem.main(env)endend#endregion