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

提出ソース
結果

問題	No.5003 物理好きクリッカー
ユーザー	omi_UT
提出日時	2018-12-13 19:19:02
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE (最新) AC (最初)
実行時間	-
コード長	14,850 bytes
コンパイル時間	4,312 ms
コンパイル使用メモリ	225,024 KB
実行使用メモリ	25,964 KB
スコア	0
平均クエリ数	1.00
最終ジャッジ日時	2024-04-27 02:44:51
合計ジャッジ時間	11,695 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

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

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) = 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);

        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) & (i < 9900)) {click(); i++;}
                spend(bo);
            } else if (enhclickcost < (1LL << enhclick) * (10000 - gameturn)){
                enhc();
            } else{
                for(; i<9900; i++) click();
            }
        }

        FOR(i,9900,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(bool packing=true){
        static ll ret = 0;
        if (packing) ret = cps();
        cookie += ret * effectlist[gameturn];
        cookie += effects[gameturn] == 'B' ? (cookie + 99) / 100 : 0;
        
        cookies.pb(cookie);
        states.pb( packing ? pack() : states.back() );
        gameturn++;
        
        return ret;
    }
    bool affordable(int i){
        return i < 5 ? strcosts(i) <= cookie : enhcosts(i-5) <= cookie;
    }
    ll click(){ // 11
        cookie += (1LL << enhclick) * (effectlist[gameturn]);
        moves.pb(11);
        // return (1LL << enhclick) * (effectlist[gameturn]) + turn(!gameturn);
        return turn(!gameturn);
    }
    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]) * effectrui[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 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 = 10000;
        int lasc = 0;
        REPN(inv,10000){
            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,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;
    }

}

bool is_valid(const Game& g, const int idx, const int change){
    ull state = g.states[idx-1];
    ll cookie = g.cookies[idx-1];
    ll cost = 0;
    //cerr << state << " " << cookie << endl;
    if (change < 5){
        cost = prices[ change ][ state>>(8*change)& 0xFF ] ;
    } else if (change < 10){
        cost = enhprices[ change-5 ][ state>>(40 + 4*change)& 0xF ] ;
    } else if (change == 10){
        cost = 15 * powll(10, state>>60);
    }

    cost *= (effects[idx-1] == 'S' ? 0.9 : 1);
    return cookie >= cost;
}

ll annealthres = 7900;
Game gameloop(){
    double st = gettime();
    REP(i,10000){
        char c = effects[i];
        if (c == 'B'){
            effectlist[i] = 1;
        } 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)){
            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 = 1000;

    while( tim < limittime ){
        REP(_,oneloop){
            int idx = prng.rnd() % annealthres + 100;
            //int change = g.moves[idx] == 11 ? prng.rnd() % 11 : 11;
            int change = prng.rnd() % 12;
            if (change == g.moves[idx] || !(is_valid(g,idx, change))) 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;
        cerr << " " << ctr << " " << g.cookie << "\r";

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

    return g;
}

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

void test(int offset=0){
    ll v = 0;
    REP(i,32){
        prng = Xorshift128(i + offset);
        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[]){
    ios::sync_with_stdio(false);
    startTemp = 4; //atof(argv[4]); //5.0
    annealthres = 7900; // atoll(argv[2]); //7900

    //{'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(114514);
    exec();
    //make_sample();
}
yukicoder

結果

テストケース

ソースコード
