DOJ Beginner Contest 7 B - tourist vs rainboy
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 7
- 問題
- B - tourist vs rainboy
問の問題が難しさの昇順に並んでいて、 番目の問題を解くには時間 がかかります()。
tourist と rainboy は時刻 に解き始め、休まずに 1 問ずつ解いていきます。各問題を解き終えた時刻の和がペナルティです。tourist は 番の順に、rainboy は 番の順に解きます。rainboy のペナルティから tourist のペナルティを引いた値を求める問題です。
解く順に を並べたとき、 問目を解き終える時刻は、最初の 問にかかる時間の和(累積和)です。ペナルティはその累積和を全部足したものです。
- tourist のペナルティは、 を前から足していったときの累積和の合計です。
- rainboy のペナルティは、 を後ろから足していったときの累積和の合計です。
それぞれを で計算し、差をとります。
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 に加えることで、差を直接求めています。