結果

問題 No.5017 Tool-assisted Shooting
ユーザー takumi152
提出日時 2023-07-16 18:42:31
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,932 ms / 2,000 ms
コード長 12,460 bytes
コンパイル時間 4,332 ms
コンパイル使用メモリ 267,916 KB
実行使用メモリ 24,384 KB
スコア 1,588,036
平均クエリ数 985.75
最終ジャッジ日時 2023-07-16 18:45:57
合計ジャッジ時間 200,872 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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);
}
double calc_score(vector<int>& 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<int> column_kill_order;
  {
    vector<int> 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.begin(), column_kill_order.end(), [&](auto x){return x == i;}));
      }
      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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0