#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Ps = pair; using vec_int = vector; using P = pair; using P2 = pair; using P3 = pair; using T = tuple; using T2 = tuple; using T3 = tuple; using T4 = tuple; using T5 = tuple; using TT = tuple; 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 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(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 commands; vector steps; }; struct History { int enemy_index; int damage; int gained_score; int gained_power; int x; }; class Game { private: vector histories; vector poped_enemy; public: int earned_power; int turn; int score; int x_pos; vector> 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 enemies; bool can_kill_enemy(int enemy_ind, int turns); void roll_back_a_turn(); void process_turns(vector &commands); State make_state() { return State{ turn, score, earned_power, x_pos, vector(), {0}}; } }; Game::Game() { turn = 0; x_pos = 12; earned_power = 0; score = 0; enemy_queue = vector>(25); poped_enemy = vector(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 &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 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>, スコア, power <- index State initial_state = game->make_state(); int turn0 = initial_state.turn; vector> pqs(50); vector> enemies = game->enemy_queue; vector 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; int turn = game->turn; int res_turn = 1000 - turn; int res_step = res_turn / 15 + 2; float res_time = 1900 - t0; float duration = res_time / res_step; while (true) { float ct = get_time(false); if (ct - t0 > duration) 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> 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 commands = vector(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); 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; } pqs.at(turn_count).emplace(score, 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; }