競プロ初中級者100問

全国統一プログラミング王決定戦本戦A Abundant Resources

この記事で使うアルゴリズム

累積和

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_a

この問題は累積和を用いて解くことができます。

方針

全探索を考えます。区画の長さ・始点・終点についてループを回すことになるため計算量はO(N^3)で間に合いません。

区画の長さを変更してループを回す度に（部分和として）同一区間の和を求めているため冗長です。これを解消するために、あらかじめ累積和を求めておけば良いという発想に至ります。

コード

Pythonで累積和を計算したい場合、accumulateを利用すると良いです。

後ほど、累積和の差分を求めることになるので、あらかじめリストの先頭に0を挿入しておきます。

1
2
3
4
5
6
7
8
9
10
11
from itertools import accumulate
N = int(input())
A = [0] + list(map(int, input().split()))
csum = list(accumulate(A))

for i in range(1,N+1):
    ans = 0
    for j in range(N-i+1):
        diff = csum[j+i] - csum[j]        
        ans = max(diff,ans)
    print (ans)

記事情報

  • 投稿日：2020年5月16日
  • 最終更新日：2020年5月16日