#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); } double calc_score(vector& column_kill_order, double score_factor, double power_factor) { 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; int column_index = 0; int target_position = !column_kill_order.empty() ? column_kill_order[0] : 0; while (turn_count < min(turn_limit, turn_count + field_height)) { turn_count++; if (!enemy_queue[player_position].empty() && enemy_queue[player_position].front().first == turn_count) { // game over score -= 100000; power_gained -= 100000; break; } if (player_position != target_position) { int left_dist = player_position >= target_position ? player_position - target_position : (player_position + field_width) - target_position; int right_dist = target_position >= player_position ? target_position - player_position : (target_position + field_width) - player_position; if (left_dist < right_dist) player_position = (player_position - 1 + field_width) % field_width; else player_position = (player_position + 1) % field_width; } if (!enemy_queue[player_position].empty() && enemy_queue[player_position].front().first == turn_count) { // game over score -= 100000; power_gained -= 100000; 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(); if (player_position == target_position) { column_index++; if (column_index >= (int) column_kill_order.size()) { // all enemy killed return score; } target_position = column_kill_order[column_index]; } } } 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_factor * score + power_factor * power_gained; } char decide_command() { static vector column_kill_order; { vector column_count(field_width); for (auto &c: column_kill_order) column_count[c]++; for (int i = 0; i < field_width; i++) { if (column_count[i] > (int) enemy_queue[i].size()) { column_kill_order.erase((find_if(column_kill_order.rbegin(), column_kill_order.rend(), [&](auto x){return x == i;}) + 1).base()); } if (!enemy_queue[i].empty() && enemy_queue[i].back().first == turn_count + field_height) { column_kill_order.push_back(i); } } } double score_factor = (double) turn_count / (double) turn_limit; double power_factor = 1.0 - (double) turn_count / (double) turn_limit; double score = calc_score(column_kill_order, score_factor, power_factor); double last_score = score; double best_score = score; const double base_temperature = 1e0; const double target_temperature = 1e-2; // const double decay_rate = 4e-5; double temperature = base_temperature; double time_start = theTimer.time(); const double time_limit = 0.00190 * (turn_count + 1); int iter_count = 0; while (theTimer.time() < time_limit) { double roll = theRandom.nextDouble(); if (roll < 0.50) { int idx1 = theRandom.nextUIntMod(column_kill_order.size()); int idx2 = theRandom.nextUIntMod(column_kill_order.size()); if (idx1 == idx2) continue; if (idx1 > field_height / 6 && idx2 > field_height / 6) continue; swap(column_kill_order[idx1], column_kill_order[idx2]); score = calc_score(column_kill_order, score_factor, power_factor); if (score >= last_score) { last_score = score; if (score > best_score) { best_score = score; } } else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // accept last_score = score; } else { // rollback swap(column_kill_order[idx1], column_kill_order[idx2]); score = last_score; } } else if (roll < 1.00) { int idx1 = theRandom.nextUIntMod(column_kill_order.size()); int idx2 = theRandom.nextUIntMod(column_kill_order.size()); if (idx1 == idx2) continue; if (idx1 > field_height / 6 && idx2 > field_height / 6) continue; int element_to_move = column_kill_order[idx1]; column_kill_order.erase(column_kill_order.begin() + idx1); column_kill_order.insert(column_kill_order.begin() + idx2, element_to_move); score = calc_score(column_kill_order, score_factor, power_factor); if (score >= last_score) { last_score = score; if (score > best_score) { best_score = score; } } else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // accept last_score = score; } else { // rollback column_kill_order.erase(column_kill_order.begin() + idx2); column_kill_order.insert(column_kill_order.begin() + idx1, element_to_move); score = last_score; } } // temperature *= 1.0 - decay_rate; temperature = exp(log(base_temperature) - ((log(base_temperature) - log(target_temperature)) * ((theTimer.time() - time_start) * (1.0 / (time_limit - time_start))))); iter_count++; } // cerr << "iter_count = " << iter_count << endl; // cerr << "score = " << score << endl; // cerr << "best_score = " << best_score << endl; // cerr << "temperature = " << temperature << endl; cerr << "turn_count = " << setw(3) << turn_count << ", iter_count = " << setw(5) << iter_count << ", score = " << setw(9) << fixed << setprecision(2) << score << ", best_score = " << setw(9) << fixed << setprecision(2) << best_score << endl; if (column_kill_order.empty()) return 'S'; int target_position = column_kill_order[0]; if (player_position == target_position) return 'S'; int left_dist = player_position >= target_position ? player_position - target_position : (player_position + field_width) - target_position; int right_dist = target_position >= player_position ? target_position - player_position : (target_position + field_width) - player_position; if (left_dist < right_dist) return 'L'; 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; }