1次元配列上のアルゴリズム
私事ですがAtCoder社様の開催されるプログラミングコンテストについて、最近はヒューリスティックのAHC(AtCoder Heuristic Contest)のほうばかりに参加してアルゴリズムのほう(ABC,ARC,AGC)への参加がおろそかになってます。
これはいかんと思い最近はまたアルゴリズムの勉強をし直しているのですが、なんか色々忘れてる感じがあるのでその思い出しのためのメモになります。
今回は1次元配列で、特に文字列処理や動的計画法、データ構造関係っぽくないものをまとめます(ぽくなさは完全に主観です。なんなら普通に動的計画法やデータ構造が出てきます)。
目次
- 累積和(Cumulative Sum)による部分和
- 最大部分配列問題(maximum subarray problem)
- しゃくとり法(Two Pointers)
- 累積和の逆演算による区間更新(Difference Array)
- 二分探索(Binary Search)
- ヒストグラム内の最大長方形
- 最長増加部分列(longest increasing subsequence)
- 転倒数(Inversion)
- Mo's algorithm
- Sliding Window Aggregation (SWAG)
累積和(Cumulative Sum)による部分和
任意の数列$A=(a_0,\cdots,a_{N-1})$。
クエリ：与えられる区間$[i,j)$に対し、$a_{i} + \cdots + a_{j-1}$を答えよ。
-
愚直。クエリごとに$\mathcal{O}(N)$
ans = 0 for k in range(i,j): ans += A[k] print(ans)同じ部分和の計算を何回も行ってて遅い→まとめる。
-
累積和を使用。準備に$\mathcal{O}(N)$。各クエリに$\mathcal{O}(1)$
cumsum = [0] t = 0 for a in A: t += a cumsum.append(t) # cumsum[i] = $a_0 + ... + a_{i-1}$ print(cumsum[j] - cumsum[i])
補足: 演算に$a_i + \cdots + a_{j-1} = a_0 + \cdots + a_{j-1} - (a_0 + \cdots + a_{i-1})$を使用しているため、累積和の使用には演算に引き算と可換性が必要。
例えば$a + b := \min(a,b)$とかには使えない。
最大部分配列問題(maximum subarray problem)
任意の数列$A=(a_0,\cdots,a_{N-1})$。
クエリ：連続する部分列の総和の最大値を求めよ。
-
Kadane's algorithm。$\mathcal{O}(N)$
ans = -1<<60 # -inf s = 0 for a in A: s = max(s+a, a) ans = max(ans, s) print(ans)
求めてるのは$\max_{1\leq i < j \leq N} { \sum_{k=i}^{j-1} a_k}$。トロピカル演算$(\oplus, \otimes)$で書き直せば$\oplus_{1\leq i < j \leq N} (\otimes_{k=i}^{j-1} a_k)$、つまりあらゆる部分積の総和となる。この見方で言うと、このアルゴリズムは任意の半環で成立する(展開すれば自明)。もっと言えば、隣り合う要素の演算さえ定義されていればよい。
計算してみると実際、あらゆる部分積の総和を求めていることが分かる(0は積の単位元、$-\infty$は和の単位元)。見づらい。
$s_0 = (0 \otimes a_0) \oplus a_0 = a_0$
$ans_0 = -\infty \oplus s_0 = a_0$
$s_1 = (a_0 \otimes a_1) \oplus a_1$
$ans_1 = ans_0 \oplus s_1 = a_0 \oplus (a_0 \otimes a_1) \oplus a_1$
$s_2 = ((a_0 \otimes a_1) \oplus a_1) \otimes a_2 \oplus a_2 = a_0 \otimes a_1 \otimes a_2 \oplus a_1 \otimes a_2 \oplus a_2$
$ans_2 = ans_1 \oplus s_2 = a_0 \oplus a_0 \otimes a_1 \oplus a_0 \otimes a_1 \otimes a_2 \oplus a_1 \oplus a_1 \otimes a_2 \oplus \cdots$
しゃくとり法(Two Pointers)
正整数の数列$A=(a_1,\cdots,a_N)$。
クエリ：総和が$K$以下になる連続部分列の最大の長さを答えよ。
-
愚直。累積和を使用。クエリに対して$\mathcal{O}(N^2)$
ans = 0 for i in range(N): for j in range(i+1,N): if cumsum[j] - cumsum[i] <= K: ans = max(ans, j-i) print(ans) -
しゃくとり法。クエリに対して$\mathcal{O}(N)$。実装や問題のバリエーションは色々考えられると思います。
ans = 0 r = 0 s = 0 # 総和部分 # [l,r)での総和は常にK以下であるように組むと考えやすい # [)...からスタート([l,r)=\emptyの想定) for l in range(N): # 左が右へ詰める => .[..).. -> ..[.).. while r < N and s + A[r] <= K: # 右が進んでも条件を満たすなら s += A[r] r += 1 # 右を進める => .[.)... -> .[..).. # while脱出時、右端は条件(sum<=K)を満たすギリギリ ans = max(ans, r-l) # 右端を固定して、(r-l)を加味する if l == r: # .[).. r += 1 # lに追い越されないように=>.[.). else: s -= A[l] # 次で左端が右に詰めるため、和を減らす # 最後は....[)となっている print(ans)
累積和の逆演算による区間更新(Difference Array)
数直線上の区間$[i,j) \subset [0,N)$に値$a$を足す操作を$M$回行う。
クエリ：操作後の点$x$における値を求めよ。
-
愚直：操作に$\mathcal{O}(MN)$
for (i,j), a in queries: for k in range(i,j): v[k] += a print(v[x]) -
累積和の逆：操作準備に$\mathcal{O}(M)$。累積和に$\mathcal{O}(N)$で合計$\mathcal{O}(M+N)$
Nがとても大きい場合は、適当な座標圧縮を噛ませばよい。for (i,j), a in queries: t[i] += a # i.... t[j] += -a # ...| j... という状態をイメージ v = cumsum(t) # 累積和でイメージを現実に print(v[x])
このアイデアやその拡張はimos法とも呼ばれているようです。多次元配列や、木の上でも行われたりします。
二分探索(Binary Search)
命題$f(x), x \in [0,T)$はある$K\in [0,T)$未満で偽、$K$以上で真となる。$K$を求めよ。
-
愚直は$\mathcal{O}(T)$
-
二分探索して$\mathcal{O}(\log(T))$
l = 0 # f(l)は常に偽 r = T # f(r)は常に真 while r-l > 1: # (l,r)=(K-1,K)で終了 k = (l+r)//2 if f(k): r = k else: l = k print(r)
ヒストグラム内の最大長方形
数列$A=(a_0,\cdots,a_{N-1})$で表されるヒストグラム内にある面積最大の長方形の面積を求める。
-
愚直は$\mathcal{O}(N^2)$。
area = 0 for i in range(N): h = inf # 疑似無限大 for j in range(i,N): h = min(h, A[j]) temp = h * (j-i+1) area = max(area, temp) -
stackを使うことで$\mathcal{O}(N)$で求まる。
area = 0 stack = [] for i,a in enumerate(A): pi = i while stack and stack[-1][0] > a: pa,pi = stack.pop() area = max(area, pa * (i-pi)) stack.append((a,pi)) while stack: pa,pi = stack.pop() area = max(area, pa * (len(A)-pi)) print(area)
最長増加部分列(longest increasing subsequence)
数列$A=(a_0,\cdots,a_{N-1})$の連続とは限らない部分列で、(広義)単調増加なものの最大の長さを求めよ。
- 二分探索による$\mathcal{O}(N\log{N})$
import bisect inf = 1 << 60 # L[i]は長さiの部分増加列の最小の最大値(infなら実現不可能) L = [inf] * len(A) for a in A: n = bisect.bisect_left(L,a) # 狭義単調増加 # n = bisect.bisect_right(R,a) # 広義単調増加 L[n] = a # aを使って長さnの部分増加列の最小最大値を更新(inf->aなら最大の長さの更新になる) print(bisect.bisect_left(L,inf)) # 実現可能な最大値
動的計画法ですね。
セグメント木使っても(定数倍遅いが)できます。
- セグメント木による方法
# max演算によるSegment tree (第三引数はデフォルト値) # i番目の値は"A[i]を最後の値とする部分増加列の最大長" seg = SegmentTree([0]*len(A),max,0) index = sorted([(s,i) for i,s in enumerate(A)]) # 狭義単調増加 #index = sorted([(s,i) for i,s in enumerate(A)]), key=lambda x : (x[0],-x[1])) # 広義単調増加 for _, i in index: # インデックスのみ使用 # A[i]が小さい値のiから順番に決定されていく seg.set(i, seg.get(0,i) + 1) print(seg.get(0,len(A)))
転倒数(Inversion)
整数列$(1,2,\cdots,N)$の置換$(P_1,\cdots,P_N)$がある。置換の回数を求めよ。
転倒数：#$\lbrace (i,j) | i <j, P_j < P_i \rbrace $と等しくなる。Binary Indexed Treeやセグメント木などを使って$\mathcal{O}(N \log{N})$で計算できる。
- セグメント木を使う。
ans = 0 # 加算(+)によるSegment Tree seg = SegmentTree([0]*N, add, 0) for i in range(N): # 0-indexに注意 ans += seg.get(P[i],N) # j<iかつP[i]<P[j]となるjの個数が足される seg.set(P[i],1) # 次ターン以降のための準備
Mo's algorithm
長さ$N$の配列$A=(a_0,\cdots,a_{N-1})$上の区間$[l_i,r_i)$に対する$Q$個のクエリを、処理順番を工夫することで愚直の$\mathcal{O}(NQ)$から$\mathcal{O}((N+Q)\sqrt{N})$に抑えるテクニック。処理の内容に制限があることに注意。
例えば区間$(a_l,\cdots,a_{r-1})$に入っている種類数を求めるのは以下の形になる。
def MoSort(lr):
block = N // int(Q**0.5)
def val(x):
n = x[0] // block # 所属するブロックの番号
# lに対してブロック番号でソート(同じ番号ならrで決まる)
# rに対してブロック番号が偶数なら昇順、奇数なら降順に並べる
return 2 * n * N + (-1 if n & 1 else 1) * x[1] # 上を実現する適当な評価関数
lr.sort(key = val)
# 各クエリ[l_i,r_i)における種類数を求める
LRI = [(l,r,i) for i,(l,r) in enumerate(LR)] # [l,r)
MoSort(LRI)
submit = [-1] * Q
cnt = defaultdict(int)
pl,pr = 0,0 # 初期状態
for l,r,j in LRI:
if l < pl:
for i in range(l,pl):A # lが左に伸びる
cnt[A[i]] += 1
if cnt[A[i]] == 0: # 無くなったら削除する
del cnt[A[i]]
else:
for i in range(pl,l): # lが右に縮む
cnt[A[i]] -= 1
if cnt[A[i]] == 0:
del cnt[A[i]]
if pr < r:
for i in range(pr,r): # rが右に伸びる
cnt[A[i]] += 1
if cnt[A[i]] == 0:
del cnt[A[i]]
else:
for i in range(r,pr): # rが左に縮む
cnt[A[i]] -= 1
if cnt[A[i]] == 0:
del cnt[A[i]]
submit[j] = len(cnt)
pl,pr = l,r
Sliding Window Aggregation
長さ$N$の配列$A=[a_0,\cdots,a_{N-1}]$上の$M$個の区間$[l_i,r_i)$(ただし$l_i\leq l_{i+1}, r_i \leq r_{i+1}$とする)に対するモノイド演算の結果を$\mathcal{O}(N+M)$で求めるデータ構造。
実装の1つとして、4つのstackを使うものがある。
class SlidingWindowAggregation:
def __init__(self,op,e):
self.front = []
self.front_sum = []
self.back = []
self.back_sum = []
self.op = op
self.e = e
def fold_all(self): # スライド内の演算結果を出力
if self.front and self.back:
return self.op(self.front_sum[-1],self.back_sum[-1])
elif self.front:
return self.front_sum[-1]
elif self.back:
return self.back_sum[-1]
else:
return self.e
def push(self,x): # pushはbackに貯めていく
self.back.append(x)
if self.back_sum:
self.back_sum.append(self.op(self.back_sum[-1],x))
else:
self.back_sum.append(x)
def pop(self): # popの段階でfrontが空ならbackのを移転する
if not self.front:
while self.back:
self.front.append(self.back.pop())
self.back_sum.clear()
self.front_sum.append(self.front[0])
for v in self.front[1:]:
self.front_sum.append(self.op(self.front_sum[-1],v))
if self.front: # 空でなければそのまま取り出す
self.front_sum.pop()
return self.front.pop()
return self.e
また何か思い出したら追記していきたいと思います。