#301343 (C++14) No.5003 物理好きクリッカー

提出ソース
結果

問題	No.5003 物理好きクリッカー
ユーザー	koyumeishi
提出日時	2018-12-04 12:38:37
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	18,927 bytes
コンパイル時間	2,087 ms
実行使用メモリ	40,832 KB
スコア	109,329,098,792
平均クエリ数	7287.81
最終ジャッジ日時	2021-07-19 08:21:17
合計ジャッジ時間	48,221 ms
ジャッジサーバーID （参考情報）	judge14 / judge10
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	AC	1,082 ms 40,036 KB
testcase_03	RE	-
testcase_04	RE	-
testcase_05	AC	1,098 ms 39,772 KB
testcase_06	AC	1,044 ms 39,936 KB
testcase_07	AC	1,057 ms 39,712 KB
testcase_08	AC	1,045 ms 40,072 KB
testcase_09	AC	1,040 ms 39,712 KB
testcase_10	AC	1,047 ms 40,156 KB
testcase_11	AC	1,045 ms 39,872 KB
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	AC	1,075 ms 39,780 KB
testcase_16	RE	-
testcase_17	AC	1,097 ms 39,768 KB
testcase_18	AC	1,021 ms 39,756 KB
testcase_19	RE	-
testcase_20	RE	-
testcase_21	AC	1,102 ms 40,080 KB
testcase_22	AC	1,047 ms 39,980 KB
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	AC	1,086 ms 39,616 KB
testcase_31	RE	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC optimize ("-Ofast")

#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 <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(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;
  return ceil((p * 6.0) / 5);
}

Int get_buy_price(Facility f, int cnt){
  if((int)buy_price[(int)f].size() <= cnt){
    buy_price[(int)f].emplace_back(next_buy_price(buy_price[(int)f].back()));
  }
  return buy_price[(int)f][cnt];
}

Int next_enh_price(Int p){
  return p * 10;
}

Int get_enh_price(Facility f, int level){
  if((int)enh_price[(int)f].size() <= level){
    enh_price[(int)f].emplace_back(next_enh_price(enh_price[(int)f].back()));
  }
  return enh_price[(int)f][level];
}

Int next_prod(Int p){
  return p * 2;
}

Int get_prod(Facility f, int level){
  if((int)prod[(int)f].size() <= level){
    prod[(int)f].emplace_back(next_prod(prod[(int)f].back()));
  }
  return prod[(int)f][level];
}

struct Movement{
  int turn;
  Command cmd;
  Facility target;
  // shared_ptr<Movement> prev;
  int prev;
};
struct State{
  Int cookie = 0;
  Int cookie_prod_per_turn = 0;
  Int future_cookies = 0;
  array<int, num_facilities> facility_cnt{};
  array<int, num_facilities> facility_level{};
  // shared_ptr<Movement> movement;
  int movement;
  long long hash = 0;
};


// constexpr int beam_width = 800;
constexpr int beam_width = 100;
constexpr int num_next_state = 5*3 + 3;
constexpr int same_state_limt = 1;

template<size_t L, class T>
struct my_pool{
  array<T, L> pool;
  array<int, L> idx;
  int size = 0;
  my_pool(){
    iota(idx.begin(), idx.end(), 0);
  }
  int get(){
    return idx[size++];
  }
  void erase(int i){
    idx[--size] = i;
  }
  int set(const T& v){
    int i = get();
    pool[i] = v;
    return i;
  }
};

array<array<State, beam_width * num_next_state>, 3> beam_pool{};

array<Int, num_facilities> zhash_facility_cnt{};
array<Int, num_facilities> zhash_facility_level{};


int main(){
  timer::init();

  int n;
  cin >> n;
  string s;
  cin >> s;

  // init

  my_pool<10005 * beam_width + beam_width * num_next_state, Movement> movement_pool;

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

  for(int& i: fever){
    i = min(i, 1);
  }

  vector<int> fever_acc = fever;
  for(int i=1; i<(int)fever_acc.size(); i++){
    fever_acc[i] += fever_acc[i-1];
  }

  vector<int> next_bonus(s.size(), 0);
  for(int i=0; i<(int)s.size(); i++){
    if(s[i] == 'B'){
      next_bonus[i] = 1;
    }
  }
  for(int i=s.size()-2; i>=0; i--){
    next_bonus[i] += next_bonus[i+1];
  }

  for(int i=0; i<num_facilities; i++){
    zhash_facility_level[i] = rng();
    zhash_facility_cnt[i] = rng();
  }

  int num_check_point = 12;
  int check_point_interval = n / num_check_point;

  vector<vector<long double>> gain_coeff(num_check_point, vector<long double>(s.size(), 0.0));
  for(int w=0; w<num_check_point; w++){
    int j = s.size()-1 - s.size() * w / num_check_point;
    for(int i=j-1; i>=0; i--){
      gain_coeff[w][i] = pow(1.01, next_bonus[i] - next_bonus[j]) * (fever[i]*6 + 1);
      gain_coeff[w][i] += gain_coeff[w][i + 1];
    }
  }

  auto calc_future_cookies = [&](State& state, int turn){
    turn++;
    static int check_point = 0;
    static int j = 0;

    static int i = -1;
    static double pk = 1;
    if(i != turn){
      i = turn;
      check_point = max<int>(0, num_check_point-2 - turn / check_point_interval);
      j = s.size() - 1 - s.size() * check_point / check_point_interval;
      pk = pow(1.01, next_bonus[turn] - next_bonus[j]);
    }

    Int res = ceil(
      state.cookie * pk +
      gain_coeff[check_point][turn] * (state.cookie_prod_per_turn + get_prod(Facility::CLICK, state.facility_level[(int)Facility::CLICK]))
      );

    // Int res = 0;
    // Int k = 1;
    // for(int c=0; c<num_check_point; c++){
    //   int j = s.size() - 1 - s.size() * c / check_point_interval;
    //   if(j < turn) break;
    //   res += ceil(
    //     state.cookie * pow(1.01, next_bonus[turn] - next_bonus[j]) +
    //     gain_coeff[c][turn] * (state.cookie_prod_per_turn + get_prod(Facility::CLICK, state.facility_level[(int)Facility::CLICK]))
    //     ) * k;
    //   k *= 10;
    // }
    return res;
  };


  // beam search

  vector<int> prev_beam_ids {0};
  beam_pool[0][0] = State{
  };
  beam_pool[0][0].facility_cnt[0] = 1;
  beam_pool[0][0].cookie = 0;

  for(int i=0; i<n; i++){
    int next_pool_size = 0;
    int next_pool_index = (i+1) % 3;

    // eprintln("turn=", i,
    //   ", cookies = ", beam_pool[i%3][prev_beam_ids[0]].cookie,
    //   ", future_cookies = ", beam_pool[i%3][prev_beam_ids[0]].future_cookies);
    // eprintln("beam_size =", prev_beam_ids.size());

    for(auto bid: prev_beam_ids){
      auto& state = beam_pool[i%3][bid];

      { // click (nothing)
        auto& next_state = beam_pool[next_pool_index][next_pool_size++];
        Int gain = get_prod(Facility::CLICK, state.facility_level[(int)Facility::CLICK]);
        if(fever[i]){
          gain *= 7;
        }
        next_state.cookie = state.cookie + gain;
        next_state.cookie_prod_per_turn = state.cookie_prod_per_turn;
        next_state.facility_cnt = state.facility_cnt;
        next_state.facility_level = state.facility_level;
        next_state.movement = movement_pool.set( Movement{
        // next_state.movement = make_shared<Movement>(Movement{
          i,
          Command::CLICK,
          Facility::NONE,
          state.movement
        });
        next_state.hash = state.hash;
      }
      { // buy
        for(int j=1; j<=5; j++){
          Int next_price = get_buy_price((Facility)j, state.facility_cnt[j]);
          if(s[i] == 'S'){
            next_price = (next_price * 90 + 99) / 100;
            // next_price = ceil(next_price * 0.9);
          }
          if(state.cookie < next_price) continue;

          auto& next_state = beam_pool[next_pool_index][next_pool_size++];
          next_state.cookie = state.cookie - next_price;
          next_state.cookie_prod_per_turn = state.cookie_prod_per_turn
            + get_prod((Facility)j, state.facility_level[j]);
          next_state.facility_cnt = state.facility_cnt;
          next_state.facility_cnt[j]++;
          next_state.facility_level = state.facility_level;
          next_state.movement = movement_pool.set( Movement{
          // next_state.movement = make_shared<Movement>(Movement{
            i,
            Command::BUY,
            (Facility)j,
            state.movement
          });
          next_state.hash = state.hash + zhash_facility_cnt[j];
        }
      }
      { // enhance
        for(int j=0; j<=5; j++){
          if(state.facility_cnt[j] == 0) continue;
          Int next_price = get_enh_price((Facility)j, state.facility_level[j]);
          if(s[i] == 'S'){
            next_price = (next_price * 90 + 99) / 100;
            // next_price = ceil(next_price * 0.9);
          }
          if(state.cookie < next_price) continue;
          Int diff = j == 0 ? 0 :
            get_prod((Facility)j, state.facility_level[j] + 1) -
            get_prod((Facility)j, state.facility_level[j]);

          auto& next_state = beam_pool[next_pool_index][next_pool_size++];
          next_state.cookie = state.cookie - next_price;
          next_state.cookie_prod_per_turn = state.cookie_prod_per_turn +
            diff * state.facility_cnt[j];
          next_state.facility_cnt = state.facility_cnt;
          next_state.facility_level = state.facility_level;
          next_state.facility_level[j]++;
          next_state.movement = movement_pool.set( Movement{
          // next_state.movement = make_shared<Movement>(Movement{
            i,
            Command::REINFORCE,
            (Facility)j,
            state.movement
          });
          next_state.hash = state.hash + zhash_facility_level[j];
        }
      }
      if( i > 9975 ){ // sell
        for(int j=1; j<=5; j++){
          if(state.facility_cnt[j] == 0) continue;
          Int sell_price = (get_buy_price((Facility)j, state.facility_cnt[j]-1) * 25 + 99) / 100;
          // Int sell_price = ceil(get_buy_price((Facility)j, state.facility_cnt[j]-1) * 0.25);

          auto& next_state = beam_pool[next_pool_index][next_pool_size++];
          next_state.cookie = state.cookie + sell_price;
          next_state.cookie_prod_per_turn = state.cookie_prod_per_turn -
            get_prod((Facility)j, state.facility_level[j]);
          next_state.facility_cnt = state.facility_cnt;
          next_state.facility_cnt[j]--;
          next_state.facility_level = state.facility_level;
          next_state.movement = movement_pool.set( Movement{
          // next_state.movement = make_shared<Movement>(Movement{
            i,
            Command::SELL,
            (Facility)j,
            state.movement
          });
          next_state.hash = state.hash - zhash_facility_cnt[j];
        }
      }

    }

    vector<pair<Int, int>> idx(next_pool_size);

    for(int b=0; b<next_pool_size; b++){
      auto& state = beam_pool[next_pool_index][b];
      Int gain = state.cookie_prod_per_turn;
      if(fever[i]){
        gain *= 7;
      }
      state.cookie += gain;

      if(s[i] == 'B'){
        state.cookie = (state.cookie * 101 + 99) / 100;
        // state.cookie = ceil(state.cookie * 1.01);
      }

      state.future_cookies = calc_future_cookies(state, i);

      idx[b] = {-state.future_cookies, b};
    }

    int sz = min(next_pool_size, beam_width);
    // sort(idx.begin(), idx.end());

    vector<int> next_beam_ids;
    // map<Int, int> used;
    unordered_map<Int, int> used;

    // for(int j=0; j<(int)idx.size(); j++){
    //   auto& state = beam_pool[next_pool_index][idx[j].second];
    //   if(used[state.hash] == same_state_limt || (int)next_beam_ids.size() >= sz){
    //     movement_pool.erase(state.movement);
    //     continue;
    //   };
    //   next_beam_ids.emplace_back(idx[j].second);
    //   used[state.hash]++;
    // }

    int offset = 0;
    while(idx.size()){
      sz = min<int>(idx.size() - offset, beam_width - next_beam_ids.size());

      if(sz<=0){
        for(int j=0; j + offset<idx.size(); j++){
          auto& state = beam_pool[next_pool_index][idx[j + offset].second];
          movement_pool.erase(state.movement);
        }
        break;
      }

      nth_element(idx.begin() + offset, idx.begin()+sz + offset, idx.end());
      sort(idx.begin() + offset, idx.begin()+sz + offset);
      for(int j=0; j<sz; j++){
        auto& state = beam_pool[next_pool_index][idx[j+offset].second];
        if(used[state.hash] == same_state_limt){
          movement_pool.erase(state.movement);
          continue;
        };
        next_beam_ids.emplace_back(idx[j+offset].second);
        used[state.hash]++;
      }

      // idx = move(decltype(idx)(idx.begin()+sz, idx.end()));
      offset += sz;
    }

    prev_beam_ids = move(next_beam_ids);
  }

  {
    vector<pair<Int, int>> idx;
    auto& pool = beam_pool[n%3];

    for(auto bid: prev_beam_ids){
      auto& state = pool[bid];
      idx.emplace_back(-state.cookie, bid);
    }

    sort(idx.begin(), idx.end());

    auto& best_state = pool[idx.front().second];

    vector<pair<Command, Facility>> res;
    // shared_ptr<Movement> last_move = best_state.movement;
    Movement* last_move = &(movement_pool.pool[best_state.movement]);
    while(true){
      res.emplace_back(last_move -> cmd, last_move -> target);
      if(last_move -> turn == 0) break;
      // last_move = last_move -> prev;
      last_move = &(movement_pool.pool[last_move -> prev]);
    }

    assert(res.size() == n);

    eprintln("completd in ", timer::get()*1000, "[ms]");
    eprintln("score = ", best_state.cookie * 1e-9);

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

    for(int i=0; i<n; i++){
      #ifndef LOCAL_TEST
        println(get_command_str(res[i].first, res[i].second));
        string response;
        cin >> response;
        // assert(response == "ok"s);
        assert(response != "-1"s);
      #else
        // if(res[i].first != Command::CLICK){
        //   println("turn =", i, ", cmd = ", get_command_str(res[i].first, res[i].second));
        // }
      #endif
    }
  }

  // for(int i=0; i<num_facilities; i++){
  //   eprintln(facility_name[i]);
  //   eprintln("buy price:", buy_price[i].size());
  //   eprintln("enh price:", enh_price[i].size());
  // }

  return 0;
}
yukicoder

結果

テストケース

ソースコード
