結果

問題 No.5018 Let's Make a Best-seller Book
ユーザー t33ft33f
提出日時 2023-10-01 15:54:48
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

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