結果
問題 | 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 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 166 ms
94,300 KB |
testcase_01 | AC | 166 ms
93,756 KB |
testcase_02 | AC | 134 ms
93,764 KB |
testcase_03 | AC | 134 ms
94,332 KB |
testcase_04 | AC | 139 ms
93,848 KB |
testcase_05 | AC | 142 ms
93,872 KB |
testcase_06 | AC | 167 ms
93,848 KB |
testcase_07 | AC | 142 ms
94,164 KB |
testcase_08 | AC | 144 ms
94,012 KB |
testcase_09 | AC | 141 ms
94,024 KB |
testcase_10 | AC | 142 ms
93,544 KB |
testcase_11 | AC | 145 ms
93,936 KB |
testcase_12 | AC | 139 ms
94,048 KB |
testcase_13 | AC | 136 ms
94,128 KB |
testcase_14 | AC | 138 ms
93,412 KB |
testcase_15 | AC | 159 ms
93,536 KB |
testcase_16 | AC | 145 ms
94,180 KB |
testcase_17 | AC | 140 ms
93,972 KB |
testcase_18 | AC | 143 ms
94,212 KB |
testcase_19 | AC | 142 ms
93,720 KB |
testcase_20 | AC | 139 ms
94,304 KB |
testcase_21 | AC | 145 ms
94,016 KB |
testcase_22 | AC | 144 ms
93,748 KB |
testcase_23 | AC | 144 ms
93,880 KB |
testcase_24 | AC | 142 ms
93,640 KB |
testcase_25 | AC | 140 ms
93,544 KB |
testcase_26 | AC | 146 ms
93,744 KB |
testcase_27 | AC | 139 ms
94,052 KB |
testcase_28 | AC | 141 ms
93,980 KB |
testcase_29 | AC | 142 ms
94,044 KB |
testcase_30 | AC | 141 ms
93,948 KB |
testcase_31 | AC | 164 ms
94,376 KB |
testcase_32 | AC | 149 ms
94,476 KB |
testcase_33 | AC | 137 ms
93,800 KB |
testcase_34 | AC | 143 ms
93,720 KB |
testcase_35 | AC | 147 ms
93,892 KB |
testcase_36 | AC | 145 ms
93,752 KB |
testcase_37 | AC | 142 ms
93,456 KB |
testcase_38 | AC | 166 ms
94,128 KB |
testcase_39 | AC | 146 ms
94,272 KB |
testcase_40 | AC | 145 ms
93,844 KB |
testcase_41 | AC | 144 ms
93,704 KB |
testcase_42 | AC | 143 ms
94,152 KB |
testcase_43 | AC | 145 ms
94,076 KB |
testcase_44 | AC | 162 ms
94,028 KB |
testcase_45 | AC | 143 ms
94,084 KB |
testcase_46 | AC | 141 ms
94,132 KB |
testcase_47 | AC | 141 ms
93,872 KB |
testcase_48 | AC | 143 ms
93,536 KB |
testcase_49 | AC | 144 ms
93,776 KB |
testcase_50 | AC | 142 ms
94,048 KB |
testcase_51 | AC | 166 ms
93,824 KB |
testcase_52 | AC | 140 ms
94,072 KB |
testcase_53 | AC | 141 ms
94,000 KB |
testcase_54 | AC | 139 ms
94,380 KB |
testcase_55 | AC | 137 ms
94,112 KB |
testcase_56 | AC | 146 ms
93,812 KB |
testcase_57 | AC | 146 ms
93,904 KB |
testcase_58 | AC | 145 ms
94,052 KB |
testcase_59 | AC | 149 ms
94,016 KB |
testcase_60 | AC | 141 ms
94,144 KB |
testcase_61 | AC | 143 ms
93,780 KB |
testcase_62 | AC | 141 ms
94,260 KB |
testcase_63 | AC | 141 ms
93,548 KB |
testcase_64 | AC | 163 ms
94,116 KB |
testcase_65 | AC | 140 ms
93,688 KB |
testcase_66 | AC | 143 ms
93,544 KB |
testcase_67 | AC | 138 ms
94,132 KB |
testcase_68 | AC | 138 ms
94,008 KB |
testcase_69 | AC | 140 ms
94,228 KB |
testcase_70 | AC | 146 ms
94,096 KB |
testcase_71 | AC | 164 ms
93,896 KB |
testcase_72 | AC | 143 ms
94,512 KB |
testcase_73 | AC | 141 ms
94,540 KB |
testcase_74 | AC | 139 ms
93,560 KB |
testcase_75 | AC | 142 ms
93,996 KB |
testcase_76 | AC | 145 ms
94,224 KB |
testcase_77 | AC | 141 ms
94,192 KB |
testcase_78 | AC | 144 ms
93,672 KB |
testcase_79 | AC | 141 ms
93,864 KB |
testcase_80 | AC | 143 ms
94,156 KB |
testcase_81 | AC | 138 ms
93,604 KB |
testcase_82 | AC | 137 ms
93,976 KB |
testcase_83 | AC | 138 ms
94,260 KB |
testcase_84 | AC | 160 ms
93,604 KB |
testcase_85 | AC | 143 ms
94,052 KB |
testcase_86 | AC | 144 ms
94,124 KB |
testcase_87 | AC | 147 ms
93,764 KB |
testcase_88 | AC | 142 ms
93,904 KB |
testcase_89 | AC | 143 ms
94,392 KB |
testcase_90 | AC | 142 ms
94,112 KB |
testcase_91 | AC | 168 ms
94,408 KB |
testcase_92 | AC | 141 ms
94,212 KB |
testcase_93 | AC | 144 ms
93,712 KB |
testcase_94 | AC | 142 ms
94,120 KB |
testcase_95 | AC | 140 ms
94,508 KB |
testcase_96 | AC | 141 ms
94,200 KB |
testcase_97 | AC | 155 ms
94,012 KB |
testcase_98 | AC | 145 ms
93,812 KB |
testcase_99 | AC | 142 ms
93,904 KB |
ソースコード
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))