結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2018-12-09 12:40:01 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.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 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 5,127 ms
42,704 KB |
| testcase_01 | AC | 5,140 ms
42,308 KB |
| testcase_02 | AC | 5,268 ms
43,016 KB |
| testcase_03 | AC | 5,207 ms
42,744 KB |
| testcase_04 | AC | 5,271 ms
43,180 KB |
| testcase_05 | AC | 5,089 ms
42,012 KB |
| testcase_06 | AC | 5,467 ms
43,716 KB |
| testcase_07 | AC | 5,239 ms
41,932 KB |
| testcase_08 | AC | 5,256 ms
43,812 KB |
| testcase_09 | AC | 5,125 ms
42,324 KB |
| testcase_10 | AC | 5,127 ms
43,720 KB |
| testcase_11 | AC | 5,187 ms
42,964 KB |
| testcase_12 | AC | 5,110 ms
40,532 KB |
| testcase_13 | AC | 5,236 ms
42,272 KB |
| testcase_14 | AC | 4,984 ms
40,440 KB |
| testcase_15 | AC | 5,176 ms
42,016 KB |
| testcase_16 | AC | 5,224 ms
43,672 KB |
| testcase_17 | AC | 5,426 ms
43,664 KB |
| testcase_18 | AC | 5,007 ms
42,392 KB |
| testcase_19 | AC | 5,069 ms
40,464 KB |
| testcase_20 | AC | 5,073 ms
43,124 KB |
| testcase_21 | AC | 5,163 ms
40,524 KB |
| testcase_22 | AC | 5,171 ms
42,048 KB |
| testcase_23 | AC | 5,349 ms
43,840 KB |
| testcase_24 | AC | 5,172 ms
42,116 KB |
| testcase_25 | AC | 5,044 ms
40,348 KB |
| testcase_26 | AC | 5,262 ms
43,716 KB |
| testcase_27 | AC | 5,096 ms
42,328 KB |
| testcase_28 | AC | 5,238 ms
42,832 KB |
| testcase_29 | AC | 5,055 ms
42,200 KB |
| testcase_30 | AC | 5,236 ms
42,872 KB |
| testcase_31 | AC | 5,237 ms
43,532 KB |
ソースコード
// #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;
}