とは思いませんか？（強引）
数列の部分和に関する問題って、ABCのC,DとかAGCのA,Bとか、まあまあ結構な頻度で出ているので、問題とその解き方をまとめておこうと思い立った
主に累積和やしゃくとり法などについてまとめる
AGC023A
A - Zero-Sum Ranges
問題文
長さNの整数列Aがあります。Aの空でない連続する部分列であって、その総和が0になるものの個数を求めてください。 ただし、ここで数えるのは部分列の取り出し方であることに注意してください。つまり、ある2つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。
例えば、
1 3 -4 2 2 -2
の中の、総和が0になる部分列は
(1,3,-4),(-4,2,2),(2,-2)の3つですよって話
答え
累積和を計算し、その和が共通の部分に着目する
先ほどの例での累積和を計算すると、（初項は何も足さないという意味で0にする、これは「初項からの和を選ぶ」というために重要な操作）
0 1 4 0 2 4 2
である
この部分和の数列で、値が等しいところを二つもってくれば、その間の和は（なにも増えていないので）０になる だから、答えは同じ累積和となる場所の選び方に等しい（0,2,4はそれぞれ1組ずつ選べるので、計3通りになる）
以下はpython3によるコード
N = int(input()) A = list(map(int,input().split())) R = [0] #Rは累積和を格納するリストです for i in range(N): R.append(R[i]+A[i]) #累積和を入れます R.sort() R.append(10**18) #カウントを止めます（番兵） cnt = 1 ans = 0 cur = R[0] #curは今見ている累積和を表します for i in range(1,N+2): #番兵の所で止まるように、N+1まで数えます if cur == R[i]: cnt += 1 #curと新たに見たR[i]が等しければインクリメント else: ans += cnt*(cnt-1)//2 cur = R[i] #違っていたら、curをR[i]に更新 cnt = 1 #cntを1に戻す print(ans)
ABC037C
C - 総和
問題文
長さNの数列 {a_i}と1以上N以下の整数Kが与えられます。この数列には長さKの連続する部分列がN-K+1個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。
例えば、N==5,K==3であれば、
1 2 4 8 16
という数列の中に、長さ3の部分列は(1,2,4),(2,4,8),(4,8,16)の3つがあり、これらの総和は7+14+28=49となる
答え
普通に和を計算してると、Kが大体N/2くらいだった時に、その部分を計算するのでO(N)、さらにそれをN/2回やることになりさらにO(N)でO(N**2)となり、N==10**5ではさすがに間に合わない
累積和を使うことで、計算をO(N)まで落とすことが可能（累積和を計算しておけば、K項間の和は一回の引き算で求まるため）
以下はpython3によるコード
N,K = map(int,input().split()) L = list(map(int,input().split())) R = [0] #累積和を格納します ans = 0 for i in range(0,N): R.append(R[i]+L[i]) for j in range(N-K+1): ans += R[j+K]-R[j] #K項離れた累積和の差が加算されます print(ans)
ABC105D
D - Candy Distribution
問題文
N個の箱が左右一列に並んでおり、左からi番目の箱にはA_i個のお菓子が入っています。あなたは、連続したいくつかの箱からお菓子を取り出してM人の子供たちに均等に配りたいと考えています。そこで、以下を満たす組(l,r)の総数を求めてください。
- l,rはともに整数であり1≤l≤r≤Nを満たす
- A_l+A_(l+1)+...+A_rはMの倍数である
例えば、4 1 5という入力が与えられて、M == 2であった場合は、
(4)と(4,1,5)という二組が、2の倍数になる
答え
累積和と同じ要領で、i番目までの和をMで割った余りを保持しておく
そして、その余りが等しいものを選べば、その間にある項の総和はMでわった余りが0になる
以下はpython3によるコード
N,M = map(int,input().split()) L = list(map(int,input().split())) L.insert(0,0) #Lの先頭に0（Mで割った余りが0）をいれた for i in range(1,N+1): L[i] = (L[i-1]+L[i])%M #累積和を計算する所を、Mで割るように変更 L.sort() p = L[0] cnt = 1 ans = 0 L.append(0) for i in range(N+1): if L[i+1] == p: #あとは同じ数字の組を数える cnt += 1 else: if cnt == 1: cnt = 1 p = L[i+1] else: ans += (cnt)*(cnt-1)//2 cnt = 1 p = L[i+1] print(ans)
ABC032C
C - 列
問題文
長さNの非負整数列S=s1,s2,...,sNと整数Kがあります。 あなたの仕事は、以下の条件を満たすSの連続する部分列のうち、最も長いものの長さを求めることです。部分列の長さは1以上の列でないといけません。
- その部分列に含まれる全ての要素の値の積は、K以下である。
もし条件を満たす部分列が一つも存在しないときは、0を出力してください。
答え
しゃくとり法を使う
注意すべきことは2/28の記事に大体書いてあります
以下はpython3によるコード
N,K = map(int,input().split()) L = [] for i in range(N): L.append(int(input())) startindex = 0 #最初はスタートとエンドの番号が0になっています endindex = 0 length = 0 #ここで尺取り虫の長さを管理します mul = 1 #積を管理します ans = 0 #最終的な答えです while startindex <= N-1: #スタートがまだ数列の終わりに無い時の話です if 0 < mul <= K: #積が0より大きくK以下であれば if endindex < N: #エンドインデックスを考慮して if mul*L[endindex] <= K: #エンドインデックスを掛けて良いなら mul = mul*L[endindex] #掛けます endindex += 1 #エンドインデックスを+1して length += 1 #尺取り虫の長さを1増やします if ans < length: ans = length #答えを更新するかの判断 else: #エンドインデックスが掛けられないなら if startindex == endindex: #スタートとエンドが同じなら startindex += 1 #スタートとエンドを1つずつずらします endindex += 1 else: #スタートとエンドが違うなら mul = mul//L[startindex] #スタートで割ります startindex += 1 #尺取り虫が後ろの方から進みます length -= 1 else: startindex = N #エンドインデックスが数列の終わりまで来たので、これ以上伸ばしません elif mul > K: if K != 0: mul = mul//L[startindex] startindex += 1 length -= 1 else: #K==0という特殊な状況を考えます L.sort() #リストの中に0があるかを探すためにソートします if L[0] != 0: startindex = N ans = 0 #Kが0であるうえ、リストの中に0がないなら用無しです else: startindex = N #0があれば任意の長さでOKなので打ち切ります ans = N else: #積が途中で0になってしまったら、Kが任意の値であっても数列は任意の長さが取れます ans = N startindex = N print(ans)
