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

提出ソース
結果

問題	No.5003 物理好きクリッカー
ユーザー	omi_UT
提出日時	2018-12-13 12:01:59
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	16,709 bytes
コンパイル時間	5,242 ms
コンパイル使用メモリ	245,832 KB
実行使用メモリ	33,936 KB
スコア	0
最終ジャッジ日時	2024-04-27 02:44:27
合計ジャッジ時間	27,823 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
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 ("tune=native")
#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){
        gameturn = rhs.gameturn;
        moves = rhs.moves;
        cookies = rhs.cookies;
        states = rhs.states;
        cookie = rhs.cookie;
        structs = rhs.structs;
        enhances = rhs.enhances;
        enhclick = rhs.enhclick;
        enhclickcost = rhs.enhclickcost;
    }
    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 ) && affordable(bo)){
                spend(bo);
            } else if (enhclickcost < (1LL << enhclick) * (9900 - gameturn)){
                enhc();
            } else{
                click();
            }
        }

        int structno = accumulate(structs.begin(), structs.end(), 0);
        FOR(i,9900,10000-structno) click();
        FOR(i,10000-structno,10000){
            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] ]+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){
        double selpr = (prices[i][ structs[i] ]+3)/4;
        return selpr - (base_cps[i] << enhances[i]) * (10000 - 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 *= (10000 - gameturn) / effectrui[gameturn];
        d *= coef();
        return d < (10000 - gameturn);
    }

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

        double ratio = -1;
        REP(i,5){
            double delta = (double)( base_cps[i] << enhances[i] ) / strcosts(i);
            if (delta > ratio){
                ratio = delta;
                ret = i;
            }
        }
        REP(i,5){
            double delta = (double)( base_cps[i] << enhances[i] ) * 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 = 10000;
        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 {
                REP(j,lasc){
                    printf("click\n");
                    fflush(stdout);
                    if (sub) scanf("%s",s);
                    maxi--;
                }
                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,10000){
            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 < 10000){
        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,10000){
        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,10000){
        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) * (10000 - g.gameturn) * 0.99){
            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,10000-structno) g.click();
    FOR(i,10000-structno,10000){
        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;

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

            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 -  pow(tim / limittime,temppow ) );
            //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;
        cerr << " " << ctr << " " << g.cookie << "\r";

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

    return g;
}

Game beam(){
    double st = gettime();
    vector<pair<int,char>> veff;
    REP(i,10000){
        char c = effects[i];
        if (c != 'N') veff.eb(i,c);
    }
    
    
    priority_queue<Game> Bstate;
    Bstate.push(Game());
    int wid = 1000;
    
    int prevturn = 0;
    REP(t,veff.size()*2){
        int nowturn = veff[t/2].first + (t&1);
        int deltaturn = nowturn - prevturn -1;

        priority_queue<Game> Bnewstate;
        Game prevstate;
        REP(i,wid){
            if (Bstate.empty()) break;
            auto nowstate = Bstate.top();
            Bstate.pop();
            if ((t/2) && nowstate.less_state(prevstate)){
                i--;
                continue;
            } else {
                prevstate = nowstate;
            }
            REP(mov, 10){
                if ( nowstate.affordable(mov) ){
                    auto nextstate = nowstate;
                    nextstate.spend(mov);
                    REP(j,deltaturn) nextstate.click();
                    
                    if (! Bnewstate.empty()){
                        auto nexttop = Bnewstate.top();
                        if (nextstate.less_state(nexttop)) continue;
                    }
                    Bnewstate.push(nextstate);
                }
            }
            if (nowstate.enhclickcost <= nowstate.cookie){
                auto nextstate = nowstate;
                nextstate.enhc();
                REP(j,deltaturn) nextstate.click();
                if ( Bnewstate.empty() || !nextstate.less_state(Bnewstate.top())){
                    Bnewstate.push(nextstate);
                }
            }
            REP(j,deltaturn + 1) nowstate.click();
            if ( Bnewstate.empty() || !nowstate.less_state(Bnewstate.top())){
                Bnewstate.push(nowstate);
            } 
        }

        Bstate = Bnewstate;
        prevturn = nowturn;
    }
    cerr << elapsed(st) << " " << Bstate.top().cookie << endl;
    return Bstate.top();
}
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 << 10000 << endl;
    prng = Xorshift128(rnd);
    randeffect();
    cout << effects << endl;

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

int main(int argc, char *argv[]){
    //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 = 45.98; //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

結果

テストケース

ソースコード
