結果

問題 No.5017 Tool-assisted Shooting
ユーザー takumi152
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 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<int, int> 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<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;
}
};
// 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<queue<pair<int, enemy>>> 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<queue<pair<int, enemy>>>(field_width);
enemy_probability.init();
}
void receive_turn_input() {
int enemy_num;
cin >> enemy_num;
if (enemy_num == -1) {
// game over
exit(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 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0