結果

問題 No.5018 Let's Make a Best-seller Book
ユーザー t33ft33f
提出日時 2023-10-01 15:54:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 118 ms / 400 ms
コード長 6,056 bytes
コンパイル時間 1,008 ms
コンパイル使用メモリ 88,476 KB
実行使用メモリ 24,420 KB
スコア 34,249
平均クエリ数 52.00
最終ジャッジ日時 2023-10-01 15:55:08
合計ジャッジ時間 10,137 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
23,376 KB
testcase_01 AC 33 ms
24,420 KB
testcase_02 AC 34 ms
23,376 KB
testcase_03 AC 118 ms
23,652 KB
testcase_04 AC 33 ms
24,024 KB
testcase_05 AC 32 ms
23,532 KB
testcase_06 AC 33 ms
23,412 KB
testcase_07 AC 32 ms
23,832 KB
testcase_08 AC 32 ms
23,364 KB
testcase_09 AC 32 ms
24,348 KB
testcase_10 AC 34 ms
23,412 KB
testcase_11 AC 48 ms
23,244 KB
testcase_12 AC 33 ms
24,336 KB
testcase_13 AC 33 ms
24,360 KB
testcase_14 AC 32 ms
23,664 KB
testcase_15 AC 33 ms
24,036 KB
testcase_16 AC 35 ms
23,388 KB
testcase_17 AC 32 ms
24,024 KB
testcase_18 AC 33 ms
23,376 KB
testcase_19 AC 32 ms
23,832 KB
testcase_20 AC 33 ms
24,348 KB
testcase_21 AC 33 ms
24,276 KB
testcase_22 AC 32 ms
24,384 KB
testcase_23 AC 32 ms
23,532 KB
testcase_24 AC 32 ms
23,664 KB
testcase_25 AC 33 ms
23,652 KB
testcase_26 AC 33 ms
23,364 KB
testcase_27 AC 32 ms
24,228 KB
testcase_28 AC 32 ms
23,532 KB
testcase_29 AC 32 ms
23,412 KB
testcase_30 AC 32 ms
24,060 KB
testcase_31 AC 33 ms
23,664 KB
testcase_32 AC 32 ms
23,664 KB
testcase_33 AC 32 ms
23,532 KB
testcase_34 AC 32 ms
23,376 KB
testcase_35 AC 33 ms
23,388 KB
testcase_36 AC 33 ms
24,036 KB
testcase_37 AC 33 ms
23,388 KB
testcase_38 AC 33 ms
24,048 KB
testcase_39 AC 33 ms
23,520 KB
testcase_40 AC 34 ms
23,844 KB
testcase_41 AC 32 ms
24,012 KB
testcase_42 AC 32 ms
23,532 KB
testcase_43 AC 33 ms
24,036 KB
testcase_44 AC 33 ms
23,832 KB
testcase_45 AC 51 ms
23,832 KB
testcase_46 AC 50 ms
24,048 KB
testcase_47 AC 32 ms
24,324 KB
testcase_48 AC 35 ms
23,412 KB
testcase_49 AC 33 ms
24,048 KB
testcase_50 AC 33 ms
23,664 KB
testcase_51 AC 33 ms
23,820 KB
testcase_52 AC 33 ms
23,376 KB
testcase_53 AC 33 ms
23,832 KB
testcase_54 AC 33 ms
23,664 KB
testcase_55 AC 33 ms
24,396 KB
testcase_56 AC 33 ms
24,024 KB
testcase_57 AC 32 ms
23,832 KB
testcase_58 AC 33 ms
23,424 KB
testcase_59 AC 32 ms
24,060 KB
testcase_60 AC 62 ms
23,544 KB
testcase_61 AC 34 ms
23,676 KB
testcase_62 AC 33 ms
24,384 KB
testcase_63 AC 32 ms
23,424 KB
testcase_64 AC 33 ms
23,640 KB
testcase_65 AC 32 ms
24,024 KB
testcase_66 AC 32 ms
23,532 KB
testcase_67 AC 32 ms
23,640 KB
testcase_68 AC 32 ms
23,388 KB
testcase_69 AC 32 ms
23,364 KB
testcase_70 AC 32 ms
23,640 KB
testcase_71 AC 32 ms
24,024 KB
testcase_72 AC 32 ms
24,276 KB
testcase_73 AC 32 ms
23,364 KB
testcase_74 AC 32 ms
23,388 KB
testcase_75 AC 32 ms
23,844 KB
testcase_76 AC 33 ms
23,424 KB
testcase_77 AC 32 ms
23,832 KB
testcase_78 AC 34 ms
23,424 KB
testcase_79 AC 33 ms
23,412 KB
testcase_80 AC 33 ms
23,388 KB
testcase_81 AC 32 ms
23,652 KB
testcase_82 AC 33 ms
23,844 KB
testcase_83 AC 33 ms
24,012 KB
testcase_84 AC 42 ms
24,036 KB
testcase_85 AC 32 ms
23,520 KB
testcase_86 AC 32 ms
24,396 KB
testcase_87 AC 33 ms
24,024 KB
testcase_88 AC 33 ms
23,412 KB
testcase_89 AC 32 ms
23,544 KB
testcase_90 AC 33 ms
23,376 KB
testcase_91 AC 32 ms
23,412 KB
testcase_92 AC 33 ms
23,376 KB
testcase_93 AC 33 ms
24,360 KB
testcase_94 AC 32 ms
23,640 KB
testcase_95 AC 32 ms
24,036 KB
testcase_96 AC 32 ms
24,036 KB
testcase_97 AC 32 ms
23,820 KB
testcase_98 AC 32 ms
24,048 KB
testcase_99 AC 33 ms
23,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <numeric>
#include <cmath>
#include <array>
#include <cassert>
#include <iostream>
using namespace std;

constexpr int N = 10, T = 52;

#ifndef ONLINE_JUDGE
array<double, N> D;
array<array<double, N>, T> Z;
#endif

void read_initial_input() {
    { int t; cin >> t; assert(t == T); }
    { int n; cin >> n; assert(n == N); }
    { int m; cin >> m; assert(m = 2'000'000); }
#ifndef ONLINE_JUDGE
    for (int i = 0; i < N; ++i) cin >> D[i];
    for (int t = 0; t < T; ++t) for (int i = 0; i < N; ++i) cin >> Z[t][i];
#endif
}

struct Data {
    int money;
    array<int, N> s, p, r;
};

#ifdef ONLINE_JUDGE

void add_inv(const array<int, N> &L) {
    cout << "1";
    for (int l : L) cout << " " << l;
    cout << endl;
}

void do_ad(int x) {
    assert(1 <= x && x <= 5);
    cout << "2 " << x << endl;
}

Data get_next_data() {
    int m; cin >> m;
    array<int, N> s, p, r;
    for (int i = 0; i < N; ++i) cin >> s[i];
    for (int i = 0; i < N; ++i) cin >> p[i];
    for (int i = 0; i < N; ++i) cin >> r[i];
    return {m, s, p, r};
}

#else

int cur_money = 2'000'000;
int turn_ = 0;
array<int, N> P_, R_;

void add_inv(const array<int, N> &L) {
    for (int i = 0; i < N; ++i) R_[i] += L[i], cur_money -= 500 * L[i];
    assert(cur_money >= 0);
}

void do_ad(int x) {
    assert(1 <= x && x <= 5);
    cur_money -= 500'000 << (x - 1);
    assert(cur_money >= 0);
    for (int i = 0; i < N; ++i) P_[i] = min(60, P_[i] + x);
}

Data get_next_data() {
    array<int, N> s{};
    for (int i = 0; i < N; ++i) {
        if (R_[i] > 0) {
            s[i] = min(R_[i], int(floor(sqrt(R_[i]) * pow(1.05, P_[i]) * D[i] * Z[turn_][i])));
            if (s[i] >= 0.3 * R_[i] && P_[i] < 60) P_[i] += 1;
            else if (s[i] < 0.1 * R_[i] && P_[i] > -60) P_[i] -= 1;
            R_[i] -= s[i];
            cur_money += 1000 * s[i];
        }
    }

    ++turn_;
    return {cur_money, s, P_, R_};
}

#endif

array<double, N> Dlb = [] { array<double, N> d; d.fill(0.5); return d; }();

array<array<int, N>, T> S, P, R;

double prob(int s, int p, int r, double d) {
    const double lb = clamp(double(s) / (sqrt(r) * pow(1.05, p) * (d + 0.1)), 0.75, 1.25);
    const double ub = r == s ? 1.25 : clamp(double(s + 1) / (sqrt(r) * pow(1.05, p) * d), 0.75, 1.25);
    return 2 * (ub - lb);
}

void update_Dlb(int cur_turn) {
    for (int i = 0; i < N; ++i) {
        array<double, 11> probs;
        probs.fill(1.0);
        for (int j = 0; j < 11; ++j) {
            const double d = 0.5 + 1.0 * j / 10;
            double tmp = 1.0;
            for (int t = 1; t <= cur_turn; ++t) {
                if (R[t][i] > 0) tmp *= prob(S[t][i], P[t - 1][i], R[t][i] + S[t][i], d);
            }
            probs[j] = tmp;
        }
        {
            double sum = accumulate(probs.begin(), probs.end(), 0.0);
            if (sum > 0)
                for (double &p : probs) p /= sum;
        }
        for (int j = 10; j > 0; --j) probs[j - 1] += probs[j];
        // for (double p : probs) cerr << p << ' ';
        // cerr << endl;
        int j = 0;
        while (j + 1 < 11 && probs[j + 1] > 0.99) ++j;
        Dlb[i] = 0.5 + 1.0 * j / 10;
    }
    for (double p : Dlb) cerr << p << ' ';
    cerr << endl;
}

array<int, N> calc_L(int money, const array<int, N> &p, const array<int, N> &r, int turn) {
    array<int, N> L;
    for (int i = 0; i < N; ++i) {
        int lb = 1;
        auto check1 = [&] (int d) {
            return sqrt(r[i] + d) * pow(1.05, p[i]) * Dlb[i] * 0.75 >= 0.1 * (r[i] + d);
        };
        // auto check3 = [&] (int d) {
        //     return sqrt(r[i] + d) * pow(1.05, p[i]) * Dlb[i] * 0.75 >= 0.3 * (r[i] + d);
        // };
        // while (lb < 1000 && !check3(lb)) ++lb;
        // if (lb < 1000) {
        //     cerr << "A\n";
        //     int ub = lb + 1;
        //     while (check3(ub) && ub < 1'000'000) ub *= 2;
        //     if (turn > 50) cerr << lb << ' ' << ub << endl;
        //     while (ub - lb > 1) {
        //         const int m = (ub + lb) / 2;
        //         if (check3(m)) lb = m;
        //         else ub = m;
        //     }
        //     L[i] = lb;
        // } else {
        //     cerr << "B\n";
        //     lb = 0;
            while (!check1(lb) && lb < 100) ++lb;
            if (lb == 100) continue;
            int ub = lb + 1;
            while (check1(ub) && ub < 1'000'000) ub *= 2;
            if (turn > 50) cerr << i << ' ' << lb << ' ' << ub << endl;
            while (ub - lb > 1) {
                const int m = (ub + lb) / 2;
                if (check1(m)) lb = m;
                else ub = m;
            }
            L[i] = lb;
        // }
    }
    int cost = 500 * reduce(L.begin(), L.end(), 0);
    while (money < cost) {
        array<int, N> idx;
        iota(idx.begin(), idx.end(), 0);
        // sort(idx.begin(), idx.end(), [&p](int l, int r) { return p[l] < p[r]; });
        for (int i : idx) {
            if (L[i] > 0) --L[i], cost -= 500;
            if (cost <= money) break;
        }
    }
    return L;
}

int main() {
    read_initial_input();
    int money = 2'000'000;
    int score = 0;
    for (int t = 0; t < T; ++t) {
        if (t == 0) {
            array<int, N> L;
            L.fill(9);
            add_inv(L);
        } else if (t < 40 && money > 500'000) {
            for (int x = 5; x > 0; --x)
                if (500'000 << (x - 1) < money) {
                    do_ad(x);
                    break;
                }
        } else {
            array<int, N> L = t > 0 ? calc_L(money, P[t - 1], R[t - 1], t) : calc_L(money, {}, {}, t);
            add_inv(L);
        }

        const auto [m, s, p, r] = get_next_data();
        // update_Dlb(t);
        money = m;
        score += reduce(s.begin(), s.end(), 0);
        S[t] = s;
        P[t] = p;
        R[t] = r;
        cerr << m << ' ' << reduce(s.begin(), s.end(), 0) << endl;
        for (int i = 0; i < N; ++i) cerr << s[i] << ' ' << p[i] << ' ' << r[i] << endl;
        cerr << endl;
    }
    cerr << "score = " << score << endl;
}
0