結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2018-12-04 14:05:29 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 6,733 ms / 10,000 ms |
| コード長 | 19,837 bytes |
| コンパイル時間 | 4,148 ms |
| 実行使用メモリ | 156,124 KB |
| スコア | 251,963,851,688 |
| 平均クエリ数 | 10000.00 |
| 最終ジャッジ日時 | 2021-07-19 08:27:49 |
| 合計ジャッジ時間 | 227,131 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 6,293 ms
152,648 KB |
| testcase_01 | AC | 6,340 ms
152,268 KB |
| testcase_02 | AC | 6,315 ms
152,448 KB |
| testcase_03 | AC | 6,541 ms
153,196 KB |
| testcase_04 | AC | 6,642 ms
155,492 KB |
| testcase_05 | AC | 6,635 ms
153,312 KB |
| testcase_06 | AC | 6,508 ms
153,684 KB |
| testcase_07 | AC | 6,413 ms
153,944 KB |
| testcase_08 | AC | 6,449 ms
154,284 KB |
| testcase_09 | AC | 6,383 ms
153,256 KB |
| testcase_10 | AC | 6,335 ms
153,744 KB |
| testcase_11 | AC | 6,545 ms
153,332 KB |
| testcase_12 | AC | 6,215 ms
152,684 KB |
| testcase_13 | AC | 6,506 ms
152,472 KB |
| testcase_14 | AC | 6,081 ms
152,128 KB |
| testcase_15 | AC | 6,278 ms
152,980 KB |
| testcase_16 | AC | 6,292 ms
152,272 KB |
| testcase_17 | AC | 6,332 ms
152,472 KB |
| testcase_18 | AC | 6,149 ms
152,776 KB |
| testcase_19 | AC | 6,384 ms
153,620 KB |
| testcase_20 | AC | 6,340 ms
153,812 KB |
| testcase_21 | AC | 6,639 ms
153,904 KB |
| testcase_22 | AC | 6,562 ms
153,220 KB |
| testcase_23 | AC | 6,526 ms
153,844 KB |
| testcase_24 | AC | 6,619 ms
153,340 KB |
| testcase_25 | AC | 6,469 ms
152,480 KB |
| testcase_26 | AC | 6,402 ms
153,324 KB |
| testcase_27 | AC | 6,350 ms
151,800 KB |
| testcase_28 | AC | 6,310 ms
152,364 KB |
| testcase_29 | AC | 6,204 ms
152,720 KB |
| testcase_30 | AC | 6,486 ms
152,984 KB |
| testcase_31 | AC | 6,733 ms
153,732 KB |
ソースコード
#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){
// Int hoge = (p * 6 + 4) / 5;
// Int res = ceil(p*6.0 / 5.0);
// assert(res == hoge);
// return res;
return (p * 6 + 4) / 5;
// return p * 12 / 10 + !!(p * 12 % 10);
}
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 = -1;
long long hash = 0;
};
constexpr int beam_width = 700;
// 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=1; i<(int)s.size(); i++){
if(s[i] == 'B'){
next_bonus[i-1] = 1;
// 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;
beam_pool[0][0].cookie_prod_per_turn = 0;
beam_pool[0][0].future_cookies = 0;
beam_pool[0][0].hash = 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'){
// Int hoge = ceil(next_price * 0.9);
// Int hoge = next_price = (next_price * 90) / 100 + !!(next_price * 90 % 100);
next_price = (next_price * 90 + 99) / 100;
// if(hoge != next_price){
// eprintln(hoge, next_price);
// }
// assert(hoge == next_price);
}
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'){
// Int hoge = ceil(next_price * 0.9);
next_price = (next_price * 90 + 99) / 100;
// Int hoge = next_price = (next_price * 90) / 100 + !!(next_price * 90 % 100);
// if(hoge != next_price){
// eprintln(hoge, next_price);
// }
// assert(hoge == next_price);
}
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 hoge = ceil(get_buy_price((Facility)j, state.facility_cnt[j]-1) * 0.25);
// assert(hoge == sell_price);
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+1] == 'B'){
// Int hoge = state.cookie + ceil(state.cookie * 0.01);
state.cookie = (state.cookie * 101 + 99) / 100;
// state.cookie += (state.cookie * 001 + 99) / 100;
// assert(hoge == state.cookie);
}
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]);
// eprintln("enh price:", enh_price[i]);
// eprintln("enh price:", prod[i]);
// }
return 0;
}