#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") #include #include #include #include #include #include #include #include #include #include #include #include #include #include struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else // return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) // return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) // return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge #endif } }; using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef pair Pii; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937 theMersenne(1); // hyper parameters // enums // structs struct enemy { int initial_health; int current_health; int power; enemy(int health, int power) { this->initial_health = health; this->current_health = health; this->power = power; } }; struct Pi_est { vector n; vector P; // 推定値 int t = 0; void init() { n.resize(25, 0); P.resize(25, 0.045); } void re_est(vector x) { t++; for (int xtmp = 0; xtmp < 25; xtmp++){ if (x[xtmp]) n[xtmp]++; } for (int xtmp = 0; xtmp < 25; xtmp++) { P[xtmp] = (double)n[xtmp] / (double)t; P[xtmp] = max(0.01, P[xtmp]); P[xtmp] = min(0.08, P[xtmp]); } return; } }; // constants constexpr int turn_limit = 1000; constexpr int field_height = 60; constexpr int field_width = 25; constexpr int player_initial_position = 12; constexpr int base_level = 1; constexpr int power_per_level = 100; constexpr double enemy_health_avg_base = 7.5; constexpr double enemy_health_avg_turn_factor = 0.15; constexpr double enemy_health_stddev_base = 1.5; constexpr double enemy_health_stddev_turn_factor = 0.03; constexpr double enemy_power_avg_health_factor = 0.8; constexpr double enemy_power_stddev_health_factor = 0.1; // inputs vector>> enemy_queue; // internals int turn_count = 0; int player_position = player_initial_position; int score = 0; int player_level = base_level; int power_gained = 0; Pi_est enemy_probability; inline bool within_board(int x, int y, int r, int c) { return 0 <= x && x < r && 0 <= y && y < c; } void init() { enemy_queue = vector>>(field_width); enemy_probability.init(); } void receive_turn_input() { int enemy_num; cin >> enemy_num; if (enemy_num == -1) { // game over exit(0); } vector enemy_exist(field_width); for (int i = 0; i < enemy_num; i++) { int h, p, x; cin >> h >> p >> x; enemy_queue[x].emplace(turn_count + field_height, enemy(h, p)); enemy_exist[x] = true; } enemy_probability.re_est(enemy_exist); } int simulate_playout(char next_command) { auto enemy_queue = ::enemy_queue; auto turn_count = ::turn_count; auto player_position = ::player_position; auto score = ::score; auto player_level = ::player_level; auto power_gained = ::power_gained; bool is_next_turn = true; while (turn_count < turn_limit) { turn_count++; if (!enemy_queue[player_position].empty() && enemy_queue[player_position].front().first == turn_count) { // game over break; } for (int i = 0; i < field_width; i++) { double roll = theRandom.nextDouble(); if (roll < enemy_probability.P[i]) { double enemy_health_avg = enemy_health_avg_base + enemy_health_avg_turn_factor * turn_count; double enemy_health_stddev = enemy_health_stddev_base + enemy_health_stddev_turn_factor * turn_count; int enemy_health = max(1, (int) normal_distribution(enemy_health_avg, enemy_health_stddev)(theMersenne)); double enemy_power_avg = enemy_power_avg_health_factor * enemy_health; double enemy_power_stddev = enemy_power_stddev_health_factor * enemy_health; int enemy_power = max(0, (int) normal_distribution(enemy_power_avg, enemy_power_stddev)(theMersenne)); enemy_queue[i].emplace(turn_count + field_height - 1, enemy(enemy_health, enemy_power)); } } if (is_next_turn) { if (next_command == 'L') player_position = (player_position - 1 + field_width) % field_width; else if (next_command == 'R') player_position = (player_position + 1) % field_width; is_next_turn = false; } else { } if (!enemy_queue[player_position].empty() && enemy_queue[player_position].front().first == turn_count) { // game over break; } if (!enemy_queue[player_position].empty()) { auto& [_, target_enemy] = enemy_queue[player_position].front(); target_enemy.current_health -= player_level; if (target_enemy.current_health <= 0) { score += target_enemy.initial_health; power_gained += target_enemy.power; player_level = base_level + (power_gained / power_per_level); enemy_queue[player_position].pop(); } } for (int i = 0; i < field_width; i++) { if (enemy_queue[i].empty()) continue; auto [enemy_height, _] = enemy_queue[i].front(); if (enemy_height == turn_count) { enemy_queue[i].pop(); } } } return score; } char decide_command() { const double time_limit = 0.00100 * (turn_count + 1); int iter_count = 0; ll score_l = 0; ll score_s = 0; ll score_r = 0; do { score_l += simulate_playout('L'); score_s += simulate_playout('S'); score_r += simulate_playout('R'); iter_count++; } while (theTimer.time() < time_limit); #ifdef DEBUG cerr << "turn_count = " << setw(3) << turn_count << ", iter_count = " << setw(4) << iter_count << ", score_l = " << setw(6) << score_l / iter_count << ", score_s = " << setw(6) << score_s / iter_count << ", score_r = " << setw(6) << score_r / iter_count << endl; #endif if (score_l > score_s && score_l > score_r) return 'L'; else if (score_s > score_r) return 'S'; else return 'R'; } void turn_action(char command) { cout << command << endl; turn_count++; if (command == 'L') player_position = (player_position - 1 + field_width) % field_width; else if (command == 'R') player_position = (player_position + 1) % field_width; if (!enemy_queue[player_position].empty()) { auto& [_, target_enemy] = enemy_queue[player_position].front(); target_enemy.current_health -= player_level; if (target_enemy.current_health <= 0) { score += target_enemy.initial_health; power_gained += target_enemy.power; player_level = base_level + (power_gained / power_per_level); enemy_queue[player_position].pop(); } } for (int i = 0; i < field_width; i++) { if (enemy_queue[i].empty()) continue; auto [enemy_height, _] = enemy_queue[i].front(); if (enemy_height == turn_count) { enemy_queue[i].pop(); } } } void solve() { while (turn_count < turn_limit) { receive_turn_input(); char command = decide_command(); turn_action(command); } } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); init(); solve(); return 0; }