結果
| 問題 | No.5017 Tool-assisted Shooting |
| ユーザー |
 yunix
|
| 提出日時 | 2023-07-01 13:11:11 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 18,867 bytes |
| コンパイル時間 | 5,871 ms |
| コンパイル使用メモリ | 164,776 KB |
| 実行使用メモリ | 25,400 KB |
| スコア | 4,054,345 |
| 平均クエリ数 | 950.00 |
| 最終ジャッジ日時 | 2023-07-16 13:36:37 |
| 合計ジャッジ時間 | 192,908 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,793 ms
25,108 KB |
| testcase_01 | AC | 1,836 ms
25,292 KB |
| testcase_02 | AC | 1,740 ms
24,268 KB |
| testcase_03 | AC | 1,817 ms
24,620 KB |
| testcase_04 | AC | 1,726 ms
25,004 KB |
| testcase_05 | AC | 1,683 ms
24,512 KB |
| testcase_06 | AC | 1,840 ms
24,292 KB |
| testcase_07 | AC | 1,829 ms
24,912 KB |
| testcase_08 | AC | 1,727 ms
24,852 KB |
| testcase_09 | AC | 1,726 ms
24,288 KB |
| testcase_10 | AC | 1,825 ms
24,752 KB |
| testcase_11 | AC | 1,910 ms
24,828 KB |
| testcase_12 | AC | 1,873 ms
25,008 KB |
| testcase_13 | AC | 1,889 ms
25,200 KB |
| testcase_14 | AC | 1,907 ms
25,076 KB |
| testcase_15 | AC | 1,971 ms
24,728 KB |
| testcase_16 | AC | 1,778 ms
24,952 KB |
| testcase_17 | AC | 1,853 ms
25,184 KB |
| testcase_18 | AC | 1,912 ms
24,392 KB |
| testcase_19 | AC | 1,871 ms
24,604 KB |
| testcase_20 | AC | 1,827 ms
24,872 KB |
| testcase_21 | AC | 1,828 ms
25,328 KB |
| testcase_22 | AC | 1,593 ms
24,620 KB |
| testcase_23 | AC | 1,789 ms
24,896 KB |
| testcase_24 | AC | 1,806 ms
25,192 KB |
| testcase_25 | AC | 1,864 ms
25,248 KB |
| testcase_26 | AC | 1,869 ms
24,724 KB |
| testcase_27 | AC | 1,783 ms
25,160 KB |
| testcase_28 | AC | 1,823 ms
25,076 KB |
| testcase_29 | AC | 1,733 ms
25,012 KB |
| testcase_30 | AC | 1,689 ms
24,980 KB |
| testcase_31 | AC | 1,727 ms
24,860 KB |
| testcase_32 | AC | 1,911 ms
24,888 KB |
| testcase_33 | AC | 1,784 ms
25,124 KB |
| testcase_34 | AC | 1,750 ms
24,248 KB |
| testcase_35 | AC | 1,787 ms
24,732 KB |
| testcase_36 | AC | 1,719 ms
24,364 KB |
| testcase_37 | AC | 1,818 ms
25,300 KB |
| testcase_38 | TLE | - |
| testcase_39 | AC | 1,833 ms
25,344 KB |
| testcase_40 | AC | 1,814 ms
25,116 KB |
| testcase_41 | AC | 1,813 ms
24,960 KB |
| testcase_42 | AC | 1,867 ms
25,064 KB |
| testcase_43 | AC | 1,806 ms
25,256 KB |
| testcase_44 | AC | 1,877 ms
24,720 KB |
| testcase_45 | AC | 1,756 ms
24,800 KB |
| testcase_46 | AC | 1,916 ms
25,232 KB |
| testcase_47 | AC | 1,813 ms
24,604 KB |
| testcase_48 | AC | 1,857 ms
25,240 KB |
| testcase_49 | AC | 1,792 ms
25,184 KB |
| testcase_50 | AC | 1,793 ms
24,600 KB |
| testcase_51 | AC | 1,933 ms
25,392 KB |
| testcase_52 | AC | 1,850 ms
24,772 KB |
| testcase_53 | AC | 1,829 ms
25,004 KB |
| testcase_54 | AC | 1,901 ms
24,396 KB |
| testcase_55 | AC | 1,634 ms
24,268 KB |
| testcase_56 | AC | 1,844 ms
25,136 KB |
| testcase_57 | AC | 1,763 ms
24,956 KB |
| testcase_58 | AC | 1,805 ms
25,180 KB |
| testcase_59 | TLE | - |
| testcase_60 | AC | 1,849 ms
25,060 KB |
| testcase_61 | AC | 1,816 ms
25,080 KB |
| testcase_62 | AC | 1,901 ms
25,084 KB |
| testcase_63 | AC | 1,883 ms
24,992 KB |
| testcase_64 | AC | 1,965 ms
24,968 KB |
| testcase_65 | AC | 1,948 ms
24,992 KB |
| testcase_66 | TLE | - |
| testcase_67 | AC | 1,806 ms
25,004 KB |
| testcase_68 | AC | 1,863 ms
24,816 KB |
| testcase_69 | AC | 1,874 ms
25,212 KB |
| testcase_70 | AC | 1,715 ms
24,840 KB |
| testcase_71 | AC | 1,676 ms
25,032 KB |
| testcase_72 | AC | 1,798 ms
24,888 KB |
| testcase_73 | AC | 1,897 ms
24,936 KB |
| testcase_74 | AC | 1,795 ms
24,856 KB |
| testcase_75 | AC | 1,820 ms
24,548 KB |
| testcase_76 | AC | 1,994 ms
25,004 KB |
| testcase_77 | TLE | - |
| testcase_78 | AC | 1,865 ms
24,776 KB |
| testcase_79 | AC | 1,746 ms
25,052 KB |
| testcase_80 | AC | 1,901 ms
24,968 KB |
| testcase_81 | AC | 1,778 ms
24,832 KB |
| testcase_82 | AC | 1,893 ms
25,216 KB |
| testcase_83 | AC | 1,768 ms
24,912 KB |
| testcase_84 | AC | 1,864 ms
24,912 KB |
| testcase_85 | AC | 1,751 ms
24,724 KB |
| testcase_86 | AC | 1,818 ms
24,808 KB |
| testcase_87 | AC | 1,862 ms
24,672 KB |
| testcase_88 | AC | 1,943 ms
25,292 KB |
| testcase_89 | AC | 1,896 ms
24,452 KB |
| testcase_90 | AC | 1,731 ms
25,228 KB |
| testcase_91 | AC | 1,969 ms
24,884 KB |
| testcase_92 | AC | 1,743 ms
24,288 KB |
| testcase_93 | AC | 1,854 ms
24,468 KB |
| testcase_94 | AC | 1,684 ms
24,564 KB |
| testcase_95 | AC | 1,902 ms
25,104 KB |
| testcase_96 | AC | 1,933 ms
25,016 KB |
| testcase_97 | AC | 1,697 ms
25,272 KB |
| testcase_98 | AC | 1,878 ms
24,856 KB |
| testcase_99 | AC | 1,824 ms
24,424 KB |
コンパイルメッセージ
main.cpp: メンバ関数 ‘char GreedyCommander::check_die(char)’ 内:
main.cpp:500:17: 警告: ‘dx’ may be used uninitialized [-Wmaybe-uninitialized]
500 | if (can_move(dx))
| ~~~~~~~~^~~~
main.cpp:486:9: 備考: ‘dx’ はここで定義されています
486 | int dx;
| ^~
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <chrono>
#include <algorithm>
#include <random>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <chrono>
#include <cmath>
#include <climits>
#include <bitset>
#include <time.h>
using namespace std;
using Ps = pair<short, short>;
using vec_int = vector<int>;
using P = pair<int, int>;
using P2 = pair<P, P>;
using P3 = pair<float, int>;
using T = tuple<int, int, int>;
using T2 = tuple<float, int, int>;
using T3 = tuple<float, int, int, int, int>;
using T4 = tuple<int, int, int, int>;
using T5 = tuple<int, int, int, int, int>;
using TT = tuple<int, int, int>;
using ll = long long;
using uc = unsigned char;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// #pragma GCC optimize("Ofast")
std::mt19937 mt{12345};
int RAND_ARR_LEN = 100000;
int RAND_RANGE = 1000000000;
float TIME_LIMIT = 5000;
float INV_TIME_LIMIT = 1. / 1000.;
const int JOB_MAX_LEN = 1003;
std::uniform_int_distribution<int> dist(1, RAND_RANGE);
int WAITING_TASK = 1001;
void remove_val_and_pop_from_last(vec_int &A, int val)
{
for (int i = 0; i < A.size(); i++)
{
if (A.at(i) == val)
{
A.at(i) = A.at(A.size() - 1);
A.pop_back();
return;
}
}
throw runtime_error("trying to remove non-existing value");
}
class Rand
{
private:
int count = 0;
vec_int rand_arr;
public:
Rand(){
rep(i, RAND_ARR_LEN){
rand_arr.push_back(dist(mt));
}
}
;
int get();
int get_rand(int from, int to);
float get_float();
}
;
int Rand::get()
{
int num = rand_arr.at(count);
count += 1;
count %= RAND_ARR_LEN;
return num;
}
int Rand::get_rand(int from, int to)
{
int diff = to - from;
int num = get() % diff;
return num + from;
}
float Rand::get_float()
{
// 0~1の間の一様乱数
return (float)get() / (float)RAND_RANGE;
}
Rand ro;
class PseudoSet
{
private:
vec_int index_arr;
public:
vec_int data;
PseudoSet(){};
PseudoSet(int value_range)
{
index_arr = vec_int(value_range, -1);
}
bool count(int value);
void insert(int value);
void erase(int value);
vec_int get_data() { return data; };
int size() { return data.size(); };
int get_random() { return data.at(ro.get_rand(0, size())); };
};
bool PseudoSet::count(int value)
{
return index_arr[value] != -1;
}
void PseudoSet::insert(int value)
{
if (count(value))
return;
index_arr[value] = data.size();
data.push_back(value);
}
void PseudoSet::erase(int value)
{
if (!count(value))
{
// throw runtime_error("no existing value:"+to_string(value));
return;
}
int tail_value = data[data.size() - 1];
if (value == tail_value)
{
data.pop_back();
index_arr[value] = -1;
}
else
{
index_arr[tail_value] = index_arr[value];
index_arr[value] = -1;
data[index_arr[tail_value]] = tail_value;
data.pop_back();
}
}
float get_time(bool init)
{
static std::chrono::system_clock::time_point start;
if (init)
{
start = std::chrono::system_clock::now();
}
std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); // 処理に要した時間をミリ秒に変換
}
double current_tmp(double current_time, double T0, double T1)
{
return T1 + (T0 - T1) * (TIME_LIMIT * 0.92 - current_time) / (TIME_LIMIT * 0.92);
// double start_time = TIME_LIMIT * 0.6;
// double x = (current_time - start_time) / (TIME_LIMIT * 0.32);
// return pow(T1, 1 - x) + (T0, x);
}
bool is_valid_transition(int diff, double current_time, double T0, float T1)
{
float t = current_tmp(current_time, T0, T1);
float rand = ro.get_float();
// diffが正だったら常にアクセぷと
return rand < exp(((float)diff) / t);
}
struct Enemy
{
int max_HP;
int HP;
int power;
int x;
int y;
};
struct State
{
int turn;
int score;
int earned_power;
int x;
vector<char> commands;
vector<int> steps;
};
struct History
{
int enemy_index;
int damage;
int gained_score;
int gained_power;
int x;
};
class Game
{
private:
vector<History> histories;
vector<vec_int> poped_enemy;
public:
int earned_power;
int turn;
int score;
int x_pos;
vector<deque<int>> enemy_queue;
Game();
void move(char command, bool output);
void attack();
void pop_enemies(int n);
void process_turn();
bool is_game_over();
bool is_alive(int enemy_index) { return enemies[enemy_index].HP > 0 && turn <= enemies[enemy_index].y; }
int get_enemy_index(int x);
vector<Enemy> enemies;
bool can_kill_enemy(int enemy_ind, int turns);
void roll_back_a_turn();
void process_turns(vector<char> &commands);
State make_state()
{
return State{
turn, score, earned_power, x_pos, vector<char>(), {0}};
}
};
Game::Game()
{
turn = 0;
x_pos = 12;
earned_power = 0;
score = 0;
enemy_queue = vector<deque<int>>(25);
poped_enemy = vector<vec_int>(1200);
}
void Game::roll_back_a_turn()
{
turn--;
History history = histories.at(histories.size() - 1);
histories.pop_back();
x_pos = history.x;
if (history.enemy_index == -1)
return;
enemies[history.enemy_index].HP += history.damage;
if (history.gained_score > 0)
{
score -= history.gained_score;
earned_power -= history.gained_power;
}
for (auto enemy_ind : poped_enemy.at(turn))
{
int x = enemies[enemy_ind].x;
enemy_queue.at(x).push_front(enemy_ind);
}
poped_enemy.at(turn).clear();
}
void Game::process_turns(vector<char> &commands)
{
for (auto command : commands)
{
move(command, false);
attack();
process_turn();
}
}
void Game::pop_enemies(int n)
{
vec_int h(n), p(n), x(n);
rep(i, n) cin >> h.at(i) >> p.at(i) >> x.at(i);
for (int i = 0; i < n; i++)
{
enemies.push_back(Enemy{h.at(i), h.at(i), p.at(i), x.at(i), 59 + turn});
enemy_queue.at(x.at(i)).push_back(enemies.size() - 1);
}
}
bool Game::is_game_over()
{
int enemy_ind = get_enemy_index(x_pos);
if (enemy_ind == -1)
return false;
if (enemies[enemy_ind].y == turn && enemies[enemy_ind].HP > 0)
return true;
return false;
}
void Game::move(char command, bool output)
{
switch (command)
{
case 'L':
x_pos--;
break;
case 'R':
x_pos++;
break;
case 'S':
break;
default:
throw runtime_error("invalid command:" + command);
}
if (output)
{
cout << command << endl;
}
}
void Game::attack()
{
int enemy_ind = get_enemy_index(x_pos);
if (enemy_ind == -1)
{
histories.push_back(History{-1, 0, 0, 0, x_pos});
return;
}
// 敵が見つかった
int my_power = 1 + earned_power / 100;
// 攻撃
int damage = min(my_power, enemies.at(enemy_ind).HP);
enemies.at(enemy_ind).HP -= damage;
// 敵が死んだ
if (enemies.at(enemy_ind).HP == 0)
{
earned_power += enemies.at(enemy_ind).power;
my_power += enemies.at(enemy_ind).power;
score += enemies.at(enemy_ind).max_HP;
poped_enemy.at(turn).push_back(enemy_queue.at(x_pos).front());
enemy_queue.at(x_pos).pop_front();
histories.push_back(History{
enemy_ind,
damage,
enemies.at(enemy_ind).max_HP,
enemies.at(enemy_ind).power,
x_pos});
}
else
{
histories.push_back(History{enemy_ind, damage, 0, 0, x_pos});
}
}
void Game::process_turn()
{
turn++;
}
int Game::get_enemy_index(int x)
{
while (!enemy_queue.at(x).empty())
{
int ind = enemy_queue.at(x).front();
if (enemies.at(ind).y < turn)
{
poped_enemy.at(turn).push_back(enemy_queue.at(x).front());
enemy_queue.at(x).pop_front();
continue;
}
return ind;
}
return -1;
}
bool Game::can_kill_enemy(int enemy_ind, int turns)
{
// 殺すのにturnsかかる
int diff = enemies[enemy_ind].y - turn - 1;
return diff > turns;
}
struct GreedyCommander
{
private:
Game *game;
int target_enemy;
int find_target();
bool will_die();
public:
GreedyCommander(Game *game) : game(game)
{
target_enemy = -1;
};
char get_command();
bool can_move(int dx);
char check_die(char command);
void set_target(int target) { target_enemy = target; };
bool is_target_alive() { return game->is_alive(target_enemy); };
};
int GreedyCommander::find_target()
{
int x = game->x_pos;
int current_power = game->earned_power / 100 + 1;
double best_efficiency = 0;
double best_enemy = -1;
for (int i = max(0, x - 8); i <= min(24, x + 8); i++)
{
int enemy_ind = game->get_enemy_index(i);
if (enemy_ind == -1)
continue;
int res_HP = game->enemies[enemy_ind].HP;
int turns = max(abs(x - i) - 1, 0) + res_HP / current_power;
if (res_HP % current_power != 0)
turns++;
if (!game->can_kill_enemy(enemy_ind, turns))
continue;
int sc;
if (game->earned_power / 100 >= 50)
{
sc = game->enemies[enemy_ind].max_HP;
}
else
{
sc = game->enemies[enemy_ind].power;
}
double eff = (double)sc / (double)turns;
if (eff > best_efficiency)
{
best_efficiency = eff;
best_enemy = enemy_ind;
}
}
return best_enemy;
}
bool GreedyCommander::can_move(int dx)
{
int x = game->x_pos + dx;
if (x < 0 || x >= 25)
return false;
int enemy_index = game->get_enemy_index(x);
if (enemy_index == -1)
return true;
int y = game->enemies[enemy_index].y;
if (y == game->turn || y == game->turn + 1)
return false;
return true;
}
char GreedyCommander::check_die(char command)
{
int dx;
switch (command)
{
case 'R':
dx = 1;
break;
case 'L':
dx = -1;
break;
case 'S':
dx = 0;
break;
}
if (can_move(dx))
{
return command;
}
for (int dx2 = -1; dx2 <= 1; dx2++)
{
if (dx2 == dx)
continue;
if (can_move(dx2))
{
switch (dx2)
{
case -1:
return 'L';
case 0:
return 'S';
case 1:
return 'R';
}
}
}
// cerr << "command:" << command << " x:" << game->x_pos << endl;
int enemy_ind = game->get_enemy_index(game->x_pos + dx);
// cerr << game->turn << " " << game->enemies[enemy_ind].y << endl;
// 諦める
return command;
}
char GreedyCommander::get_command()
{
if (target_enemy == -1 || !game->is_alive(target_enemy))
{
target_enemy = find_target();
}
char command;
if (target_enemy == -1)
{
command = 'S';
}
else
{
int enemy_x = game->enemies[target_enemy].x;
if (enemy_x == game->x_pos)
{
command = 'S';
}
else if (enemy_x < game->x_pos)
{
command = 'L';
}
else
{
command = 'R';
}
}
command = check_die(command);
return command;
}
// 30ターン先までを先読みして10ターン分の行動を決める
class ChokudaiCommander
{
private:
Game *game;
queue<char> command_queue;
void prepare_moves();
public:
ChokudaiCommander(Game *game) : game(game){};
char get_command();
bool can_move(int dx);
char check_die(char command);
};
void ChokudaiCommander::prepare_moves()
{
// queueに10ターン分くらいのコマンドを詰める
// Chokudaiサーチを20ms分やる
// 状態としてはvector<deque<int>>, スコア, power <- index
State initial_state = game->make_state();
int turn0 = initial_state.turn;
vector<priority_queue<P, vector<P>, greater<P>>> pqs(50);
vector<deque<int>> enemies = game->enemy_queue;
vector<State> states;
states.push_back(initial_state);
pqs.at(0).emplace(states[0].earned_power, 0);
float t0 = get_time(false);
GreedyCommander greedy = GreedyCommander(game);
int best_state = -1;
double best_eff = 0;
int count = 0;
while (true)
{
float ct = get_time(false);
if (ct - t0 > 35)
break;
int flag = 0;
for (int turn = 0; turn < 30; turn++)
{
if (pqs.at(turn).empty())
{
continue;
}
flag = 1;
auto [score, state_ind] = pqs.at(turn).top();
pqs.at(turn).pop();
game->process_turns(states[state_ind].commands);
vector<deque<int>> enemies2 = game->enemy_queue;
int x = game->x_pos;
int current_power = game->earned_power / 100 + 1;
for (int i = max(0, x - 8); i <= min(24, x + 8); i++)
{
int enemy_ind = game->get_enemy_index(i);
if (enemy_ind == -1)
continue;
int res_HP = game->enemies[enemy_ind].HP;
int turns = max(abs(x - i) - 1, 0) + res_HP / current_power;
if (res_HP % current_power != 0)
turns++;
if (!game->can_kill_enemy(enemy_ind, turns))
continue;
greedy.set_target(enemy_ind);
// cerr << "enemy:" << enemy_ind << " turn:" << turn << " alive:" << greedy.is_target_alive() << " target x:" << game->enemies[enemy_ind].x << " turns:" << turns << endl;
int turn_count = turn;
vector<char> commands = vector<char>(states[state_ind].commands);
bool game_over = false;
int initial_x = game->x_pos;
while (true)
{
if (!greedy.is_target_alive())
break;
char command = greedy.get_command();
// cerr << "command:" << command << " hp:" << game->enemies[enemy_ind].HP << endl;
commands.push_back(command);
game->move(command, false);
if (game->is_game_over())
{
game_over = true;
}
game->attack();
game->process_turn();
turn_count++;
if (game->is_game_over() || game_over)
{
game_over = true;
break;
}
}
// cerr << "turn:" << turn_count << " gameover?" << game_over << endl;
State next_state = game->make_state();
next_state.steps = states[state_ind].steps;
next_state.steps.push_back(turn_count);
rep(i, turn_count - turn)
{
game->roll_back_a_turn();
}
game->x_pos = initial_x;
game->enemy_queue = enemies2;
if (game_over)
continue;
if (turn_count >= 50)
continue;
// cerr << "next_state turn:" << turn_count << endl;
next_state.commands = commands;
states.push_back(next_state);
pqs.at(turn_count).emplace(next_state.earned_power, states.size() - 1);
int score;
if (initial_state.earned_power / 100 > 50)
{
score = next_state.score - initial_state.score;
}
else
{
score = next_state.earned_power - initial_state.earned_power;
}
if (best_eff < (double)score / (double)turn_count && turn_count >= 10)
{
best_eff = (double)score / (double)turn_count;
best_state = states.size() - 1;
}
// cerr << "end:" << turn << " " << turn_count << endl;
}
rep(i, turn)
{
game->roll_back_a_turn();
}
game->x_pos = initial_state.x;
game->enemy_queue = enemies;
}
count++;
if (flag == 0)
{
break;
}
}
// 30ターンよりも先を調べて、最もearned_powerの効率がよかったやつを採用する
// cerr << "turn:" << game->turn << " "
// << "count:" << count << " best_state:" << best_state << " best_eff:" << best_eff << endl;
if (best_state == -1)
{
command_queue.push('S');
}
else
{
int count = 0;
for (auto tmp : states[best_state].steps)
{
count = tmp;
if (count > 15)
break;
}
for (int i = 0; i < count && i < states[best_state].commands.size(); i++)
{
command_queue.push(states[best_state].commands.at(i));
}
}
}
char ChokudaiCommander::get_command()
{
if (command_queue.empty())
{
prepare_moves();
}
char result = command_queue.front();
command_queue.pop();
return result;
}
double T0 = 500.;
double T1 = 0;
int main(int argc, char *argv[])
{
#ifdef LOCAL
vec_int pp;
rep(i, 25)
{
int val;
cin >> val;
pp.push_back(val);
}
#endif
#ifdef OPTUNA_STUDY
cerr << "optuna study, override parameters" << endl;
T0 = stod(argv[1]);
T1 = stod(argv[2]);
#endif
get_time(true);
Game game = Game();
ChokudaiCommander commander = ChokudaiCommander(&game);
// GreedyCommander commander = GreedyCommander(&game);
rep(i, 1000)
{
game.process_turn();
if (game.is_game_over())
break;
int n;
cin >> n;
if (n == -1)
break;
game.pop_enemies(n);
char command = commander.get_command();
game.move(command, true);
// cerr << i << " " << game.turn << " " << game.x_pos << endl;
if (game.is_game_over())
break;
game.attack();
}
cerr << " time: " << get_time(false) << " turn:" << game.turn << " power:" << game.earned_power << " score:" << game.score << endl;
return 0;
}