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

提出ソース
結果

問題	No.5003 物理好きクリッカー
ユーザー	omi_UT
提出日時	2018-12-13 15:31:28
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	14,578 bytes
コンパイル時間	4,437 ms
実行使用メモリ	42,564 KB
スコア	0
最終ジャッジ日時	2021-08-26 00:55:52
合計ジャッジ時間	27,106 ms
ジャッジサーバーID （参考情報）	judge10 / judge14
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	--	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
//----------------------------おまじない
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx")
//----------------------------
#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define REPN(i,n) for (int i=(n);i>0;i--)
#define I(n) scanf("%d", &(n))
#define LL(n) scanf("%lld", &(n))
#define pb(n) push_back((n))
#define mp(i,j) make_pair((i),(j))
#define eb(i,j) emplace_back((i),(j))
#include <bits/stdc++.h>
using namespace std;
//------------------------------typedef集
typedef vector<int> vi;
typedef vector<char> vc;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;
typedef vector<vvi> vvvi;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<ull> vull;
const int mod = 1000000009;

inline unsigned long long rdtsc()
{
#ifdef __amd64
  unsigned long long a, d;
  __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
  return (d << 32) | a;
#else
  unsigned long long x;
  __asm__ volatile ("rdtsc" : "=A" (x));
  return x;
#endif
}
inline double gettime(){return rdtsc()/2593344000.0;}
inline double elapsed(double st){return gettime()-st;}

class Xorshift128 {
private:
  static constexpr unsigned MASK = 0x7FFFFFFF;
  unsigned x = 123456789, y = 987654321, z = 1000000007, w;
public:
  unsigned rnd(){
    unsigned t = x ^ (x << 11);
    x = y; y = z; z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return w & MASK;
  }
  Xorshift128(const unsigned seed) : w(seed) {}
};
Xorshift128 prng(21);

ll powll(ll base,ll power){
    ll ans = 1;
    while (power){
        if (power&1) ans = (base*ans);
        base = (base*base);
        power >>= 1;
    }
    return ans;
}

const string building[5] = {"hand", "lily", "factory", "casino", "grimoire"};
const ll base_cps[5] = {1,10,120,2000,25000};
const ll base_cost[5] = {150,2000,30000,600000,10000000};
string effects;
vector<double> effectlist(10101);
vector<double> effectrui(10101);

vector<vll> prices(5),enhprices(5);

double dismiss = 0.0;
double coef_base = 0.6;
double coef_thres = 7000;
double startTemp = 5.0;
double temppow = 2.0;

struct Game{
public:
    int gameturn;
    vi moves;
    vll cookies;
    vull states;

    ll cookie;
    vll structs;
    vll enhances;
    ll enhclick;
    ll enhclickcost;

    Game() : gameturn(0), moves(), cookies(), states(), cookie(0), enhclick(0), enhclickcost(15){
        structs = vll(5);
        enhances = vll(5);

    }
    Game (const Game& rhs) = default;
    Game (const Game& rhs, const int ind, const int newmv) {
        structs = vll(5);
        enhances = vll(5);
        cookie = rhs.cookies[ind-1];
        unpack(rhs.states[ind-1]);
        gameturn = ind;
        enhclickcost = 15 * powll(10, enhclick);
        if (newmv < 10 && !affordable(newmv)){
            cookie = -1; return;
        } else if (newmv == 10 && (enhclickcost > cookie)){
            cookie = -1; return;
        }
        moves = vi( rhs.moves.begin(), rhs.moves.begin()+ind );
        states = vull( rhs.states.begin(), rhs.states.begin()+ind );
        cookies = vll( rhs.cookies.begin(), rhs.cookies.begin()+ind );

        if (newmv < 10){
            spend(newmv);
        } else if (newmv == 10){
            enhc();
        } else {
            click();
        }
        prng.rnd();
        FOR(i,ind+1,9900){
            
            int bo = bestops();
            if ( depr( bo )){
                while(! affordable(bo) ) {click(); i++;}
                spend(bo);
            } else if (enhclickcost < (1LL << enhclick) * (9900 - gameturn)){
                enhc();
            } else{
                click();
            }
        }

        int structno = accumulate(structs.begin(), structs.end(), 0);
        FOR(i,9900,9999-structno) click();
        FOR(i,9999-structno,9999){
            double sellab = -1145141919;
            int ind = -1;
            REP(j,5){
                if (sellab < sellability(j)){
                    sellab = sellability(j);
                    ind = j;
                }
            }
            if (sellab > 0){
                sell(ind);
            } else {
                click();
            }
        }


    }

    bool less_state( const Game& rhs){
        return structs == rhs.structs && enhances == rhs.enhances && cookie <= rhs.cookie && enhclick <= rhs.enhclick ;
    }

    ll enhcosts(int i){
        ll base = enhprices[i][enhances[i]];
        return base * (gameturn && effects[gameturn-1] == 'S' ? 0.9 : 1);
    }

    ll strcosts(int i){
        ll base = prices[i][structs[i]];
        return base * (gameturn && effects[gameturn-1] == 'S' ? 0.9 : 1);
    }

    ll cps() const {
        ll ret = 0;
        REP(i,5) ret += structs[i] * ( base_cps[i] << enhances[i] );
        return ret;
    }

    ull pack(){
        ull ret = 0;
        REP(i,5) ret |= (structs[i] << (i*8));
        REP(i,5) ret |= (enhances[i] << (i*4 + 40));
        return ret | (enhclick << 60);
    }
    void unpack(ull pc){
        REP(i,5) structs[i] = (pc >> (i*8)) & 0xFF;
        REP(i,5) enhances[i] = (pc >> (i*4 + 40)) & 0x0F;
        enhclick = (pc >> 60) & 0x0F;
    }
    ll turn(){
        ll ret = cps();
        ret *= effectlist[gameturn] == 7 ? 7 : 1;
        cookie += ret;
        cookie += effects[gameturn] == 'B' ? (cookie + 99) / 100 : 0;
        gameturn++;
        cookies.pb(cookie);
        states.pb(pack());

        
        return ret;
    }
    bool affordable(int i){
        return i < 5 ? strcosts(i) <= cookie : enhcosts(i-5) <= cookie;
    }
    ll click(){ // 11
        cookie += (1LL << enhclick) * (effectlist[gameturn] == 7 ? 7 : 1);
        moves.pb(11);
        return (1LL << enhclick) * (effectlist[gameturn] == 7 ? 7 : 1) + turn();
    }
    ll buystr(int i){ // 0-4
        if ( strcosts(i) <= cookie ){
            cookie -= strcosts(i);
            structs[i]++;
            moves.pb(i);
        } else {
            return click();
        }
        return turn();
    }
    ll enh(int i){ // 5-9
        if ( structs[i] && enhcosts(i) <= cookie ){
            cookie -= enhcosts(i);
            enhances[i]++;
            moves.pb(i+5);
        } else {
            return click();
        }
        return turn();
    }
    ll enhc(){ // 10
        if ( enhclickcost <= cookie ){
            cookie -= enhclickcost;
            enhclick++;
            enhclickcost *= 10;
            moves.pb(10);
        } else {
            return click();
        }
        return turn();
    }
    ll sell(int i) { //20-24
        if (structs[i]){
            cookie += (prices[i][ structs[i]-1 ]+3)/4;
            structs[i]--;
            moves.pb(i+20);
        } else {
            return click();
        }
        return turn();
    }
    ll spend(int i){
        return i < 5 ? buystr(i) : enh(i - 5);
    }

    double depturn(int i){
        if (i < 5){
            double d = strcosts(i);
            d /= (base_cps[i] << enhances[i]);
            return d;
        } else if (i < 10){
            double d = enhcosts(i-5);
            d /= ((base_cps[i-5] << enhances[i-5]) * structs[i-5]);
            return d;
        }
        return -1;
    }
    double sellability(int i){
        if (!structs[i]) return -1;
        double selpr = (prices[i][ structs[i]-1]+3)/4;
        return selpr - (base_cps[i] << enhances[i]) * (9999 - gameturn);
    }
    double coef(){
        return gameturn < coef_thres ? ((double)gameturn / coef_thres * (1 - coef_base)) + coef_base : 1;
    }

    bool depr(int i){
        double d = depturn(i);
        d *= (9999 - gameturn) / effectrui[gameturn];
        //d *= coef();
        return d < (9999 - gameturn);
    }

    bool operator< (const Game& rhs) const {
        return cookie + cps() * (9999-gameturn) < rhs.cookie + rhs.cps() * (9999-gameturn);
    }
    bool operator> (const Game& rhs) const {
        return cookie > rhs.cookie;
    }
    int bestops(){
        int ret = -1;

        double ratio = -1;
        REP(i,5){
            double strprod = ( base_cps[i] << enhances[i] );
            double delta = strprod / strcosts(i);
            if (delta > ratio){
                ratio = delta;
                ret = i;
            }

            delta = strprod * structs[i] / enhcosts(i);
            if (delta > ratio){
                ratio = delta;
                ret = i + 5;
            }
        }

        double r = ret < 5 ? strcosts(ret): enhcosts(ret-5) ;
        r = (r-cookie)/cps();

        // REP(i,10){
        //     if (depturn(i) < r){
        //         r = depturn(i); ret = i;
        //     }
        // }
        assert(ret >= 0);
        return ret;
    }

    void output(const bool sub=false){
        char s[114];
        int maxi = 9999;
        int lasc = 0;
        REPN(inv,9999){
            if (moves[inv] == 11){
                lasc++;
            } else {
                break;
            }
        }
        REP(i,maxi){
            auto mov = moves[i];
            if (mov < 5) {
                printf("buy %s\n", building[mov%5].c_str());
            } else if (mov < 10){
                printf("reinforce %s\n", building[mov%5].c_str());
            } else if (mov == 10){
                printf("enhclick\n");
            } else if (mov == 11){
                printf("click\n");
            } else {
                while(lasc){
                    printf("click\n");
                    fflush(stdout);
                    if (sub) scanf("%s",s);
                    maxi--;
                    lasc--;
                }
                printf("sell %s\n", building[mov%5].c_str());
            }
            fflush(stdout);
            if (sub) scanf("%s",s);
        }
    }
    void dump(){
        cerr << gameturn << " " << cps() << "  " << cookie << "  ";
        REP(i,5) cerr << structs[i] << " ";
        REP(i,5) cerr << enhances[i] << " ";
        cerr << enhclick << endl;
    }

    void simulate(){
        Game cp;
        REP(i,9999){
            auto mov = moves[i];
            if (mov < 10){
                cp.spend(mov);
            } else if (mov == 10){
                cp.enhc();
            } else if (mov == 11){
                cp.click();
            } else{
                cp.sell(mov%5);
            }
            cerr << cp.cookie << endl;
        }
       
    }
};

const string special = "BFS";

void randeffect(){
    int v = 0;
    int t = prng.rnd() % 200;
    REP(i,t) effects += 'N';
    effects += special[ prng.rnd()%3 ];
    v += t + 1;

    while( v < 9999){
        t = prng.rnd() % 101 + 99;
        REP(i,t) effects += 'N';
        effects += special[ prng.rnd()%3 ];
        v += t + 1;
    }

}

Game gameloop(){
    double st = gettime();
    REP(i,9999){
        char c = effects[i];
        if (c == 'B'){
            effectlist[i] = 1.5;
        } else if (c == 'F'){
            int ii = i + 21;
            i++;
            for (; i < ii; i++) effectlist[i] = 7;
        } else if (c == 'S'){
            effectlist[i] = 1;
        } else {
            effectlist[i] = 1;
        }
    }
    REPN(i,9999){
        effectrui[i-1] = effectrui[i] + effectlist[i-1];
    }

    Game g = Game();
    REP(i,9900){
        int bo = g.bestops();
        //bool buy = dismiss * UINT_MAX < prng.rnd();
        if ( g.depr( bo ) && g.affordable(bo)){
            g.spend(bo);
        } else if (g.enhclickcost < (1LL << g.enhclick) * (9999 - g.gameturn)){
            g.enhc();
        } else{
            g.click();
        }
        // if (i % 10 == 0 ) {
        //     cerr << bo << " " << g.depturn(bo) << endl;
        //     g.dump();
        // }
    }
    int structno = accumulate(g.structs.begin(), g.structs.end(), 0);
    FOR(i,9900,9999-structno) g.click();
    FOR(i,9999-structno,9999){
        double sellab = -1145141919;
        int ind = -1;
        REP(j,5){
            if (sellab < g.sellability(j)){
                sellab = g.sellability(j);
                ind = j;
            }
        }
        if (sellab > 0){
            g.sell(ind);
        } else {
            g.click();
        }
    }
    cerr << g.cookie << endl;

    const double limittime = 9.5;

    double tim = elapsed(st);
    int ctr = 0;
    const int oneloop = 100;

    Game bestg = g;
    while( tim < limittime ){
        REP(_,oneloop){
            int idx = prng.rnd() % 8000 + 100;
            //int change = g.moves[idx] == 11 ? prng.rnd() % 11 : 11;
            int change = prng.rnd() % 12;
            if (change == g.moves[idx]) continue;

            Game gi = Game(g, idx, change);
            if (gi.cookie < 0) continue;

            double dscore = (gi.cookie - g.cookie);
            dscore *= 1e-8;
            double temper = startTemp * (1.0 -  tim / limittime);
            double prob = exp( dscore/temper);

            bool exch = prob * (double)UINT_MAX > (double)(prng.rnd());
            if (exch) g = gi;
        }
        tim = elapsed(st);
        ctr+=oneloop;
        if (bestg.cookie < g.cookie ) bestg = g;
        cerr << " " << ctr << " " << g.cookie << "\r";

    }
    cerr << "                                     \r";
    cerr << ctr << " " << bestg.cookie << endl;

    return bestg;
}

long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}

void test(){
    ll v = 0;
    REP(i,32){
        prng = Xorshift128(i);
        effects = "";
        randeffect();
        v += gameloop().cookie;

        //break;
    }
    cout << v << endl;
}

void exec(){
    int v; cin >> v;
    cin >> effects;

    auto g = gameloop();
    g.output(true);
    //cerr << g.cookie << endl;
    //g.simulate();
}

void make_sample(int rnd=21){
    cout << 9999 << endl;
    prng = Xorshift128(rnd);
    randeffect();
    cout << effects << endl;

    REP(i,9999) cout << "ok" << endl; 
}

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    //dismiss = 0.0; //atof(argv[1]); // 0.0
    coef_base = 0.6; //atof(argv[2]); // 0.6
    coef_thres = 8280; //atof(argv[3]); //7000
    startTemp = 4; //atof(argv[4]); //5.0
    //temppow = 0.04686; //atof(argv[5]); //2.0

    //{'base': 0.6004643314155524, 'pow': 0.046862762704473385, 'temp': 45.93752027988493, 'thres': 8279.719154386894}
    REP(i,5){
        ll pr = base_cost[i];
        REP(j,100){
            prices[i].pb(pr);
            pr = llceil(pr*6 ,5);
        }
    }
    REP(i,5){
        ll pr = base_cost[i] * 10;
        REP(j,15){
            enhprices[i].pb(pr);
            pr *= 10;
        }
    }
    //test();
    exec();
    //make_sample();
}
yukicoder

結果

テストケース

ソースコード
