結果
問題 | No.5017 Tool-assisted Shooting |
ユーザー |
|
提出日時 | 2023-07-16 17:25:35 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,025 ms / 2,000 ms |
コード長 | 8,938 bytes |
コンパイル時間 | 4,362 ms |
コンパイル使用メモリ | 269,992 KB |
実行使用メモリ | 24,348 KB |
スコア | 576,770 |
平均クエリ数 | 833.45 |
最終ジャッジ日時 | 2023-07-16 17:27:17 |
合計ジャッジ時間 | 95,664 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#pragma GCC optimize ("O3")#pragma GCC optimize ("unroll-loops")#pragma GCC target ("avx2")#include <iostream>#include <iomanip>#include <vector>#include <algorithm>#include <utility>#include <string>#include <queue>#include <stack>#include <unordered_set>#include <unordered_map>#include <random>#include <cmath>#include <cassert>#include <x86intrin.h>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 LOCALreturn (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<int, int> Pii;const ll mod = 1000000007;timer theTimer;xorshift64 theRandom;mt19937 theMersenne(1);// hyper parameters// enums// structsstruct 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<int> n;vector<double> P; // 推定値int t = 0;void init() {n.resize(25, 0);P.resize(25, 0.045);}void re_est(vector<bool> 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;}};// constantsconstexpr 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;// inputsvector<queue<pair<int, enemy>>> enemy_queue;// internalsint 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<queue<pair<int, enemy>>>(field_width);enemy_probability.init();}void receive_turn_input() {int enemy_num;cin >> enemy_num;if (enemy_num == -1) {// game overexit(0);}vector<bool> 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 overbreak;}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 overbreak;}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 DEBUGcerr << "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;#endifif (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;}