結果

問題 No.5017 Tool-assisted Shooting
ユーザー takumi152takumi152
提出日時 2023-07-16 16:26:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 9,249 bytes
コンパイル時間 4,543 ms
コンパイル使用メモリ 281,740 KB
実行使用メモリ 24,504 KB
スコア 52,819
平均クエリ数 140.41
最終ジャッジ日時 2023-07-16 16:29:08
合計ジャッジ時間 160,189 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 404 ms
24,012 KB
testcase_01 TLE -
testcase_02 AC 787 ms
23,832 KB
testcase_03 AC 846 ms
24,384 KB
testcase_04 AC 399 ms
23,640 KB
testcase_05 TLE -
testcase_06 AC 882 ms
23,544 KB
testcase_07 TLE -
testcase_08 AC 384 ms
24,324 KB
testcase_09 TLE -
testcase_10 TLE -
testcase_11 AC 625 ms
23,592 KB
testcase_12 AC 438 ms
23,664 KB
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 AC 1,923 ms
23,868 KB
testcase_17 AC 302 ms
24,408 KB
testcase_18 AC 1,108 ms
23,412 KB
testcase_19 AC 776 ms
24,408 KB
testcase_20 AC 587 ms
24,468 KB
testcase_21 AC 420 ms
24,228 KB
testcase_22 TLE -
testcase_23 AC 704 ms
23,424 KB
testcase_24 AC 478 ms
23,376 KB
testcase_25 TLE -
testcase_26 TLE -
testcase_27 AC 587 ms
23,424 KB
testcase_28 AC 430 ms
23,388 KB
testcase_29 TLE -
testcase_30 TLE -
testcase_31 AC 1,928 ms
23,640 KB
testcase_32 AC 525 ms
23,544 KB
testcase_33 TLE -
testcase_34 AC 518 ms
23,532 KB
testcase_35 AC 455 ms
24,060 KB
testcase_36 AC 454 ms
23,640 KB
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 TLE -
testcase_42 AC 300 ms
23,544 KB
testcase_43 AC 638 ms
24,072 KB
testcase_44 AC 396 ms
23,388 KB
testcase_45 AC 580 ms
24,012 KB
testcase_46 AC 473 ms
24,000 KB
testcase_47 TLE -
testcase_48 TLE -
testcase_49 AC 560 ms
24,360 KB
testcase_50 TLE -
testcase_51 TLE -
testcase_52 AC 488 ms
24,024 KB
testcase_53 AC 656 ms
24,492 KB
testcase_54 AC 1,925 ms
23,640 KB
testcase_55 AC 363 ms
23,640 KB
testcase_56 TLE -
testcase_57 AC 488 ms
23,556 KB
testcase_58 AC 538 ms
23,664 KB
testcase_59 AC 514 ms
23,532 KB
testcase_60 TLE -
testcase_61 TLE -
testcase_62 TLE -
testcase_63 TLE -
testcase_64 TLE -
testcase_65 AC 315 ms
24,024 KB
testcase_66 TLE -
testcase_67 AC 642 ms
23,664 KB
testcase_68 AC 657 ms
24,384 KB
testcase_69 TLE -
testcase_70 AC 234 ms
23,820 KB
testcase_71 TLE -
testcase_72 AC 477 ms
23,376 KB
testcase_73 AC 1,385 ms
24,384 KB
testcase_74 AC 1,908 ms
23,640 KB
testcase_75 AC 764 ms
23,532 KB
testcase_76 AC 600 ms
24,252 KB
testcase_77 AC 360 ms
23,400 KB
testcase_78 AC 394 ms
24,336 KB
testcase_79 TLE -
testcase_80 AC 523 ms
23,388 KB
testcase_81 TLE -
testcase_82 TLE -
testcase_83 TLE -
testcase_84 TLE -
testcase_85 AC 628 ms
24,276 KB
testcase_86 AC 726 ms
24,408 KB
testcase_87 AC 635 ms
23,820 KB
testcase_88 AC 292 ms
23,664 KB
testcase_89 TLE -
testcase_90 AC 700 ms
24,060 KB
testcase_91 TLE -
testcase_92 TLE -
testcase_93 TLE -
testcase_94 AC 1,928 ms
24,468 KB
testcase_95 TLE -
testcase_96 TLE -
testcase_97 TLE -
testcase_98 TLE -
testcase_99 AC 445 ms
23,832 KB
権限があれば一括ダウンロードができます

ソースコード

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 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<vector<bool>> enemy_exist;
vector<vector<int>> enemy_initial_health;
vector<vector<int>> enemy_current_health;
vector<vector<int>> enemy_power;

// 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_exist = vector<vector<bool>>(turn_limit + field_height, vector<bool>(field_width));
  enemy_initial_health = vector<vector<int>>(turn_limit + field_height, vector<int>(field_width));
  enemy_current_health = vector<vector<int>>(turn_limit + field_height, vector<int>(field_width));
  enemy_power = vector<vector<int>>(turn_limit + field_height, vector<int>(field_width));

  enemy_probability.init();
}

void receive_turn_input() {
  int enemy_num;
  cin >> enemy_num;
  if (enemy_num == -1) {
    // game over
    exit(0);
  }
  for (int i = 0; i < enemy_num; i++) {
    int h, p, x;
    cin >> h >> p >> x;
    enemy_exist[turn_count + field_height][x] = true;
    enemy_initial_health[turn_count + field_height][x] = h;
    enemy_current_health[turn_count + field_height][x] = h;
    enemy_power[turn_count + field_height][x] = p;
  }

  enemy_probability.re_est(enemy_exist[turn_count + field_height]);
}

int simulate_playout(char next_command) {
  auto enemy_exist = ::enemy_exist;
  auto enemy_initial_health = ::enemy_initial_health;
  auto enemy_current_health = ::enemy_current_health;
  auto enemy_power = ::enemy_power;

  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_exist[turn_count][player_position]) {
      // game over
      break;
    }

    for (int i = 0; i < field_width; i++) {
      double roll = theRandom.nextDouble();
      if (roll < enemy_probability.P[i]) {
        enemy_exist[turn_count + field_height - 1][i] = true;

        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;
        enemy_initial_health[turn_count + field_height - 1][i] = max(1, (int) normal_distribution(enemy_health_avg, enemy_health_stddev)(theMersenne));
        enemy_current_health[turn_count + field_height - 1][i] = enemy_initial_health[turn_count + field_height - 1][i];

        double enemy_power_avg = enemy_power_avg_health_factor * enemy_initial_health[turn_count + field_height - 1][i];
        double enemy_power_stddev = enemy_power_stddev_health_factor * enemy_initial_health[turn_count + field_height - 1][i];
        enemy_power[turn_count + field_height - 1][i] = max(0, (int) normal_distribution(enemy_power_avg, enemy_power_stddev)(theMersenne));
      }
    }

    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_exist[turn_count][player_position]) {
      // game over
      break;
    }

    for (int x = turn_count; x < turn_count + field_height; x++) {
      if (enemy_exist[x][player_position]) {
        enemy_current_health[x][player_position] -= player_level;
        if (enemy_current_health[x][player_position] <= 0) {
          enemy_exist[x][player_position] = false;
          score += enemy_initial_health[x][player_position];
          power_gained += enemy_power[x][player_position];
          player_level = base_level + (power_gained / power_per_level);
        }
        break;
      }
    }
  }

  return score;
}

char decide_command() {
  const double time_limit = 0.00190 * (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;
  for (int x = turn_count; x < turn_count + field_height; x++) {
    if (enemy_exist[x][player_position]) {
      enemy_current_health[x][player_position] -= player_level;
      if (enemy_current_health[x][player_position] <= 0) {
        enemy_exist[x][player_position] = false;
        score += enemy_initial_health[x][player_position];
        power_gained += enemy_power[x][player_position];
        player_level = base_level + (power_gained / power_per_level);
      }
      break;
    }
  }
}

void solve() {
  while (true) {
    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;
}
0