#302821 (C++17(gcc12)) No.5003 物理好きクリッカー

• 問題: No.5003 物理好きクリッカー
• ユーザー: koyumeishi
• 提出日時: 2018-12-09 12:40:01
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 5,467 ms / 10,000 ms
• コード長: 20,115 bytes
• コンパイル時間: 2,958 ms
• 実行使用メモリ: 43,840 KB
• スコア: 315,853,972,335
• 平均クエリ数: 10000.00
• 最終ジャッジ日時: 2021-07-19 09:15:11
• 合計ジャッジ時間: 184,781 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

ファイルパターン	結果
other	AC * 32

ソースコード

// #pragma GCC optimize ("-Ofast")

#ifdef LOCAL_TEST
#define _GLIBCXX_DEBUG
#endif
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
#include <memory>
#include <unordered_map>
#include <array>
#include <fstream>
#include <numeric>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator   end(){ return range_iterator(  end_, step_); } };

  inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

  mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

  template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }

  inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}

namespace timer{
  using namespace chrono;
  steady_clock::time_point start_time;
  unsigned long long begin_time;
  unsigned long long int get_cycle()
  {
    unsigned int low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
  }

  void init(){
    start_time = steady_clock::now();
    begin_time = get_cycle();
  }

  double sec_per_cycle(){
    auto end_time = steady_clock::now();
    double elapsed = duration_cast<nanoseconds>(end_time - start_time).count() * 1e-9;
    return elapsed / (get_cycle() - begin_time);
  }

  // [sec]
  double get()
  {
    static double spc = sec_per_cycle();
    return (double)(get_cycle() - begin_time) * spc;
  }

};

class XorShift{
public:
  uint32_t x;
  uint32_t y;
  uint32_t z;
  uint32_t w;

  XorShift(){
    x = 123456789;
    y = 362436069;
    z = 521288629;
    w = 88675123;
  }
  
  XorShift(uint32_t seed){
    x = 123456789;
    y = 362436069;
    z = 521288629;
    w = seed;

    for(int i=0; i<100; i++){
      next();
    }
  }
  
  uint32_t next() {
    uint32_t t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
  }

  uint32_t operator () () {
    return next();
  }

  // [0, range)
  int operator () (int range){
    return (((long long)next()) * range) >> 32 ;
  }

  // [0, 1.0]
  double prob(){
    return (next()&0xfffffff) * 3.7252903123397e-9; // 0xfffffff = 268,435,455 = 2^28-1
  }

  template<class T>
  T& operator()(vector<T>& v){
    return v[ next()%v.size() ];
  }

  template<class T>
  void shuffle(vector<T>& v){
    int n = v.size();
    for(int i=0; i<n; i++){
      int j = (*this)(n-i) + i;
      swap(v[i], v[j]);
    }
  }
};

XorShift rng(114514);

using Int = int64_t; // __int128 ?

enum class Facility{
  CLICK = 0,
  HAND = 1,
  LILY = 2,
  FACTORY = 3,
  CASINO = 4,
  GRIMOIRE = 5,
  NONE = 6
};

enum class Command{
  CLICK = 0,
  BUY = 1,
  SELL = 2,
  REINFORCE = 3,
  ENHCLICK = 4,
  NOTHING = 5
};

constexpr int num_facilities = 6;
constexpr int num_commands = 6;

array<string, num_facilities> facility_name{
  "click"s,
  "hand"s,
  "lily"s,
  "factory"s,
  "casino"s,
  "grimoire"s
};

array<string, num_commands> command_name{
  "click"s,
  "buy"s,
  "sell"s,
  "reinforce"s,
  "enhclick"s,
  "nothing"s
};

string get_command_str(Command cmd, Facility target){
  if(cmd == Command::CLICK){
    return command_name[(int)cmd];
  }else if(target == Facility::NONE){
    return command_name[(int)cmd];
  }else{
    if(target == Facility::CLICK)
      return command_name[(int)Command::ENHCLICK];
    return command_name[(int)cmd] + " " + facility_name[(int)target];
  }
}

array<vector<Int>, num_facilities> buy_price{
  vector<Int>{-1},
  vector<Int>{150},
  vector<Int>{2000},
  vector<Int>{30000},
  vector<Int>{600000},
  vector<Int>{10000000}
};

array<vector<Int>, num_facilities> enh_price{
  vector<Int>{15},
  vector<Int>{1500},
  vector<Int>{20000},
  vector<Int>{300000},
  vector<Int>{6000000},
  vector<Int>{100000000}
};

array<vector<Int>, num_facilities> prod{
  vector<Int>{1},
  vector<Int>{1},
  vector<Int>{10},
  vector<Int>{120},
  vector<Int>{2000},
  vector<Int>{25000}
};

Int next_buy_price(Int p){
  return (p * 6 + 4) / 5;
}
void init_buy_price(){
  for(int i=1; i<num_facilities; i++){
    while(true){
      buy_price[i].emplace_back(next_buy_price(buy_price[i].back()));
      if(buy_price[i].back() > (1ll<<40)) break;
    }
  }
}

Int next_enh_price(Int p){
  return p * 10;
}
void init_enh_price(){
  for(int i=0; i<num_facilities; i++){
    while(true){
      enh_price[i].emplace_back(next_enh_price(enh_price[i].back()));
      if(enh_price[i].back() > (1ll<<40)) break;
    }
  }
}

Int next_prod(Int p){
  return p * 2;
}
void init_prod(){
  for(int i=0; i<num_facilities; i++){
    while(true){
      prod[i].emplace_back(next_prod(prod[i].back()));
      if(prod[i].back() > (1ll<<40)) break;
    }
  }
}

array<Int, num_facilities> level_hash{};
array<Int, num_facilities> cnt_hash{};
void init_hash(){
  for(int i=0; i<num_facilities; i++){
    level_hash[i] = rng();
    cnt_hash[i] = rng();
  }
}

void init_facilities(){
  eprint("initializing facilities ... ");
  init_buy_price();
  init_enh_price();
  init_prod();
  init_hash();
  eprintln("completed");
}


struct dp_state{
  Int cookie;
  int prev_idx;
  int last_command;
  int step;
};
array<array<dp_state, 50>, 10005> table{};

struct state{
  Int click;
  Int prod_per_turn;
  Int pay;
  array<char, num_facilities> level{};
  array<char, num_facilities> cnt{};
};
array<state, 400> st{};

struct beam_state{
  // Int cookie;
  vector<Int> phase_cookie;
  vector<int> v;
  int64_t hash;
  array<int, num_facilities> level{};
  array<int, num_facilities> cnt{};
};


int n;
string S;
array<int, 10005> fever{};


class Solver{
 public:

  Solver(istream& is){
    is >> n;
    is >> S;
    init();
  }

  void init(){
    S = "N" + S;
    for(int i=1; i<S.size(); i++){
      if(S[i] == 'F'){
        fever[i] = 20;
      }
      fever[i] = max<int>(fever[i-1] - 1, fever[i]);
    }

    init_facilities();
  }

  void solve(){
    beam_search();
  }

  int turn_step = 25;
  vector<Int> get_phase_cookie(){
    vector<Int> res;
    for(int s=turn_step; s<=n; s+=turn_step){
      res.emplace_back(table[s][0].cookie);
    }
    return res;
  }

  void beam_search(){
    constexpr int bw = 2;
    array<array<beam_state, bw * 24>, 2> beam;
    vector<int> basic = {
      (int)Command::REINFORCE * 8 + (int)Facility::CLICK,
    };
    array<int, num_facilities> cnt__{};
    array<int, num_facilities> lev__{};
    for(int f=0; f<num_facilities; f++){
      cnt__[f] = count(basic.begin(), basic.end(), (int)Command::BUY*8 + f);
      lev__[f] = count(basic.begin(), basic.end(), (int)Command::REINFORCE*8 + f);
    }
    cnt__[0] = 1;
    dp(basic);
    beam[0][0] = {
      get_phase_cookie(),
      basic,
      // dp({}),
      // {},
      0,
      lev__,
      cnt__
    };

    beam_state best_state = beam[0][0];

    eprintln("initial state =", best_state.phase_cookie.back());
    // return;

    vector<pair<Int, int>> cur_idx = {{0, 0}};
    array<pair<Int,int>, bw * 24> next_idx;

    int prev_bw = 1;
    for(int opr=0, i=0; opr<n/turn_step; opr++){
      for(int ii=0; ii<(opr+1 == n/turn_step ? 10 : 1); ii++, i++){
        int next_bw_size = 0;

        for(int j=0; j<prev_bw; j++){
          int jj = cur_idx[j].second;
          auto& last = beam[i&1][jj];

          { // hold
            auto& next = beam[~i&1][next_bw_size];
            next = last;
            next_idx[next_bw_size] = {
              -next.phase_cookie[opr],
              next_bw_size
            };
            next_bw_size++;
          }

          for(int b=1; b<num_facilities; b++){ // buy
            Int pay = buy_price[b][last.cnt[b]];
            if(last.phase_cookie[opr] < pay) continue;

            auto& next = beam[~i&1][next_bw_size];
            next = last;
            next.v.push_back( ((int)Command::BUY * 8) | b);
            Int score = dp(next.v);
            if(score < 0) continue;
            next.phase_cookie = get_phase_cookie();
            next.cnt[b]++;
            next.hash += cnt_hash[b];

            next_idx[next_bw_size] = {
              -next.phase_cookie[opr],
              next_bw_size
            };
            next_bw_size++;
          }
          for(int b=0; b<num_facilities; b++){ // enh
            if(last.cnt[b] == 0) continue;

            Int pay = enh_price[b][last.level[b]];
            if(last.phase_cookie[opr] < pay) continue;

            auto& next = beam[~i&1][next_bw_size];
            next = last;
            next.v.push_back( ((int)Command::REINFORCE * 8) | b);
            if(b)
              next.v.push_back( ((int)Command::BUY * 8) | b);

            Int score = dp(next.v);
            if(score < 0) continue;
            next.phase_cookie = get_phase_cookie();
            next.level[b]++;
            next.hash += level_hash[b];

            next_idx[next_bw_size] = {
              -next.phase_cookie[opr],
              next_bw_size
            };
            next_bw_size++;
          }
        }

        unordered_map<Int, int> used;
        int w = 0;
        prev_bw = min(bw, next_bw_size);
        cur_idx = vector<pair<Int,int>>{};

        eprintln(next_bw_size);

        for(int j=0; w<prev_bw && j<next_bw_size; ){
          int r = min({bw - w, next_bw_size - w, next_bw_size - j});
          if(r == 0) break;
          assert(r>0);
          assert(j+r <= next_bw_size);

          nth_element(next_idx.begin() + j, next_idx.begin() + j + r, next_idx.begin() + next_bw_size);
          sort(next_idx.begin() + j, next_idx.begin() + j + r);

          for(int k=j; k<j+r && w < prev_bw && k<next_bw_size; k++){
            if(used.count(beam[~i&1][next_idx[k].second].hash)) continue;
            used[beam[~i&1][next_idx[k].second].hash]++;
            w++;
            cur_idx.emplace_back(next_idx[k]);
          }
          j += r;
        }

        prev_bw = cur_idx.size();

        // eprintln(cur_idx);

        if(beam[~i&1][next_idx[0].second].phase_cookie.back() > best_state.phase_cookie.back()){
          best_state = beam[~i&1][next_idx[0].second];
        }

        eprintln("#operation =", i+1, ", best score =", best_state.phase_cookie.back() * 1e-9);
      }
    }

    // restore(best_state.v);

    dp(best_state.v);
    eprintln("hoge");
    optimize_sell(best_state.v);
  }

  // cmd * 8 | facility
  Int dp(const vector<int>& command){
    st[0] = state{
      1,
      0,
      0,
      {0, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 0}
    };

    for(int i=0; i<command.size(); i++){
      auto& st_ = st[i+1];
      st_ = st[i];

      int c = command[i] >> 3;
      int f = command[i] & 7;
      if(c == (int)Command::BUY){
        st_.prod_per_turn += prod[f][st_.level[f]];
        st_.pay = buy_price[f][st_.cnt[f]];
        st_.cnt[f]++;
      }else if(c == (int)Command::REINFORCE){
        Int diff = prod[f][st_.level[f] + 1] - prod[f][st_.level[f]];
        if(f == (int)Facility::CLICK){
          st_.click += diff;
        }else{
          st_.prod_per_turn += diff * st_.cnt[f];
        }
        st_.pay = enh_price[f][st_.level[f]];
        st_.level[f]++;
      }
    }

    table[0][0] = dp_state{
      0,
      -1,
      -1,
      0
    };

    int last_size = 1;
    for(int i=0; i<n; i++){
      int current_size = 0;
      // for(int j=0; j<last_size; j++){
      for(int j=max(0, last_size-13); j<last_size; j++){
        auto& last = table[i][j];
        { // click
          dp_state next = last;
          Int gain = st[last.step].click + st[last.step].prod_per_turn;
          if(fever[i]){
            gain *= 7;
          }
          next.cookie += gain;
          next.prev_idx = j;
          next.last_command = (int)Command::CLICK * 8;
          next.step = last.step;

          if(S[i+1] == 'B'){
            next.cookie = (next.cookie * 101 + 99) / 100;
          }
          while(current_size && table[i+1][current_size-1].cookie <= next.cookie){
            current_size--;
          }

          if(current_size == 0 || table[i+1][current_size-1].step != next.step){
            table[i+1][current_size++] = next;
          }
        }

        if(last.step < command.size()){ // next step
          dp_state next = last;
          Int pay = st[last.step + 1].pay;
          if(last.cookie - pay < 0) continue;
          if(S[i] == 'S'){
            pay = (pay  * 90 + 99) / 100;
          }
          Int gain = st[last.step + 1].prod_per_turn;
          if(fever[i]){
            gain *= 7;
          }
          next.cookie = last.cookie - pay + gain;
          next.prev_idx = j;
          next.last_command = command[last.step];
          next.step = last.step + 1;

          if(S[i+1] == 'B'){
            next.cookie = (next.cookie * 101 + 99) / 100;
          }

          while(current_size && table[i+1][current_size-1].cookie <= next.cookie){
            current_size--;
          }

          if(current_size == 0 || table[i+1][current_size-1].step != next.step){
            table[i+1][current_size++] = next;
          }
        }
      }

      last_size = current_size;
    }

    if(table[n][0].step != command.size()) return -1;
    return table[n][last_size-1].cookie;
  }

  Int optimize_sell(const vector<int>& command){
    int back = 70;

    state last = st[command.size()];
    pair<Int, vector<int>> best = pair<Int, vector<int>>{table[n-back][0].cookie, {}};

    vector<int> ord = {(int)Facility::FACTORY ,(int)Facility::CASINO, (int)Facility::GRIMOIRE};
    sort(ord.begin(), ord.end(), [&](int a, int b){
      return prod[a][last.level[a]] < prod[b][last.level[b]];
    });

    map<vector<int>, pair<Int, vector<int>>> sell_dp;
    vector<int> initial_vec = vector<int>{
      last.cnt[ord[0]],
      last.cnt[ord[1]],
      last.cnt[ord[2]]};
    sell_dp[initial_vec] = pair<Int, vector<int>>{table[n-back][0].cookie, {}};

    for(int i=n-back; i<n; i++){
      map<vector<int>, pair<Int, vector<int>>> sell_dp_;
      for(auto cur: sell_dp){
        if(cur.first == initial_vec){ // click
          Int gain = last.click + last.prod_per_turn;
          for(int j=0; j<ord.size(); j++){
            gain -= prod[ord[j]][last.level[ord[j]]] * (last.cnt[ord[j]] - cur.first[j]);
          }
          if(fever[i]){
            gain *= 7;
          }
          Int next_cookie = cur.second.first + gain;
          if(S[i+1] == 'B'){
            next_cookie = (next_cookie * 101 + 99) / 100;
          }
          vector<int> next_state = cur.first;
          vector<int> next_v = cur.second.second;
          next_v.push_back((int)Command::CLICK * 8);
          if(sell_dp_.count(next_state) == 0 || sell_dp_[next_state].first < next_cookie){
            sell_dp_[next_state] = pair<Int, vector<int>>{next_cookie, next_v};
          }
        }
        for(int j=0; j<3; j++){
          if(cur.first[j] && (j == ord.size()-1 || cur.first[j+1] == last.cnt[ord[j+1]]) ){
            Int next_cookie = cur.second.first + (buy_price[ord[j]][cur.first[j] - 1] * 25 + 99) / 100;
            Int gain = last.click + last.prod_per_turn;
            for(int jj=0; jj<ord.size(); jj++){
              gain -= prod[ord[jj]][last.level[ord[jj]]] * (last.cnt[ord[jj]] - (cur.first[jj] + (jj==j ? -1 : 0)) );
            }
            if(fever[i]){
              gain *= 7;
            }
            next_cookie += gain;
            if(S[i+1] == 'B'){
              next_cookie = (next_cookie * 101 + 99) / 100;
            }
            vector<int> next_state = cur.first;
            next_state[j]--;
            vector<int> next_v = cur.second.second;
            next_v.push_back((int)Command::SELL * 8 + ord[j]);
            if(sell_dp_.count(next_state) == 0 || sell_dp_[next_state].first < next_cookie){
              sell_dp_[next_state] = pair<Int, vector<int>>{next_cookie, next_v};
            }
          }
        }
      }

      swap(sell_dp, sell_dp_);
    }

    for(auto cur: sell_dp){
      if(best.first < cur.second.first){
        best = cur.second;
      }
    }

    eprintln("score after selling = ", best.first * 1e-9);
    // restore(command);
    // restore(best.second);
    auto res = restore_from_dp();
    for(int i=0; i<back; i++){
      res.pop_back();
    }
    for(auto m: best.second){
      res.emplace_back((Command)(m>>3), (Facility)(m&7));
    }

    output(res);
    return best.first;
  }

  vector<pair<Command, Facility>> restore_from_dp(){
    vector<pair<Command, Facility>> res;
    int i = n;
    int j = 0;

    while(i){
      auto& st = table[i][j];
      int i_ = i-1;
      int j_ = st.prev_idx;

      res.emplace_back((Command)(st.last_command >> 3), (Facility)(st.last_command & 7));
      i = i_;
      j = j_;
    }

    reverse(res.begin(), res.end());
    return res;
  }

  vector<int> restore(const vector<int>& command){
    for(int i=0; i<command.size(); i++){
      int c = command[i] >> 3;
      int f = command[i] & 7;
      eprintln(command_name[c], facility_name[f]);
    }
    return {};
  }

  void output(vector<pair<Command, Facility>>& res){
    assert(res.size() == n);
    string tmp;
    for(int i=0; i<n; i++){
      println(get_command_str(res[i].first, res[i].second));
      cin >> tmp;
      assert(tmp == "ok"s);
    }
  }
};

int main(int argc, char* argv[]){
  timer::init();
  for(int i=1; i+1<argc; i++){
  }
  Solver sol(cin);
  sol.solve();

  eprintln("time elapsed :", timer::get()*1000, "[ms]");

  return 0;
}