結果
| 問題 |
No.5018 Let's Make a Best-seller Book
|
| コンテスト | |
| ユーザー |
 t33f
|
| 提出日時 | 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 |
ソースコード
#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;
}