結果

問題 No.5003 物理好きクリッカー
ユーザー nebukuro09nebukuro09
提出日時 2018-12-01 09:15:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 325 ms / 10,000 ms
コード長 5,825 bytes
コンパイル時間 3,073 ms
実行使用メモリ 22,008 KB
スコア 27,376,328
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 07:33:51
合計ジャッジ時間 16,110 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 324 ms
21,684 KB
testcase_01 AC 323 ms
21,528 KB
testcase_02 AC 321 ms
21,564 KB
testcase_03 AC 323 ms
21,864 KB
testcase_04 AC 304 ms
21,180 KB
testcase_05 AC 306 ms
21,300 KB
testcase_06 AC 301 ms
21,516 KB
testcase_07 AC 295 ms
21,876 KB
testcase_08 AC 297 ms
21,876 KB
testcase_09 AC 295 ms
21,684 KB
testcase_10 AC 291 ms
21,360 KB
testcase_11 AC 325 ms
21,504 KB
testcase_12 AC 298 ms
21,360 KB
testcase_13 AC 296 ms
21,516 KB
testcase_14 AC 304 ms
21,888 KB
testcase_15 AC 293 ms
21,516 KB
testcase_16 AC 294 ms
21,888 KB
testcase_17 AC 323 ms
21,924 KB
testcase_18 AC 324 ms
21,360 KB
testcase_19 AC 325 ms
21,540 KB
testcase_20 AC 301 ms
21,348 KB
testcase_21 AC 300 ms
21,864 KB
testcase_22 AC 312 ms
21,516 KB
testcase_23 AC 301 ms
21,372 KB
testcase_24 AC 323 ms
21,864 KB
testcase_25 AC 300 ms
21,528 KB
testcase_26 AC 312 ms
21,540 KB
testcase_27 AC 303 ms
21,852 KB
testcase_28 AC 301 ms
21,528 KB
testcase_29 AC 303 ms
21,876 KB
testcase_30 AC 325 ms
21,348 KB
testcase_31 AC 319 ms
21,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;

const int N = 10000;
const int F = 5;
const int MAXB = 20;

const string action[5] = {"click", "buy", "sell", "reinforce", "enhclick"};
const string facility[F] = {"hand", "lily", "factory", "casino", "grimoire"};
const uint64_t productivity[F] = {1, 10, 120, 2000, 25000};

uint64_t buy_cost[F][MAXB];
uint64_t rein_cost[F][MAXB];
uint64_t click_cost[MAXB];


struct State {
    uint16_t turn;
    uint64_t cookies;
    uint16_t click_level;
    uint16_t facility_count[F];
    uint16_t facility_level[F];

    uint64_t eval() {
        uint64_t ret = 0;
        ret += cookies;
        ret += (N - turn) * (((uint64_t)(1)) << click_level);
        for (int i = 0; i < F; ++i) {
            ret += (N - turn) *
                productivity[i] *
                (((uint64_t)(1)) << facility_level[i]) *
                facility_count[i];
        }
        return ret + cookies;
    }

    void click() {
        turn += 1;
        cookies += ((uint64_t)(1)) << click_level;
    }

    void click_back() {
        cookies -= ((uint64_t)(1)) << click_level;
        turn -= 1;
    }

    bool buy(int f) {
        if (cookies < buy_cost[f][facility_count[f]]) return false;
        turn += 1;
        cookies -= buy_cost[f][facility_count[f]];
        facility_count[f] += 1;
        return true;
    }

    void buy_back(int f) {
        facility_count[f] -= 1;
        cookies += buy_cost[f][facility_count[f]];
        turn -= 1;
    }

    bool sell(int f) {
        if (facility_count[f] == 0) return false;
        turn += 1;
        cookies += ceil(buy_cost[f][facility_count[f]-1] / 4.0);
        facility_count[f] -= 1;
        return true;
    }

    void sell_back(int f) {
        facility_count[f] += 1;
        cookies -= ceil(buy_cost[f][facility_count[f]-1] / 4.0);
        turn -= 1;
    }

    bool reinforce(int f) {
        if (cookies < rein_cost[f][facility_level[f]]) return false;
        turn += 1;
        cookies -= rein_cost[f][facility_level[f]];
        facility_level[f] += 1;
        return true;
    }

    void reinforce_back(int f) {
        facility_level[f] -= 1;
        cookies += rein_cost[f][facility_level[f]];
        turn -= 1;
    }

    bool enhclick() {
        if (cookies < click_cost[click_level]) return false;
        turn += 1;
        cookies -= click_cost[click_level];
        click_level += 1;
        return true;
    }

    void enhclick_back() {
        click_level -= 1;
        cookies += click_cost[click_level];
        turn -= 1;
    }

    uint64_t eval_click() {
        click();
        uint64_t score = eval();
        click_back();
        return score;
    }

    uint64_t eval_buy(int f) {
        if (!buy(f)) return 0;
        uint64_t score = eval();
        buy_back(f);
        return score;
    }

    uint64_t eval_sell(int f) {
        if (!sell(f)) return 0;
        uint64_t score = eval();
        sell_back(f);
        return score;
    }

    uint64_t eval_reinforce(int f) {
        if (!reinforce(f)) return 0;
        uint64_t score = eval();
        reinforce_back(f);
        return score;
    }

    uint64_t eval_enhclick() {
        if (!enhclick()) return 0;
        uint64_t score = eval();
        enhclick_back();
        return score;
    }

    pair<int, int> best_next_action() {
        uint64_t best_score = 0;
        int x = -1;
        int y = 0;

        uint64_t s;

        s = eval_click();
        if (s > best_score) {
            best_score = s;
            x = 0;
        }

        REP(i, F) {
            s = eval_buy(i);
            if (s > best_score) {
                best_score = s;
                x = 1;
                y = i;
            }
        }

        REP(i, F) {
            s = eval_sell(i);
            if (s > best_score) {
                best_score = s;
                x = 2;
                y = i;
            }
        }

        REP(i, F) {
            s = eval_reinforce(i);
            if (s > best_score) {
                best_score = s;
                x = 3;
                y = i;
            }
        }

        s = eval_enhclick();
        if (s > best_score) {
            best_score = s;
            x = 4;
        }

        return make_pair(x, y);
    }
};


void init() {
    buy_cost[0][0] =  150;
    buy_cost[1][0] =  2000;
    buy_cost[2][0] =  30000;
    buy_cost[3][0] =  600000;
    buy_cost[4][0] =  10000000;
    rein_cost[0][0] = buy_cost[0][0] * 10;
    rein_cost[1][0] = buy_cost[1][0] * 10;
    rein_cost[2][0] = buy_cost[2][0] * 10;
    rein_cost[3][0] = buy_cost[3][0] * 10;
    rein_cost[4][0] = buy_cost[4][0] * 10;
    click_cost[0] = 15;

    REP(i, F) REP(j, MAXB-1) {
        buy_cost[i][j+1] = ceil(6.0 * buy_cost[i][j] / 5);
    }

    REP(i, F) REP(j, MAXB-1) {
        rein_cost[i][j+1] = 10 * rein_cost[i][j];
    }

    REP(j, MAXB-1) {
        click_cost[j+1] = click_cost[j] * 10;
    }
}

int main() {
    int hoge;
    string s;
    cin >> hoge >> s;

    init();

    State S;
    S.turn = 0;
    S.cookies = 0;
    S.click_level = 0;
    REP(i, F) S.facility_count[i] = 0;
    REP(i, F) S.facility_level[i] = 0;

    pair<int, int> p;
    int x, y;

    REP(_, N) {
        p = S.best_next_action();
        x = p.first;
        y = p.second;

        cout << action[x];
        if (x >= 1 && x <= 3) {
            cout << " " << facility[y];
        }
        cout << endl;

        if (x == 0) {
            S.click();
        } else if (x == 1) {
            S.buy(y);
        } else if (x == 2) {
            S.sell(y);
        } else if (x == 3) {
            S.reinforce(y);
        } else {
            S.enhclick();
        }

        cin >> s;
    }
}
0