#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; }; class Game { private: PseudoSet alive_enemies; vector> enemy_queue; public: int earned_power; int turn; int score; int x_pos; Game(); void move(char command); 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; } int get_enemy_index(int x); vector enemies; bool can_kill_enemy(int enemy_ind, int turns); }; Game::Game() { turn = 0; x_pos = 12; earned_power = 0; score = 0; enemy_queue = vector>(25); } 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 (turn == 368) { cerr << "enemy_ind:" << enemy_ind << " " << enemies[enemy_ind].y << " " << enemies[enemy_ind].HP << endl; } 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) { switch (command) { case 'L': x_pos--; break; case 'R': x_pos++; break; case 'S': break; default: throw runtime_error("invalid command"); } cout << command << endl; } void Game::attack() { int enemy_ind = get_enemy_index(x_pos); if (enemy_ind == -1) return; // 敵が見つかった int my_power = 1 + earned_power / 100; // 攻撃 enemies.at(enemy_ind).HP = max(0, enemies.at(enemy_ind).HP - my_power); // 敵が死んだ 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; enemy_queue.at(x_pos).pop_front(); } } 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) { enemy_queue.at(x).pop_front(); continue; } return ind; } return -1; } bool Game::can_kill_enemy(int enemy_ind, int turns) { int diff = enemies[enemy_ind].y - turn; 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); }; 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++; // cerr << "turns:" << turns << " enemy:" << enemy_ind << endl; if (!game->can_kill_enemy(enemy_ind, turns)) continue; int power = game->enemies[enemy_ind].power; double eff = (double)power / (double)turns; // cerr << i << " " << eff << " " << enemy_ind << " " << game->turn << endl; 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(); } if (target_enemy == -1) return 'S'; char command; 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; } 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(); 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); if (game.is_game_over()) break; game.attack(); } cerr << " turn:" << game.turn << " power:" << game.earned_power << " score:" << game.score << endl; return 0; }