尺取り法といえば、英語だと Two Pointers Technique とか呼ばれているように、lとr 2つのポインタを動かしながら条件に合う区間を調べるアルゴリズムですね。
いろんな人のコードを見るといろんな流派があり、l固定派と r固定派、for-while型と while-while型とか色々です。
理屈を学んでいても、いざ書こうというときに、どう書くんだっけ?となりやすいアルゴリズムでもあると思います(諸説あり)
そこで、筆者ごりちゃんがPythonでいつも使っているテンプレを共有します!
テンプレ
l固定、for-while型です。
何らかの集合に条件を満たす限りA[r]を入れて、条件を満たす区間の数を調べるシチュエーションを想定しています。
ans = 0 r = 0 for l in range(N): while r < N and #「A[r]を集合に入れたときに条件を満たすか」: #「A[r]を集合に加える」 r += 1 #「A[l]を集合から取り除く」 ans += r - l
#で記した3箇所を、実際の目的に合わせて書き換える形になります。
使用例
#SortedSet略 N,D = map(int,input().split()) A = list(map(int,input().split())) INF = 10**18 ss = SortedSet([-INF, INF]) ans = 0 r = 0 for l in range(N): while r < N and A[r] - ss.le(A[r]) >= D and ss.ge(A[r]) - A[r] >= D: ss.add(A[r]) r += 1 ss.discard(A[l]) ans += r - l print(ans)
テンプレと見比べてみてください。3箇所の記述でACしています。
条件を満たすかのところだけちょっとややこしいですが、もちろんwhileの中で判定してもokです。
おわり
尺取り法はどう書くんだっけ?ってなりがちですが、テンプレがあれば怖くない!
みなさんもテンプレを用意して良き競プロライフを!