結果
| 問題 |
No.5018 Let's Make a Best-seller Book
|
| コンテスト | |
| ユーザー |
 Kiri8128
|
| 提出日時 | 2023-10-02 20:28:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 168 ms / 400 ms |
| コード長 | 15,283 bytes |
| コンパイル時間 | 283 ms |
| コンパイル使用メモリ | 87,176 KB |
| 実行使用メモリ | 94,540 KB |
| スコア | 167,914 |
| 平均クエリ数 | 52.00 |
| 最終ジャッジ日時 | 2023-10-02 20:28:46 |
| 合計ジャッジ時間 | 20,235 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
from random import gauss, random, randrange
try:
LOCAL
except NameError:
LOCAL = 0
if LOCAL:
import optuna
DEBUG = 1
print("LOOP ?")
LOOP = int(input())
OP = 1 if LOOP == 0 else 0
else:
DEBUG = 0
LOOP = 1
OP = 0
def estimate(i, p):
l, r = int(MI[i] * 100 + 0.999), int(MA[i] * 100 + 0.001) + 1
if MA[i] - MI[i] < 0.01 or l >= r - 1:
return MI[i] + (MA[i] - MI[i]) * p
a = estimation_matrix[i]
su = 0
for j in range(l, r):
su += a[j-50]
if su > p:
return j / 100
return MI[i] + (MA[i] - MI[i]) * p
def expected(i):
l, r = int(MI[i] * 100 + 0.999), int(MA[i] * 100 + 0.001) + 1
if MA[i] - MI[i] < 0.01 or l >= r - 1:
return MI[i] + (MA[i] - MI[i]) * 0.5
a = estimation_matrix[i]
su = 0
ret = 0
for j in range(l, r):
su += a[j-50]
ret += a[j-50] * (j / 100)
if 0.99 < su < 1.01:
return max(MA[i], min(MI[i], ret))
return MI[i] + (MA[i] - MI[i]) * 0.5
def receive():
global P
global R
global money
global MI, MA
global sell_count, estimation_matrix, expected
if DEBUG:
sell_count = [min(R[i], int(R[i] ** 0.5 * 1.05 ** P[i] * D[i] * (0.75 + random() * 0.5))) for i in range(N)]
money += 1000 * sum(sell_count)
else:
money = int(input())
sell_count = [int(a) for a in input().split()]
for i in range(N):
if R[i]:
cn = R[i] ** 0.5 * 1.05 ** P[i]
ma = (sell_count[i] + 1) / (cn * 0.75)
mi = sell_count[i] / (cn * 1.25)
MI[i] = max(mi, MI[i])
if sell_count[i] < R[i]:
MA[i] = min(ma, MA[i])
l, r = int(MI[i] * 100 + 0.999), int(MA[i] * 100 + 0.001) + 1
sum_prob = 0
ai = estimation_matrix[i]
for j in range(l, r):
low = max(0.75, sell_count[i] / (cn * (j / 100)))
if sell_count[i] < R[i]:
high = min(1.25, (sell_count[i] + 1) / (cn * (j / 100)))
else:
high = 1.25
prob = max(0, high - low)
ai[j-50] *= prob
sum_prob += ai[j-50]
if sum_prob:
ex = 0
for j in range(l, r):
ai[j-50] /= sum_prob
ex = ai[j-50] * j
expected[i] = max(MA[i], min(MI[i], ex / 100))
else:
expected[i] = (MA[i] + MI[i]) / 2
if 0 and DEBUG:
assert l >= r - 2, (t, i, l, r)
for i in range(N):
if R[i]:
if sell_count[i] * 10 >= 3 * R[i]:
P[i] = min(P[i] + 1, 60)
elif sell_count[i] * 10 < R[i]:
P[i] = max(P[i] - 1, -60)
if DEBUG:
for i in range(N):
R[i] -= sell_count[i]
else:
for i, a in enumerate(input().split()):
P[i] = int(a)
for i, a in enumerate(input().split()):
R[i] = int(a)
for i in range(N):
total_sell_count[i] += sell_count[i]
def adj(n):
if n < 4:
return 3
if n % 10 < 3:
return n // 10 * 10
if n % 10 < 6:
return n // 10 * 10 + 3
return n // 10 * 10 + 6
def Order(t0, pa1, pa2, f1, f2, f3, f4, f5, f6, f7, g1, g2):
global P
global R
global money
global best_allocation_flg, expected
def calc_best_allocation():
best_allocation = [(expected[i] * 1.05 ** P[i]) ** 2 for i in range(N)]
su = sum(best_allocation)
for i in range(N):
best_allocation[i] *= 10 ** 8
best_allocation[i] = adj(int(best_allocation[i]))
return best_allocation
target = 10
buy_count = [0] * N
# exp = [expected(i) for i in range(N)]
best_allocation = None
best_allocation_flg = [0] * N
for i in range(N):
# a30 = (10 / 3 * 1.05 ** P[i] * (MA[i] * 0.0 + MI[i] * 1.0)) ** 2
# b30 = (10 / 3 * 1.05 ** P[i] * (MA[i] * 0.5 + MI[i] * 0.5)) ** 2
# c30 = (10 / 3 * 1.05 ** P[i] * (MA[i] * 0.1 + MI[i] * 0.9)) ** 2
if t == 0:
target = t0 * 10 // 3
elif t < 5:
target = adj(int((10 / 3 * 1.05 ** P[i] * estimate(i, pa1) * f1) ** 2))
elif t < 12:
target = adj(int((10 / 3 * 1.05 ** P[i] * estimate(i, pa2) * f2) ** 2))
elif t < 20:
target = adj(int((10 / 3 * 1.05 ** P[i] * expected[i] * f3) ** 2))
elif t < (20 * 0.75 + g2 * 0.25) and P[i] < g1:
target = adj(int((10 / 3 * 1.05 ** P[i] * expected[i] * f4) ** 2))
elif t < (20 * 0.5 + g2 * 0.5) and P[i] < g1:
target = adj(int((10 / 3 * 1.05 ** P[i] * expected[i] * f5) ** 2))
elif t < (20 * 0.25 + g2 * 0.75) and P[i] < g1:
target = adj(int((10 / 3 * 1.05 ** P[i] * expected[i] * f6) ** 2))
elif t < g2 and P[i] < g1:
target = adj(int((10 / 3 * 1.05 ** P[i] * expected[i] * f7) ** 2))
elif t < 100:
if best_allocation is None:
best_allocation = calc_best_allocation()
target = best_allocation[i]
best_allocation_flg[i] = 1
else:
assert 0
buy_count[i] = max(0, target - R[i])
if best_allocation:
su_best = sum([a for a, f in zip(best_allocation, best_allocation_flg) if f])
su_R = sum([r for r, f in zip(R, best_allocation_flg) if f])
used = sum([max(t - r, 0) for t, r, f in zip(buy_count, R, best_allocation_flg) if not f])
avail = max(0, money // 500 - used + su_R)
for i in range(N):
if best_allocation_flg[i]:
buy_count[i] = adj(int(best_allocation[i] / su_best * avail - R[i]))
# buy_count[i] = adj(int(best_allocation[i] / su_best * avail))
while 1:
r = sum(buy_count) * 500 / money
if r <= 1:
break
for i in range(N):
buy_count[i] = adj(int(buy_count[i] / r))
money -= sum(buy_count) * 500
if money < 0:
while 1:
pass
assert money >= 0
for i in range(N):
R[i] += buy_count[i]
if not DEBUG:
print(1, *buy_count)
return buy_count
def Advertise(x):
global money
money -= 500000 << x - 1
if money < 0:
while 1:
pass
assert money >= 0
for i in range(N):
P[i] = min(P[i] + x, 60)
if not DEBUG:
print(2, x)
def round3(x):
return round(x * 1000) / 1000
def main_loop(t0, adv_l2, adv_r2, adv_m2_0, adv_m2_25, adv_m2_50, adv_l3, adv_r3, adv_m3, pa1, pa2, f1, f2, f3, f4, f5, f6, f7, g1, g2):
global T, N, money
global MI, MA, P, R, t, D, total_sell_count, LOOP
global total_total
ret = 0
main_loop_loop = 2000
for _ in range(main_loop_loop):
ret += main(t0, adv_l2, adv_r2, adv_m2_0, adv_m2_25, adv_m2_50, adv_l3, adv_r3, adv_m3, pa1, pa2, f1, f2, f3, f4, f5, f6, f7, g1, g2)
return ret / main_loop_loop
def main(t0, adv_l2, adv_r2, adv_m2_0, adv_m2_25, adv_m2_50, adv_l3, adv_r3, adv_m3, pa1, pa2, f1, f2, f3, f4, f5, f6, f7, g1, g2):
global T, N, money
global MI, MA, P, R, t, D, total_sell_count, LOOP
global total_total
global sell_count, best_allocation_flg
if DEBUG:
T, N, money = 52, 10, 2 * 10 ** 6
D = [random() + 0.5 for _ in range(N)]
else:
T, N, money = map(int, input().split())
D = [random() + 0.5 for _ in range(N)]
total_sell_count = [0] * N
sell_count = [0] * N
best_allocation_flg = [0] * N
MA = [1.5] * N
MI = [0.5] * N
P = [0] * N
R = [0] * N
max_buy_count = 30
for t in range(T):
adv_m2 = adv_m2_0 * (1 - t / 25) + adv_m2_25 * (t / 25) if t <= 25 else adv_m2_25 * (1 - (t - 25) / 25) + adv_m2_50 * ((t - 25) / 25)
if (adv_l3 < t < adv_r3 and money >= adv_m3) and sorted(P)[-1] < 58:
Advertise(3)
elif 1 and (adv_l2 < t < adv_r2 and money >= adv_m2) and sorted(P)[-1] < 59:
Advertise(2)
elif 0 and (adv_l2 < t < adv_r2 and money - 1000000 >= max_buy_count * 1.0 * 500) and sorted(P)[-1] < 59:
Advertise(2)
elif (0 < t < 0 and money >= 1200000) and sorted(P)[-1] < 59:
Advertise(2)
elif t < 4 and money >= 6000000:
Advertise(4)
elif t < 4 and money >= 3000000:
Advertise(3)
else:
buy_count = Order(t0, pa1, pa2, f1, f2, f3, f4, f5, f6, f7, g1, g2)
max_buy_count = max(max_buy_count, sum(buy_count))
if DEBUG:
if LOOP == 1:
print("-" * 20)
print("t =", t)
print("Money =", money)
receive()
if DEBUG:
if LOOP == 1:
print("Money =", money)
print("P =", P)
print("R =", R)
print("sell_count =", sell_count)
print("MI =", ["{:.2f}".format(a) for a in MI])
print("MA =", ["{:.2f}".format(a) for a in MA])
print("D =", ["{:.2f}".format(a) for a in D])
print("Flg =", best_allocation_flg)
print("Total =", sum(total_sell_count), total_sell_count)
for i in range(10):
l, r = int(MI[i] * 100 + 0.999), int(MA[i] * 100 + 0.001) + 1
L = [estimation_matrix[i][j-50] for j in range(l, r)]
print("i =", i)
print(round3(MI[i]), round3(MA[i]), round3(D[i]), l / 100, (r - 1) / 100, [round3(a) for a in L], round3(sum(L)))
print(estimate(i, 0.1), estimate(i, 0.5))
if LOCAL:
total_total += sum(total_sell_count)
if LOCAL and 4 >= LOOP > 1:
print("loop =", loop, total_sell_count, sum(total_sell_count), round(total_total / (loop + 1)))
return sum(total_sell_count)
def objective(trial):
t0 = trial.suggest_int('t0', 1, 1)
adv_l2 = trial.suggest_int('adv_l2', 1, 1)
adv_r2 = trial.suggest_int('adv_r2', 30, 45)
# adv_m2 = trial.suggest_float('adv_m2', 105 * 10 ** 4, 130 * 10 ** 4)
adv_m2_0 = trial.suggest_float('adv_m2_0', 105 * 10 ** 4, 150 * 10 ** 4)
adv_m2_25 = trial.suggest_float('adv_m2_25', 105 * 10 ** 4, 150 * 10 ** 4)
adv_m2_50 = trial.suggest_float('adv_m2_50', 105 * 10 ** 4, 150 * 10 ** 4)
adv_l3 = trial.suggest_int('adv_l3', 15, 20)
adv_r3 = trial.suggest_int('adv_r3', 40, 50)
adv_m3 = trial.suggest_float('adv_m3', 220 * 10 ** 4, 300 * 10 ** 4)
pa1 = trial.suggest_float('pa1', 0.05, 0.20)
pa2 = trial.suggest_float('pa2', 0.05, 0.20)
f1 = trial.suggest_float('f1', 0.65, 0.75)
f2 = trial.suggest_float('f2', 0.60, 0.7)
f3 = trial.suggest_float('f3', 0.60, 0.7)
f4 = trial.suggest_float('f4', 0.60, 0.8)
f5 = trial.suggest_float('f5', 0.50, 1.0)
f6 = trial.suggest_float('f6', 0.50, 1.5)
f7 = trial.suggest_float('f7', 1.00, 2.5)
g1 = trial.suggest_int('g1', 40, 60)
g2 = trial.suggest_int('g2', 40, 50)
score = main_loop(t0, adv_l2, adv_r2, adv_m2_0, adv_m2_25, adv_m2_50, adv_l3, adv_r3, adv_m3, pa1, pa2, f1, f2, f3, f4, f5, f6, f7, g1, g2)
return -score
N = 10
sell_count = [0] * N
best_allocation_flg = [0] * N
estimation_matrix = [[1 / 101] * 101 for _ in range(N)]
expected = [1.0] * N
if OP:
T, N, money = None, None, None
MI, MA, D = None, None, None
P, R, t, total_sell_count = None, None, None, None
study = optuna.create_study()
study.optimize(objective, n_trials=2000)
print("Best Params =", study.best_params)
print("Best Score =", study.best_value)
else:
total_total = 0
_t = 0
Params = {
'adv_l2': 1, 'adv_r2': 33, 'adv_m2': 1150894.1177157715,
'adv_l3': 16, 'adv_r3': 50, 'adv_m3': 2946328.352258085,
'f1': 0.7577663544011545, 'f2': 0.4828227141584538, 'f3': 0.4972439506386438,
'f4': 0.5629233324271415, 'f5': 0.5131416541498899, 'f6': 0.45233343537815346,
'f7': 0.438522644272038, 'g1': 45, 'g2': 44}
Params = {
'adv_l2': 1, 'adv_r2': 33,
'adv_m2_0': 1123020.3753850544, 'adv_m2_25': 1288743.5426866524, 'adv_m2_50': 1253489.0596099684,
'adv_l3': 16, 'adv_r3': 50, 'adv_m3': 2844417.54023583,
'f1': 0.7205992286224824, 'f2': 0.5565542576756614, 'f3': 0.4399660197983403,
'f4': 0.5212192343140634, 'f5': 0.5250031287694346, 'f6': 0.23877967298253283,
'f7': 0.10991904486471206, 'g1': 44, 'g2': 48}
Params = {'t0': 1, 'adv_l2': 1, 'adv_r2': 33, 'adv_m2_0': 1426078.8881682719, 'adv_m2_25': 1283126.1323284279, 'adv_m2_50': 1294982.9461560582, 'adv_l3': 16, 'adv_r3': 50, 'adv_m3': 2793228.676762244, 'f1': 0.9253559437203199, 'f2': 1.0782986213593686, 'f3': 0.8903959239285214, 'f4': 1.0546976032171025, 'f5': 1.0111526161355209, 'f6': 0.710258091945632, 'f7': 0.7596096884833397, 'g1': 40, 'g2': 45}
Params = {
't0': 1, 'adv_l2': 1, 'adv_r2': 33,
'adv_m2_0': 1110853.9703218008, 'adv_m2_25': 1265411.1806625545, 'adv_m2_50': 1174453.8497893137,
'adv_l3': 16, 'adv_r3': 50, 'adv_m3': 2835338.226649481,
'f1': 0.7959737776095417, 'f2': 0.6711256267655628, 'f3': 0.5458483694117402,
'f4': 0.6985138326712955, 'f5': 0.8177103445792984, 'f6': 1.1195154172991402,
'f7': 1.063274260974727, 'g1': 48, 'g2': 48}
Params = {'t0': 1, 'adv_l2': 1, 'adv_r2': 33,
'adv_m2_0': 1085794.3113618647, 'adv_m2_25': 1364320.0322415212, 'adv_m2_50': 1264407.0072151911,
'adv_l3': 16, 'adv_r3': 50, 'adv_m3': 2689021.087630408,
'f1': 0.7591365852771064, 'f2': 0.6568779372367627, 'f3': 0.5365137179442521,
'f4': 0.7301887169857361, 'f5': 0.729854029317634, 'f6': 0.6391223277425482,
'f7': 1.4121129251060212, 'g1': 44, 'g2': 42}
Params = {'t0': 1, 'adv_l2': 1, 'adv_r2': 33,
'adv_m2_0': 1070701.297158546, 'adv_m2_25': 1050631.533440852, 'adv_m2_50': 1309850.6325924492,
'adv_l3': 16, 'adv_r3': 50, 'adv_m3': 2987246.773087814,
'f1': 0.7178026016906326, 'f2': 0.6914188178555515, 'f3': 0.6086726301173585,
'f4': 0.6431800953698513, 'f5': 0.7405037759739107, 'f6': 0.6778052075743504,
'f7': 1.7592543252021107, 'g1': 45, 'g2': 50}
Params = {'t0': 1, 'adv_l2': 1, 'adv_r2': 33, 'adv_m2_0': 1057765.6554199192, 'adv_m2_25': 1390056.7800918967, 'adv_m2_50': 1129107.2582191813, 'adv_l3': 17, 'adv_r3': 44, 'adv_m3': 2976285.981496374, 'pa1': 0.19352679470982645, 'pa2': 0.19609991751700323, 'f1': 0.7152371841163966, 'f2': 0.6681160258746499, 'f3': 0.6953025097762972, 'f4': 0.6877728816092175, 'f5': 0.7546674322112074, 'f6': 0.7448776822446097, 'f7': 2.119308144498358, 'g1': 45, 'g2': 46}
for k, v in Params.items():
exec(k + str(" = ") + str(v))
t0 = 1
for loop in range(LOOP):
_t += main(t0, adv_l2, adv_r2, adv_m2_0, adv_m2_25, adv_m2_50, adv_l3, adv_r3, adv_m3, pa1, pa2, f1, f2, f3, f4, f5, f6, f7, g1, g2)
if LOCAL:
print("LOOP =", LOOP, round(total_total / LOOP), round(_t / LOOP))