しゃくとり法

date: 2021-05-19 excerpt: しゃくとり法(two pointers)について

しゃくとり法(two pointers)について

ある基準を満たす区間を走査する場合、AからBまでを変数にして全区間をみるとO(n^2)の計算量がかかってしまう
A(left)が広義単調増加関数として扱えるときしゃくとり法が使え計算量がO(n)になる
参考
- しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
２つのリストの要素間の最小値を求める等にも使える

python

テンプレート1

一般化しやすい

N=int(input())
*A,=map(int,input().split())

ans = 0
left, right = 0, 0
tmp = set()
while left < N and right < N:
    if A[right] not in tmp: # 満たすか
        tmp.add(A[right])
        right += 1
        ans = max(len(tmp), ans)
    else:
        tmp.remove(A[left])
        left += 1
        if left > right:
            right = left
print(ans)

テンプレート2

segment treeを使う方法
かんたんに一般化できる

N,K=map(int,input().split())
S=[int(input()) for _ in range(N)]
 
if S.count(0) > 0:
    print(N); exit()
 
stree = Segtree(V=S, OP=lambda x,y:x*y, E=1)
ans = 0
left, right =0, 0
while left < N and right < N:
    if stree.prod(left, right+1) <= K:
        ans = max(ans, right - left + 1)
        right += 1
    else:
        left += 1
        if left > right:
            right = left
print(ans)

テンプレート3

成立している条件の個数を求める(最大値はmax関数で出せるが、個数は同じ実装では出せない)
2重whileになるので実装が複雑になっているように感じる
参考

N=int(input())
*A,=map(int,input().split())

stree0 = Segtree(V=A, OP=lambda x,y:x^y, E=0)
stree1 = Segtree(V=A, OP=lambda x,y:x+y, E=0)

acc = 0
left, right = 0, 0
while left < N:
    while right < N:
        if stree0.prod(left, right+1) == stree1.prod(left, right+1): # 成立条件
            right += 1
        else:
            break
    acc += right - left # breakしたあとのright, leftの差が成立している条件の個数の一部(累積すると全部の満たす個数が得られる)
    if left > right:
        right = left
    left += 1
print(acc)

テンプレート4

二重whileにする
rightをインクリメントするループで条件を満たさないときにbreakを最初に記述する
最も確実に動作する
- 参考1
- 参考2

import collections
N,K=map(int,input().split())
*A,=map(int,input().split())

left, right = 0, 0
Map = collections.defaultdict(int)
shurui, ans = 0, 0

while left < N:
    while right < N:
        if Map[A[right]] == 0 and shurui == K: # break条件を最初に
            break
        if Map[A[right]] == 0:
            shurui += 1
        Map[A[right]] += 1
        right += 1 # インクリメントは最後
    ans = max(ans, right - left)
    if Map[A[left]] == 1:
        shurui -= 1
    Map[A[left]] -= 1
    left += 1 # インクリメントは最後

print(ans)

例; 掛け算のしゃくとり法

問題
AtCoder Beginner Contest 032; C - 列

解答

N,K=map(int,input().split())

S=[]
for _ in range(N):
    S.append(int(input()))
if S.count(0) != 0:
    print(N)
    exit()

right = 0
calc = 1
ans = 0
for left in range(0,N):
    while right < N:
        if S[right]*calc <= K:
            calc *= S[right]
            ans = max(ans, right-left+1)
            #print(left, right, calc)
            right += 1
        else:
            break
    # leftがrightに追いついてしまったら
    # rightをインクリメントする
    # (これを入れ忘れると間違う)
    if left == right:
        right += 1
    else:
        # インクリメント時に前の情報を消す
        calc /= S[left]
print(ans)

例; ２つのリストの要素の最小値を求める

問題
NOMURA プログラミングコンテスト 2021(AtCoder Regular Contest 121)
解説
計算量をO(N^2)からO(2N)に変換することができる

A = [i for i in range(10**4) if random.random() <= 0.1 ]
B = [i for i in range(10**4) if random.random() <= 0.1 ]
i, j = 0, 0
ans = 0
while i < len(A) and j < len(B):
    ans = min(ans, abs(A[i] - B[j]))
    if A[i] > B[j]:
        j += 1
    else:
        i += 1
print(ans)

実験コード

解答
submission