しゃくとり法(two pointer approach)

どういう場合で使えるか

こちらの記事を引用させていただくと、以下のような問題を解くのに使える。

長さのn数列 a1, a2, a3, ... , anにおいて
- 「条件」を満たす区間 (連続する部分列) のうち、最小の長さを求めよ
- 「条件」を満たす区間 (連続する部分列) のうち、最大の長さを求めよ
- 「条件」を満たす区間 (連続する部分列) を数え上げよ

尺取り法

範囲を表現するleftとrightを用意する。(0<= left <= right <= n)
初期状態ではleftもrightも0(つまり、leftもrightも数列の先頭にいる)。

以下を繰り返す

  • [left, right)の範囲で条件を満たす限り、rightを進める。→rightが進められなくなる(rightが数列の末尾に達する OR rightを進めると条件を満たさなくなってしまう)。
    • left<rightなら、部分解を求めてleftを進める。
    • left==rightなら、leftもrightも両方とも進める。

example

問題

要素の和が20以下になる連続する部分列を数え上げよ。

プログラム

package main

import "fmt"

func shakutori(data []int, left, right int, cond func(d []int, l, r int) bool) int {
    if right+1 <= len(data) && cond(data, left, right+1) {
        return shakutori(data, left, right+1, cond)
    }
    if right+1 <= len(data) && left == right {
        return shakutori(data, left+1, right+1, cond)
    }
    if left+1 <= len(data) {
        return right - left + shakutori(data, left+1, right, cond)
    }
    return 0
}


func main() {
    data := []int{1, 3, 9, 1, 20, 2, 9, 33, 11, 6}
    left, right := 0, 0
    cond := func(d []int, l, r int) bool {
        sum := 0
        for _, v := range d[l:r] {
            sum += v
        }
        return sum <= 20
    }
    ans := shakutori(
        data,
        left,
        right,
        cond,
    )
    fmt.Println(ans)
}

right - leftの所が部分解になっている。

参考

www.kumilog.net

bmf-tech.com

qiita.com