結果
| 問題 | No.5003 物理好きクリッカー |
| ユーザー |
 komori3
|
| 提出日時 | 2018-12-08 00:59:26 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,740 ms / 10,000 ms |
| コード長 | 26,208 bytes |
| コンパイル時間 | 4,327 ms |
| 実行使用メモリ | 22,008 KB |
| スコア | 303,644,738,670 |
| 平均クエリ数 | 9999.53 |
| 最終ジャッジ日時 | 2021-07-19 09:08:32 |
| 合計ジャッジ時間 | 51,862 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,620 ms
21,864 KB |
| testcase_01 | AC | 1,318 ms
21,852 KB |
| testcase_02 | AC | 1,364 ms
21,348 KB |
| testcase_03 | AC | 1,195 ms
21,936 KB |
| testcase_04 | AC | 1,292 ms
21,360 KB |
| testcase_05 | AC | 1,417 ms
21,360 KB |
| testcase_06 | AC | 1,008 ms
21,900 KB |
| testcase_07 | AC | 1,263 ms
21,516 KB |
| testcase_08 | AC | 1,217 ms
21,540 KB |
| testcase_09 | AC | 1,181 ms
21,852 KB |
| testcase_10 | AC | 975 ms
21,864 KB |
| testcase_11 | AC | 1,206 ms
21,852 KB |
| testcase_12 | AC | 1,563 ms
21,852 KB |
| testcase_13 | AC | 1,270 ms
21,888 KB |
| testcase_14 | AC | 1,484 ms
21,840 KB |
| testcase_15 | AC | 1,256 ms
21,840 KB |
| testcase_16 | AC | 1,449 ms
21,516 KB |
| testcase_17 | AC | 775 ms
21,372 KB |
| testcase_18 | AC | 1,601 ms
21,504 KB |
| testcase_19 | AC | 1,440 ms
21,684 KB |
| testcase_20 | AC | 1,637 ms
21,360 KB |
| testcase_21 | AC | 1,254 ms
21,528 KB |
| testcase_22 | AC | 1,151 ms
21,360 KB |
| testcase_23 | AC | 1,021 ms
21,300 KB |
| testcase_24 | AC | 1,445 ms
21,336 KB |
| testcase_25 | AC | 1,327 ms
21,348 KB |
| testcase_26 | AC | 1,198 ms
21,672 KB |
| testcase_27 | AC | 1,740 ms
21,888 KB |
| testcase_28 | AC | 1,420 ms
21,840 KB |
| testcase_29 | AC | 1,469 ms
21,516 KB |
| testcase_30 | AC | 1,239 ms
21,360 KB |
| testcase_31 | AC | 881 ms
21,492 KB |
コンパイルメッセージ
main.cpp: 関数 ‘bool State::greedy()’ 内:
main.cpp:300:17: 警告: ‘best_bld’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
300 | while (!action(act, bld)) {
| ~~~~~~^~~~~~~~~~
main.cpp:369:8: 備考: ‘best_bld’ はここで定義されています
369 | EBld best_bld;
| ^~~~~~~~
main.cpp:300:17: 警告: ‘best_act’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
300 | while (!action(act, bld)) {
| ~~~~~~^~~~~~~~~~
main.cpp:368:8: 備考: ‘best_act’ はここで定義されています
368 | EAct best_act;
| ^~~~~~~~
ソースコード
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#include <iostream>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <array>
#ifdef _MSC_VER
//#include <opencv2/core.hpp>
//#include <opencv2/highgui.hpp>
//#include <opencv2/imgproc.hpp>
#include <ppl.h>
//#include <windows.h>
#endif
using namespace std;
//呪文
#define DUMPOUT cerr
#define dump(...) DUMPOUT<<" ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<" ";dump_func(__VA_ARGS__)
typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss;
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const pair<_KTy, _Ty>& m) { o << "{" << m.first << ", " << m.second << "}"; return o; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const unordered_map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const vector<_Ty>& v) { if (v.empty()) { o << "{ }"; return o; } o << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const unordered_set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const stack<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } stack<_Ty> t(s); o << "{" << t.top(); t.pop(); while (!t.empty()) { o << ", " << t.top(); t.pop(); } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const list<_Ty>& l) { if (l.empty()) { o << "{ }"; return o; } o << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { o << ", " << *itr; } o << "}"; return o; }
template <typename _KTy, typename _Ty> istream& operator >> (istream& is, pair<_KTy, _Ty>& m) { is >> m.first >> m.second; return is; }
template <typename _Ty> istream& operator >> (istream& is, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) is >> v[i]; return is; }
namespace aux { // print tuple
template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } };
template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& v) { os << get<N>(v); } };
}
template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys) - 1>::print(os, t); os << "}"; return os; }
template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); }
#define PI 3.14159265358979323846
#define EPS 1e-10
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define all(j) (j).begin(), (j).end()
#define SZ(j) ((int)(j).size())
#define fake false
struct SXor128 {
unsigned x, y, z, w;
SXor128() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; }
SXor128(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
void setSeed() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; }
void setSeed(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
unsigned nextUInt() {
unsigned t = (x ^ (x << 11));
x = y; y = z; z = w;
return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
unsigned nextUInt(unsigned mod) {
unsigned t = (x ^ (x << 11));
x = y; y = z; z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
return w % mod;
}
unsigned nextUInt(unsigned l, unsigned r) {
unsigned t = (x ^ (x << 11));
x = y; y = z; z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
return w % (r - l + 1) + l;
}
double nextDouble() {
return double(nextUInt()) / UINT_MAX;
}
} rnd;
class timer {
vector<timer> timers;
int n = 0;
public:
#ifdef _MSC_VER
double limit = 9.9;
#else
double limit = 9.9;
#endif
double t = 0;
timer() {}
timer(int size) : timers(size) {}
bool elapses() const {
return time() - t > limit;
}
void measure() {
t = time() - t;
++n;
}
void measure(char id) {
timers[id].measure();
}
void print() {
if (n % 2)
measure();
for (int i = 0; i < 128; ++i) {
if (timers[i].n)
cerr << (char)i << ' ' << timers[i].t << 's' << endl;
}
cerr << " " << t << 's' << endl;
}
static double time() {
#ifdef _MSC_VER
return __rdtsc() / 2.6e9;
#else
unsigned long long a, d;
__asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
return (d << 32 | a) / 2.6e9;
#endif
}
} timer(128);
constexpr int N = 10000;
//string S;
const vector<ll> base_cost({ 150, 2000, 30000, 600000, 10000000 });
const vector<ll> base_prod({ 1, 10, 120, 2000, 25000 });
enum EAct { CLICK, BUY, SELL, REINFORCE, ENHCLICK, NOTHING };
const vector<EAct> acts({ CLICK, BUY, REINFORCE, ENHCLICK, SELL });
const map<string, EAct> dict_acts_se({ { "click", CLICK },{ "buy", BUY },{ "sell", SELL },{ "reinforce", REINFORCE },{ "enhclick", ENHCLICK },{ "nothing", NOTHING } });
const map<EAct, string> dict_acts_es({ { CLICK, "click" } ,{ BUY, "buy" },{ SELL, "sell" },{ REINFORCE, "reinforce" },{ ENHCLICK, "enhclick" },{ NOTHING, "nothing" } });
enum EBld { HAND, LILY, FACTORY, CASINO, GRIMOIRE, NONE };
const vector<EBld> blds({ HAND, LILY, FACTORY, CASINO, GRIMOIRE });
const map<string, EBld> dict_blds_se({ { "hand", HAND },{ "lily", LILY },{ "factory", FACTORY },{ "casino", CASINO },{ "grimoire", GRIMOIRE },{ "none", NONE } });
const map<EBld, string> dict_blds_es({ { HAND, "hand" },{ LILY,"lily" },{ FACTORY,"factory" },{ CASINO, "casino" },{ GRIMOIRE,"grimoire" },{ NONE,"none" } });
enum EEff { FEVER = 1, SALE = 2 };
class State {
public:
typedef shared_ptr<State> StatePtr;
shared_ptr<string> S;
// history : 解答出力用．あとで undo とか実装するかも
array<char, N> hist_act;
array<char, N> hist_bld;
// ターン数
int turn;
// effect のフラグ
int eff_state;
// effect の残りターン数
int eff_turn[3];
// 所持クッキー
ll cookies;
// cookies per click
ll cpc;
// 施設保有数
short num_blds[5];
// 基本生産性
ll prod[5];
// 購入コスト
ll cost_buy[5];
// 施設強化コスト
ll cost_rif[5];
// クリック強化コスト
ll cost_enhclk;
State() {
turn = 0;
cookies = 0;
cpc = 1;
eff_state = eff_turn[FEVER] = eff_turn[SALE] = 0;
for (const auto& act : acts) {
num_blds[act] = 0;
prod[act] = base_prod[act];
cost_buy[act] = cost_rif[act] = base_cost[act];
cost_rif[act] *= 10;
}
cost_enhclk = 15;
}
// 行動．行動不可能(クッキー不足, 施設数 0 での売却)の場合 false が返る
bool action(EAct act, EBld bld) {
// 消費クッキーの計算
ll gains = 0, losts = 0, sells = 0;
switch (act)
{
case CLICK: gains = cpc; break;
case BUY: losts = cost_buy[bld]; break;
case SELL:
if (!num_blds[bld]) return false; // 売る施設がないよ
sells = cost_buy[bld] * 5 / 6; // 現在の施設価格
sells = (sells + 3) / 4; // 25%
break;
case REINFORCE: losts = cost_rif[bld]; break;
case ENHCLICK: losts = cost_enhclk; break;
}
ll diff =
gains * ((eff_state & FEVER) ? 7 : 1)
+ sells
- ((eff_state & SALE) ? (losts * 9 + 9) / 10 : losts);
// クッキー不足
if (cookies + diff < 0) return false;
// 各種 status の更新
switch (act)
{
case BUY:
num_blds[bld]++;
cost_buy[bld] = (cost_buy[bld] * 6 + 4) / 5;
break;
case SELL:
num_blds[bld]--;
cost_buy[bld] = cost_buy[bld] * 5 / 6;
break;
case REINFORCE:
prod[bld] <<= 1;
cost_rif[bld] *= 10;
break;
case ENHCLICK:
cpc <<= 1;
cost_enhclk *= 10;
break;
}
// history に追加
hist_act[turn] = act;
hist_bld[turn] = bld;
// 行動によるクッキー総数の更新
cookies += diff;
// 生産によるクッキー総数の更新
ll fever_const = (eff_state & FEVER) ? 7 : 1;
for (const auto& bld : blds) cookies += num_blds[bld] * prod[bld] * fever_const;
// 特殊効果のターン減少
eff_turn[FEVER]--;
eff_turn[SALE]--;
eff_state ^= eff_turn[FEVER] ? 0 : FEVER;
eff_state ^= eff_turn[SALE] ? 0 : SALE;
// 特殊効果の発動
switch (S->at(turn))
{
case 'B':
cookies = (cookies * 101 + 99) / 100;
break;
case 'F':
eff_state |= FEVER;
eff_turn[FEVER] = 20;
break;
case 'S':
eff_state |= SALE;
eff_turn[SALE] = 1;
break;
}
// ターン数インクリメント
turn++;
return true;
}
// 巻き戻し
void rewind(int t) {
// 履歴以外を初期化
turn = 0;
cookies = 0;
cpc = 1;
eff_state = eff_turn[FEVER] = eff_turn[SALE] = 0;
for (const auto& act : acts) {
num_blds[act] = 0;
prod[act] = base_prod[act];
cost_buy[act] = cost_rif[act] = base_cost[act];
cost_rif[act] *= 10;
}
cost_enhclk = 15;
// t ステップ進む
for (int i = 0; i < t; i++)
action(EAct(hist_act[i]), EBld(hist_bld[i]));
}
// 十分なクッキーが集まるまで click してからコマンドを実行
bool autoplay(EAct act, EBld bld, int turn_range = N) {
int cur_turn = turn;
while (!action(act, bld)) {
action(CLICK, NONE);
// turn_range ターン経過した場合は false
if (turn >= min(N, cur_turn + turn_range)) return false;
}
return true;
}
// 最も高い施設を売却する
bool sell_highest() {
ll max_sell = INT64_MIN;
EBld max_bld = NONE;
for (auto bld : blds) {
if (!num_blds[bld]) continue;
ll sell = cost_buy[bld] * 5 / 6;
sell = (sell + 3) / 4;
if (max_sell < sell) {
max_sell = sell;
max_bld = bld;
}
}
if (max_bld == NONE) return false;
action(SELL, max_bld);
return true;
}
// n ターンにわたって生産量の低い施設から売却していく
bool sell_blds(int n) {
vector<pll> candidates; // (prod, bld)
ll cost_cpy[5], num_cpy[5];
REP(i, 5) {
cost_cpy[i] = cost_buy[i];
num_cpy[i] = num_blds[i];
}
for (int i = 0; i < n; i++) {
ll max_sell = INT64_MIN;
EBld max_bld = NONE;
for (auto bld : blds) {
if (!num_cpy[bld]) continue;
ll sell = cost_cpy[bld] * 5 / 6;
sell = (sell + 3) / 4;
if (max_sell < sell) {
max_sell = sell;
max_bld = bld;
}
}
if (max_bld == NONE) return false;
candidates.emplace_back(prod[max_bld], max_bld);
cost_cpy[max_bld] = cost_cpy[max_bld] * 5 / 6;
}
sort(all(candidates));
for (auto& e : candidates)
action(SELL, EBld(e.second));
return true;
}
// 効率のいい ( Log(1+ΔCpT/CpT)/T の最も大きな ) ものを貪欲に実行する
// https://ita.hatenadiary.jp/entry/20130920/p1
// undo があるといいんだけど
bool greedy() {
ll cur_turn = turn;
ll cur_prod_sum = 0;
for (auto bld : blds)
cur_prod_sum += num_blds[bld] * prod[bld];
cur_prod_sum += cpc;
double best_score = DBL_MIN;
EAct best_act;
EBld best_bld;
for (auto act : { BUY, REINFORCE, ENHCLICK }) {
auto bs = (act == ENHCLICK ? vector<EBld>({ NONE }) : blds);
for (auto bld : blds) {
State next_state(*this);
if (!next_state.autoplay(act, bld)) continue;
ll next_turn = next_state.turn;
ll next_prod_sum = 0;
for (auto b : blds)
next_prod_sum += next_state.num_blds[b] * next_state.prod[b];
next_prod_sum += cpc;
double score = log(1 + double(next_prod_sum - cur_prod_sum) / next_prod_sum) / (next_turn - cur_turn);
if (score > best_score) {
best_score = score;
best_act = act;
best_bld = bld;
}
}
}
if (best_score == DBL_MIN) return false;
autoplay(best_act, best_bld);
return true;
}
ll prod_sum() {
ll res = 0;
for (auto bld : blds)
res += prod[bld] * num_blds[bld];
res += cpc;
return res;
}
void show_log(ostream& os) {
map<char, int> eff_cnt;
for (auto s : *S) {
if (s != 'N') {
eff_cnt[s]++;
os << s;
}
}
os << endl;
os << eff_cnt << endl;
for (int i = 0; i < turn; i++) {
EAct act = EAct(hist_act[i]);
EBld bld = EBld(hist_bld[i]);
if (act == CLICK) continue;
os << dict_acts_es.at(act);
if (bld != NONE) os << " " << dict_blds_es.at(bld);
os << endl;
}
}
};
typedef shared_ptr<State> StatePtr;
StatePtr solve(const StatePtr& init_state) {
init_state->autoplay(ENHCLICK, NONE);
init_state->autoplay(ENHCLICK, NONE);
ll best_cookies = init_state->cookies;
StatePtr best_state = init_state;
SXor128 r(init_state->cookies % 1000000007);
StatePtr state(new State(*init_state));
map<int, ll> turns_prods;
while (state->turn < N) {
state->greedy();
ll prods = 0;
REP(i, 5) prods += state->prod[i] * state->num_blds[i];
prods += state->cpc;
turns_prods[state->turn] = prods;
}
if (state->turn != N) cerr << state->turn << endl;
// 0 ターンまで巻き戻し
state->rewind(0);
for (int i = 0; i < N; i++) {
state->action(EAct(state->hist_act[i]), EBld(state->hist_bld[i]));
// 5000 ターン以降のキーフレーム
if (state->turn >= 5000 && turns_prods.find(state->turn) != turns_prods.end()) {
// 全部クリック
for (int i = 40; i >= 0; i--) {
StatePtr s(new State(*state));
for (int t = s->turn; t < N - i; t++)
s->action(CLICK, NONE);
//cerr << "before sell: " << s->cookies << ", ";
//for (int t = s->turn; t < N; t++) s->sell_highest();
if (!s->sell_blds(i)) cerr << "error!" << endl;
//cerr << "after sell: " << s->cookies << endl;
//cerr << state->turn << ": " << s->cookies << endl;
if (best_cookies < s->cookies) {
best_cookies = s->cookies;
best_state = s;
}
}
}
}
//cerr << loopcnt << endl;
return best_state;
}
//State BeamSearch(State FirstState) {
// Heap<State> HNowStates = new Heap<State>();
// HNowState.push(FirstState) :
// int k = 100; // ビーム幅
// for (size_t t = 0; t < MaxTurn; t++) {
// Heap<State> HNextStates = new Heap<State>();
// for (size_t i = 0; i < k; i++) {
// if (HNowStates.top == null) break;
// var NowState = HNowStates.pop();
// foreach(var NextState in NowState.GetAllNextState()) {
// HNextStates.push(NextState);
// }
// }
// HNowStates = HNextStates;
// }
// var BestState = HNowStates.pop();
// return BestState;
//}
typedef pair<double, StatePtr> Obj;
bool operator < (const Obj& a, const Obj& b) {
return a.first == b.first ? a.second->prod_sum() > b.second->prod_sum() : a.first < b.first;
}
bool operator < (const StatePtr& a, const StatePtr& b) {
return a->prod_sum() > b->prod_sum();
}
vector<Obj> getAllNextState(const Obj& obj) {
vector<Obj> res;
const auto& state = obj.second;
ll cur_turn = state->turn;
ll cur_prod_sum = state->prod_sum();
for (auto act : { BUY, REINFORCE, ENHCLICK }) {
auto bs = (act == ENHCLICK ? vector<EBld>({ NONE }) : blds);
for (auto bld : blds) {
StatePtr next_state(new State(*state));
if (!next_state->autoplay(act, bld)) continue;
ll next_turn = next_state->turn;
ll next_prod_sum = next_state->prod_sum();
double score = log(1.0 + double(next_prod_sum - cur_prod_sum) / next_prod_sum) / (next_turn - cur_turn);
res.emplace_back(score, next_state);
}
}
return res;
}
StatePtr beam_search(const StatePtr& init_state) {
priority_queue<StatePtr> best_states;
StatePtr state(new State(*init_state));
priority_queue<Obj> now_states;
now_states.emplace(0.0, state);
ll max_prod = 0;
int width = 1;
int loopcnt = 0;
while (!now_states.empty()) {
priority_queue<Obj> next_states;
for (int i = 0; i < width; i++) {
if (now_states.empty()) break;
//set<double> scores;
auto now_state = now_states.top(); now_states.pop();
for (auto next_state : getAllNextState(now_state)) {
//if (scores.find(next_state.first) != scores.end()) continue;
//scores.insert(next_state.first);
next_states.push(next_state);
}
}
now_states = next_states;
if (now_states.empty()) break;
//cerr << "loopcnt: " << loopcnt << endl;
while (!next_states.empty()) {
auto s = next_states.top(); next_states.pop();
//cerr << s.second->turn << ": " << s.second->prod_sum() << " " << s.first << endl;
if (s.second->prod_sum() > max_prod) {
best_states.push(s.second);
if (best_states.size() >= 10) best_states.pop();
max_prod = s.second->prod_sum();
//cerr << s.second->turn << ": " << max_prod << endl;
}
}
auto top = now_states.top().second;
//cerr << top->turn << ": " << top->prod_sum() << endl;
loopcnt++;
}
//cerr << best_states.size() << endl;
StatePtr best_state = solve(init_state);
ll best_cookies = best_state->cookies;
while (!best_states.empty()) {
auto state = best_states.top(); best_states.pop();
ll max_turn = state->turn;
set<int> turns_prods;
for (int i = 0; i < state->turn; i++) {
if (state->hist_act[i] != CLICK) {
turns_prods.insert(i);
}
}
// 0 ターンまで巻き戻し
state->rewind(0);
for (int i = 0; i < max_turn; i++) {
state->action(EAct(state->hist_act[i]), EBld(state->hist_bld[i]));
// 5000 ターン以降のキーフレーム
if (state->turn >= 5000 && turns_prods.find(state->turn) != turns_prods.end()) {
// 全部クリック
for (int i = 40; i >= 0; i--) {
StatePtr s(new State(*state));
for (int t = s->turn; t < N - i; t++)
s->action(CLICK, NONE);
//cerr << "before sell: " << s->cookies << ", ";
//for (int t = s->turn; t < N; t++) s->sell_highest();
if (!s->sell_blds(i)) cerr << "error!" << endl;
// if (!s->sell_highest()) cerr << "error!" << endl;
//cerr << "after sell: " << s->cookies << endl;
//cerr << state->turn << ": " << s->cookies << endl;
if (best_cookies < s->cookies) {
best_cookies = s->cookies;
//cerr << best_cookies << endl;
best_state = s;
}
}
}
}
}
return best_state;
}
string testcase(unsigned seed) {
SXor128 r(seed);
REP(i, 100) r.nextUInt();
int range_min = 0, range_max = 199;
string S(N, 'N');
while (range_min < N) {
int idx = r.nextUInt(range_min, range_max);
if (idx >= N) break;
int kind = r.nextUInt(3);
if (kind == 0) S[idx] = 'B';
else if (kind == 1) S[idx] = 'F';
else S[idx] = 'S';
range_min = idx + 100;
range_max = idx + 200;
}
return S;
}
//#ifdef _MSC_VER
//typedef struct SMouseParams {
// int event, x, y, flags;
// SMouseParams() {}
// SMouseParams(int event, int x, int y, int flags) : event(event), x(x), y(y), flags(flags) {}
//}*SMouseParamsPtr;
//
//void mouse_callback(int event, int x, int y, int flags, void* params) {
// SMouseParamsPtr mp = static_cast<SMouseParamsPtr>(params);
// mp->event = event;
// mp->x = x;
// mp->y = y;
// mp->flags = flags;
//}
//
//struct Button {
// //int x1, y1, x2, y2;
// cv::Rect roi;
// EAct act;
// EBld bld;
// string text;
// cv::Mat_<cv::Vec3b> img;
//
// Button(int x1, int y1, int x2, int y2, EAct act, EBld bld, string text)
// : roi(x1, y1, x2 - x1, y2 - y1), act(act), bld(bld), text(text)
// {
// img = cv::Mat_<cv::Vec3b>(y2 - y1, x2 - x1, cv::Vec3b(255, 255, 255));
// cv::rectangle(img, cv::Rect(0, 0, x2 - x1, y2 - y1), cv::Scalar(0, 0, 0), 3, cv::LINE_AA);
// cv::putText(img, text, cv::Point(20, y2 - y1 - 32), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
// //ll diff = state->diff(act, bld);
// //cv::putText(img, to_string(abs(diff)), cv::Point(20, y2 - y1 - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
// }
//};
//
//void play(StatePtr state) {
//
// int W = 500;
// int H = 500;
// cv::Mat_<cv::Vec3b> board(H, W, cv::Vec3b(255, 255, 255));
//
// vector<Button> buttons;
// buttons.emplace_back(0, 0, 250, 250, CLICK, NONE, "cookie");
// buttons.emplace_back(0, 250, 250, 500, ENHCLICK, NONE, "enhance click");
// for (int i = 0; i < 5; i++) {
// buttons.emplace_back(250, 100 * i, 500, 100 * i + 50, BUY, EBld(i), "buy " + dict_blds_inv.at(EBld(i)));
// buttons.emplace_back(250, 100 * i + 50, 500, 100 * i + 100, REINFORCE, EBld(i), "reinforce " + dict_blds_inv.at(EBld(i)));
// }
//
// for (int i = 0; i < buttons.size(); i++) {
// cv::Mat img_roi = board(buttons[i].roi);
// //dump(buttons[i].roi, buttons[i].img.size(), board.size());
// buttons[i].img.copyTo(img_roi);
// }
//
// cv::String winname = "window";
// cv::namedWindow(winname);
// cv::imshow(winname, board);
// cv::waitKey(15);
//
// SMouseParamsPtr mp(new SMouseParams(0, 0, 0, 0));
// cv::setMouseCallback(winname, mouse_callback, mp);
//
// state->autoplay(ENHCLICK, NONE);
// state->autoplay(ENHCLICK, NONE);
// REP(i, 5) state->autoplay(BUY, HAND);
// state->autoplay(REINFORCE, HAND);
// REP(i, 2) state->autoplay(BUY, HAND);
// state->autoplay(ENHCLICK, NONE);
//
//
// int key;
// do {
// cv::Mat_<cv::Vec3b> cur_board = board.clone();
//
// cv::Point p(mp->x, mp->y);
//
// EAct act_selected;
// EBld bld_selected;
// ll diff_selected;
// ll fever_const = (state->effects_state & FEVER) ? 7 : 1;
// bool sale = state->effects_state & SALE;
// ll total_cps = 0;
// for (int i = 0; i < buttons.size(); i++) {
// EAct act = buttons[i].act;
// EBld bld = buttons[i].bld;
// ll diff = state->diff(act, bld);
// cv::putText(cur_board(buttons[i].roi), to_string(abs(diff)), cv::Point(20, buttons[i].roi.height - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
// if (act == BUY) {
// ll sum_cps = state->blds_count[bld] * state->productivity[bld] * fever_const;
// total_cps += sum_cps;
// cv::putText(cur_board(buttons[i].roi), to_string(state->blds_count[bld]),
// cv::Point(200, buttons[i].roi.height - 32), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
// cv::putText(cur_board(buttons[i].roi), to_string(sum_cps),
// cv::Point(150, buttons[i].roi.height - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
// }
// if (buttons[i].roi.contains(p)) {
// act_selected = buttons[i].act;
// bld_selected = buttons[i].bld;
// diff_selected = diff;
// }
// }
//
// cv::putText(cur_board, "turn: " + to_string(state->turn), cv::Point(20, 20), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
// cv::putText(cur_board, "cps: " + to_string(total_cps), cv::Point(20, 40), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//
// cv::putText(cur_board(buttons[0].roi), to_string(state->total_cookies), cv::Point(20, 100), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//
// //cv::imshow(winname, cur_board);
// //key = cv::waitKey(15);
//
// if (/*key == 'a'*/ state->turn < 8000) {
// optimal(state);
// // 足りなかったら足りるまでクッキーを焼き続ける
// //if(!state->autoplay(act_selected, bld_selected)) return;
// }
// else if (/*key == 'c'*/ state->turn < 9950) {
// if (!state->autoplay(CLICK, NONE)) return;
// }
// else if (state->turn < 10000) {
// ll maxsell = -1;
// EBld maxbld = NONE;
// for (int i = 4; i >= 0; i--) {
// ll d = state->diff(SELL, EBld(i));
// if (maxsell < d) {
// maxsell = d;
// maxbld = EBld(i);
// }
// }
// if (maxsell != -1) {
// state->action(SELL, maxbld, maxsell);
// }
// }
// else {
// key = 27;
// }
//
// } while (key != 27);
//}
//#endif
#ifdef _MSC_VER
int _main() {
timer.measure();
cin.tie(0);
ios::sync_with_stdio(false);
int T = 32;
vector<ll> scores(T);
vector<unsigned> seeds(T);
REP(i, 100) rnd.nextUInt();
REP(i, T) seeds[i] = /*rnd.nextUInt()*/i;
//for (int i = 0; i < T; i++) {
concurrency::parallel_for(0, T, [&](int i) {
ofstream ofs("input_" + to_string(i) + ".txt");
unsigned seed = seeds[i];
shared_ptr<string> S(new string(testcase(seed)));
StatePtr state(new State);
state->S = S;
state = beam_search(state);
//ll best_score = 0;
//StatePtr best_state;
//StatePtr s = solve(state);
//if (s->cookies > best_score) {
// best_score = s->cookies;
// best_state = s;
//}
//s = beam_search(state);
//if (s->cookies > best_score) {
// best_score = s->cookies;
// best_state = s;
//}
ofs << N << endl << *S << endl;
for (int i = 0; i < state->turn; i++) {
EAct act = EAct(state->hist_act[i]);
EBld bld = EBld(state->hist_bld[i]);
ofs << dict_acts_es.at(act);
if (act != CLICK && act != ENHCLICK) ofs << " " << dict_blds_es.at(bld);
ofs << endl;
}
cerr << seed << " ";
scores[i] = state->cookies;
});
//}
REP(i, T) cerr << "seed " << seeds[i] << ": " << scores[i] << endl;
cerr << endl;
cerr << "total: " << accumulate(all(scores), 0LL) / (T / 32) << endl;
return 0;
}
#endif
int main() {
timer.measure();
cin.tie(0);
ios::sync_with_stdio(false);
shared_ptr<string> S(new string);
int buf;
cin >> buf >> (*S);
//shared_ptr<string> S(new string(testcase(0)));
StatePtr state(new State);
state->S = S;
//state = solve(state);
state = beam_search(state);
string retval;
for (int i = 0; i < state->turn; i++) {
EAct act = EAct(state->hist_act[i]);
EBld bld = EBld(state->hist_bld[i]);
cout << dict_acts_es.at(act);
if (act != CLICK && act != ENHCLICK) cout << " " << dict_blds_es.at(bld);
cout << endl;
cin >> retval;
}
return 0;
}