累積和(cumsum)について
- ある列があり区間の評価を行いたい場合
O(n^2)をO(n)に減らす - 左から見た累積和のリストを構築し
O(1)でその区間を評価できるようにする点がキモ - 右から見た累積和の計算が少々ややこしい
(N-1-i)-(sum[N] - sum[i+1])
- にた概念として、
cumprodもある
例; 毎回ソートすることが不可能である場合
問題
N人の人が東西方向に一列に並んでいます。 それぞれの人は、東または西を向いています。 誰がどの方向を向いているかは長さ
Nの文字列Sによって与えられます。 西からi番目に並んでいる人は、E なら東を、W なら西を向いています。
あなたは、N人のうち誰か 1人をリーダーとして任命します。 そして、リーダー以外の全員に、リーダーの方向を向くように命令します。 このとき、リーダーはどちらの方向を向いていても構いません。
並んでいる人は、向く方向を変えるのを嫌っています。 そのためあなたは、向く方向を変える人数が最小になるようにリーダーを選びたいです。 向く方向を変える人数の最小値を求めてください。
解答
import math
N = int(input())
S = input()
min_turn = math.inf
sum_w = [0]
for i in range(0, N):
if S[i] == "W":
sum_w.append(sum_w[i]+1)
else:
sum_w.append(sum_w[i])
for i in range(0, N):
# 西を無ている人の数
w = sum_w[i]
# 東を無ている人の数(ここの添字が複雑)
e = (N-1-i) - (sum_w[N] - sum_w[i+1])
# 向きを変える数
turn = w + e
min_turn = min(min_turn, turn)
print(min_turn)
例; xorの性質を利用したcumsum
問題
解説 ある範囲のA_i...A_jまでのxorがkに一致するかどうかというもの
xorの交換法則を利用して(A_1...A_i) ^ ((A_1...A_j)^k) = 0という式に変形する
この式に変形すると、それぞれのcumsumの集合同士の比較で解があるかどうかがわかる
解答
import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
# X^X=0
# X^0=X
l0 = [0]
for i in range(len(A)):
l0.append(l0[-1] ^ A[i])
l1 = copy.copy(l0)
for i in range(len(l0)):
l0[i] ^= K
if len(set(l0) & set(l1)) >= 1:
print("Yes")
else:
print("No")
例; ある閉区間のソートを連続して行いたい
問題
解説
毎回ソートは間に合わない
cumsumを利用することで、範囲内の出現する要素の個数を限定と特定することができ、個数がわかっていればO(1)で計算することができる
解答
N,Q=map(int,input().split())
S=input()
cs = [None for i in range(len(S)+1)]
cs[0] = [0]*26
chidx = [0]*26
for i,s in enumerate(S, 1):
chidx[ord(s) - ord('a')] += 1 # 文字の累積和
cs[i] = chidx[:] # コピーする
que = []
for q in range(Q):
l,r,x=map(int,input().split())
diff = [ri-li for ri,li in zip(cs[r], cs[l-1])]
tmp = 0
for i, d in enumerate(diff, ord('a')):
tmp += d
if tmp >= x:
que.append(chr(i))
break
print(*que,sep='\n')
例; 任意の区間での差が最大となるようにしたい
問題
解説
cumsumを計算すれば良いとすぐわかるが、任意の区間であるから、符号の反転を一般化(足し算化)してcumsumのmin, maxのそれぞれの値の差が解となる
解答
import collections
N=int(input())
S=input()
*A,=map(int,input().split())
cs = [0]
for i in range(N):
if S[i] == "B":
A[i] = -A[i]
cs.append(cs[-1] + A[i])
print(abs(max(cs) - min(cs)))
例; cumsumした結果がゲームの状態を決定する時
問題
解説
- 自分の２倍以内のモンスターを食べられるが、何匹、残る可能性があるかという問題
- 食べられてしまう可能性のあるモンスターを求め、全体から引くことで、答えを得る
解答
import itertools
N=int(input())
*A,=map(int,input().split())
A.sort()
*C,=itertools.accumulate(A)
tmp = 0
for i in range(N-1):
if C[i]*2 < A[i+1]:
tmp = i+1
print(N-tmp)