ツーポインタ法

概要

配列上のインデックスを $2$ つ持ち、それを並行して動かすことで処理を高速化する方法。
sliding window法や尺取法の基礎となる。

片方が長さ $N$ の配列、片方が長さ $M$ の配列上を動く場合、素直にやると $O(MN)$ かかる。
しかし、都合のいい条件を満たす場合に、ツーポインタ法を用いれば $O(M+N)$ で済む。

例えば、以下の $2$ つの単調非減少数列があるとする。

A: 1 2 4 4 7
B: 3 4 7 8

$A$ と $B$ から $1$ つずつ値を選んで和が $10$ 以下になる組の数を求めよう。

まず、素直に全探索すると、要素数の積である $20$ 通り調べることになる。
そして、以下の表の青い部分の個数である $13$ 個が答えとなる。

$B\backslash A$	$1$	$2$	$4$	$4$	$7$
$3$	$4$	$5$	$7$	$7$	$10$
$4$	$5$	$6$	$8$	$8$	$11$
$7$	$8$	$9$	$11$	$11$	$14$
$8$	$9$	$10$	$12$	$12$	$15$

しかし、実はこれの青マスの数を調べるには、最悪でも $8$ ヶ所調べればよい。
というのも、$A$ と $B$ が単調非減少であるために、この表には以下の規則が存在する。

よって、以下のように移動するだけで、青と赤の境界が完全にわかるのである。

そして、青から右に進むとき、自身を含めて上に何個マスがあるかを加算していけばよい。

$B\backslash A$	$1$	$2$	$4$	$4$	$7$
$3$	?	?	?	?	$10$
$4$	?	?	$8$	$8$	$11$
$7$	?	?	$11$	?	?
$8$	$9$	$10$	$12$	?	?

実際の値の変化を表にすると以下のようになる。

`i`	`j`	$A_i$	$B_j$	和	組数総計	処理
$0$	$3$	$1$	$8$	$9$	$4$	$B_0$ から $B_3$ までの $4$ 個を加え、右に進む
$1$	$3$	$2$	$8$	$10$	$8$	$B_0$ から $B_3$ までの $4$ 個を加え、右に進む
$2$	$3$	$4$	$8$	$12$	$8$	$10$ を超えたので上に進む
$2$	$2$	$4$	$7$	$11$	$8$	$10$ を超えたので上に進む
$2$	$1$	$4$	$4$	$8$	$10$	$B_0$ から $B_1$ までの $2$ 個を加え、右に進む
$3$	$1$	$4$	$4$	$8$	$12$	$B_0$ から $B_1$ までの $2$ 個を加え、右に進む
$4$	$1$	$7$	$4$	$11$	$12$	$10$ を超えたので上に進む
$4$	$0$	$7$	$3$	$10$	$13$	$B_0$ の $1$ 個を加え、右に進む

実装例は以下。
$i$ は最大 $M$ 回、$j$ は最大 $N$ 回しか動かない。
そのため、全体の計算量は $O(M+N)$ となる。

int m = a.size();
int n = b.size();
long long sum = 0;

for (int i=0, j=n-1; i<m; i++) {
  while (j>=0&&a[i]+b[j]>10) j--;
  sum += j+1;
}

単調性の向き次第では、左上から出発して右下へ向かう場合もある。
また、インデックスを同時に $3$ つ走らせるスリーポインタ法などになることもある。

縦横それぞれ単調性があれば和以外でも使え、応用の幅はかなり広い。

ツーポインタ法で $O(M+N)$ にできるのは、各インデックスを一方向にだけ動かせばよい場合である。
このような単調性がない場合は、そのままツーポインタ法を使うことはできない。