用語解説 - 尺取法

英語ではtwo pointersなどと言う.
例題にて説明する.
数列 $\{A_k\}_{k=1}^M, \;\; \{B_k\}_{k=1}^N$ が与えられた時,$A_i+B_j = x$ なる $(i,j)$ のペアを列挙したいとする.
ただし,$A_1 < A_2 < \cdots < A_M$ かつ $B_1 < B_2 < \cdots < B_N$ とソートされており,それぞれの数列内に同じ整数はないとする.
このとき,最初 $j=N$ とセットし,$i=1,2,\ldots,M$ と動かしていき探していく.
各 $i$ の値の時に,ペアと成る $j$ の値をどうやって探すかというと,$A_i+B_j$ が $x$ より大きい限り $j$ の値を減らす.
(この問題の場合は必要ないが,$A_i+B_j$ が $x$ より小さいと $j$ の値を増やす)
また $j$ の値は毎回リセットするのではなく,次の $i$ の値の時は,前回の $i$ の値の時に使用した $j$ の値からスタートする.
この問題の場合は,$j$ は減っていく一方で,$j$ を減らす回数の最大値は $O(N)$ であるので,合計で $O(M+N)$ 時間で求めることができる.
これは,各 $i$ について二分探索で $j$ を求める $O(N \log M)$ と比較して高速.
このように,$2$ つ以上の整数のペアを求める場合に,$1$ つを除く整数($i$ とする)について指し示す場所を決めておいて,リセットせずに使いまわし,$i$ が動くたびに前後に調整するように動かす方法を尺取法と呼ぶ.

尺取法が出てくる問題


Current time: 2017年07月22日09時46分14秒
Last modified: 2014年08月06日02時03分25秒 (by laycrs)
Tags: no_tags
トップページに戻る

Logged in as: unknown user (not login)

ログイン: