コンテンツにスキップ

DOJ Beginner Contest 9 B - Rating Updates

サイト
DOJ
コンテスト
DOJ Beginner Contest 9
問題
B - Rating Updates

最初のレーティングは R0R_0 です。NN 個のコンテストに順に参加し、ii 番目のパフォーマンスが PiP_i のとき、レーティングは

Ri=3Ri−1+Pi4R_i = \frac{3 R_{i-1} + P_i}{4}

に更新されます。最終的なレーティング RNR_N を求める問題です。どの RiR_i も正の整数になることが保証されています。

テストケースは T≤105T \le 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

式のとおりに RR を NN 回更新します。計算量はテストケース全体で O(∑N)O(\sum N) です。

RiR_i が整数になることが保証されているので、3Ri−1+Pi3 R_{i-1} + P_i は必ず 44 で割り切れます。そのため、整数の割り算 // で正確に計算できます。

Python
for _ in range(int(input())):
N, R = map(int, input().split())
P = list(map(int, input().split()))
for p in P:
R = (3 * R + p) // 4
print(R)