コンテンツにスキップ

DOJ Beginner Contest 7 B - tourist vs rainboy

サイト
DOJ
コンテスト
DOJ Beginner Contest 7
問題
B - tourist vs rainboy

NN 問の問題が難しさの昇順に並んでいて、ii 番目の問題を解くには時間 AiA_i がかかります(A1≤A2≤⋯≤ANA_1 \le A_2 \le \dots \le A_N)。

tourist と rainboy は時刻 00 に解き始め、休まずに 1 問ずつ解いていきます。各問題を解き終えた時刻の和がペナルティです。tourist は 1,2,…,N1, 2, \dots, N 番の順に、rainboy は N,N−1,…,1N, N - 1, \dots, 1 番の順に解きます。rainboy のペナルティから tourist のペナルティを引いた値を求める問題です。

解く順に AA を並べたとき、kk 問目を解き終える時刻は、最初の kk 問にかかる時間の和(累積和)です。ペナルティはその累積和を全部足したものです。

  • tourist のペナルティは、AA を前から足していったときの累積和の合計です。
  • rainboy のペナルティは、AA を後ろから足していったときの累積和の合計です。

それぞれを O(N)O(N) で計算し、差をとります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = 0
x = 0
for a in A:
x += a
ans -= x
x = 0
for a in reversed(A):
x += a
ans += x
print(ans)

x が今の累積和(解き終えた時刻)です。前から足すときは ans から引き、後ろから足すときは ans に加えることで、差を直接求めています。