コンテンツにスキップ

尺取り法

タグ「尺取り法」の記事 2 件

尺取り法のリンク集

尺取り法(しゃくとり法)について、参考になる記事や資料をまとめました。

尺取り法は、数列の区間 [l,r)[l, r) の左端と右端をどちらも右にだけ動かしながら、条件を満たす区間を調べる手法です。「区間が条件を満たすなら、それに含まれる区間も満たす」(または「それを含む区間も満たす」)という単調性があると、左端 ll ごとの右端の境目が ll について単調になります。そのため、右端を伸ばせるだけ伸ばし、次に左端を 1 つ縮める、を繰り返すと、全体で O(N)O(N) 回の操作で済みます。条件を満たす区間の最大長・最小長・個数を求めるときによく使われます。

区間の和で判定するときは、値が非負(正)であることが単調性の前提です。負の値があると使えないので、累積和と二分探索やデータ構造を組み合わせる方法を考えます。また、ソートした配列の両端から 2 本のポインタを寄せていく方法も、two pointers と呼ばれます。

  • しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ(drken、Qiita)
    • 尺取り法が使える場面を「条件を満たす区間の最小長・最大長・個数」の 3 つに整理し、AOJ DSL_3_C を例に、素朴な O(n2)O(n^2) の方法から「右端の境目が左端について広義単調増加」という観察を経て O(n)O(n) にするまでを、図と C++ のコードで説明しています。使える条件、二分探索との類似、スライド最小値や Convex Hull Trick との関係まで扱い、最後に AtCoder などの問題例が並んでいます。
    • 細かい誤記がいくつかあります。たとえば最後の問題「L番目のK番目の数」の出典が、冒頭では JOI 2017 予選 E、本文では予選 F となっています(AtCoder 上では JOI 2018 予選 F)。また、ABC098 D の問題概要は「正の整数列」とありますが、実際は 00 も含みます。
  • 競プロ典型 90 問 034 の解説(E869120、画像)
    • 値の種類が KK 以下の最長の区間を求める問題を例に、左端 ii ごとの右端の限界 cic_i を表にし、c1≤c2≤⋯c_1 \le c_2 \le \cdots という単調性から操作が合計 2N2N 回で済むことを 1 枚で説明しています。C++ の解答コードと、類題の一覧もあります。
  • しゃくとり法のDequeを使ったバグりにくい実装(keroru、Qiita)
    • 添字を動かす代わりに、右端の要素を deque に入れ、条件を満たさない間は先頭から取り出す実装を、ABC032 C を例に Python で説明しています。deque の中身の推移をデバッグ出力で見せ、一般形のテンプレートも載せています。単調性の説明はないので、上の記事とあわせて読んでください。
  • 尺取り法の実装で嵌ったあの日の涙を数え切れないあなたにお送りする、尺取り法実装の † ソウル † です。(ngtkana、Qiita)
    • 尺取り法の難しさを「左右の端を動かしたときの状態の更新」と「どう動かすか」に分けて、和が KK 以下・KK より大きい区間の数え上げ、最大長・最小長などを C# で書き分けています。要素が 00 以上であることを「大事な仮定」として明示しています。図はありません。
    • コードにそのままでは誤答になる誤りがあります。和が KK 以下の区間を数えるコードで、左端を進めるときに sum += a[l++] となっている箇所(正しくは -=)、最小長のコードで ans を 00 で初期化したまま Math.Min を取っている箇所などです。
  • 二分探索のリンク集:左端ごとの右端の境目は、累積和の上の二分探索でも求められます。尺取り法より log⁡\log が付きますが、考えやすいこともあります。
  • 累積和・いもす法のリンク集:区間の和の判定や、区間内の特定の要素の個数を O(1)O(1) で求めるのに使います。
  • スライド最小値のリンク集:両端が単調に動く区間の最小値・最大値を deque で求める手法で、尺取り法と組み合わせてよく使われます。

尺取り法を扱う講座はまだありません。競技プログラミング基本用語集の 6.2「区間」(半開区間の表記)、6.3「部分列,部分配列(連続部分列)」、6.6「単調性」の節で、関連する用語を確認できます。

日本語版・英語版の Wikipedia には、尺取り法(two pointers)の記事はありません。

  • Two Pointers(USACO Guide)
    • 両端から寄せる型(ソートした配列で和が xx になる 2 要素を探す CSES Sum of Two Values)と、同じ向きに動かす型(Codeforces 279B Books)を、表やアニメーションで説明しています。C++・Java・Python のコードと、12 問の問題一覧があります。
    • 末尾の小テストは、two pointers を「2 つの添字の組を探す手法」とする選択肢だけを正解にしていて、本文の同じ向きに動かす型と噛み合いません。
  • Competitive Programmer’s Handbook(Antti Laaksonen、PDF)
    • 8 章「Amortized analysis」の 8.1 節「Two pointers method」で、正の整数の列で和がちょうど xx の区間を探す問題と、2SUM(和が xx になる 2 要素)を図で説明しています。コードはありません。8.3 節はスライド最小値です。
  • Two Pointers Method(Codeforces EDU)
    • ITMO Academy の講座の 1 レッスンです。中身を見るには Codeforces へのログインが必要です。

左端を 1 つ進めるたびに右端を伸ばせるだけ伸ばす、という基本の形の問題です。

ソートした配列の上で 2 本のポインタを動かす形の問題です。

  • ABC481 E - Most Brilliant Starry Sky
    • 星を偏角の順に並べ、偏角に 2π2\pi を足した写しを後ろにつなげた列の上で、偏角の幅が π\pi 未満の区間を尺取り法で求めています。円環の上の尺取り法の例です。

ABC481 E - Most Brilliant Starry Sky

xyxy 平面上に NN 個の星 (Xi,Yi)(X_i, Y_i) があります。原点を通り、どの星も通らない直線を 1 本引き、分けられた 2 つの領域のどちらかを選びます。選んだ領域に含まれる星の個数の最大値を求める問題です。

どの 2 個の星も原点と一直線上に並ぶことはありません。TT 個のテストケースに答えます(NN の総和は 2×1052 \times 10^5 以下、∣Xi∣,∣Yi∣≤109|X_i|, |Y_i| \le 10^9)。

原点を通る直線で分けた一方の領域は、偏角(原点から見た向きの角度)が長さ π\pi の開区間 (α,α+π)(\alpha, \alpha + \pi) に入る点の集まりです。よって、偏角が長さ π\pi の区間に入る星の個数の最大値を求めればよいです。

ある領域 (α,α+π)(\alpha, \alpha + \pi) が星を含むとき、含まれる星のうち偏角が最小のものを θ\theta とします。含まれる星の偏角はどれも θ\theta 以上 α+π\alpha + \pi 未満で、α<θ\alpha < \theta なので、どれも [θ,θ+π)[\theta, \theta + \pi) に入ります。逆に、偏角が [θ,θ+π)[\theta, \theta + \pi) に入る星は、α\alpha を θ\theta より少しだけ小さくした領域でちょうど全部含められます。偏角がちょうど θ+π\theta + \pi の星はないので(原点と一直線上に並ばないため)、α\alpha を θ\theta に十分近くすれば余計な星は入りません。

したがって、各星 ii について、偏角が [θi,θi+π)[\theta_i, \theta_i + \pi) に入る星を数え、その最大値が答えです。

星を偏角の順に並べます。偏角は一周すると元に戻るので、偏角に 2π2\pi を足した写しを後ろにつなげた長さ 2N2N の列を作ります。この列で、各 ll (0≤l<N)(0 \le l < N) について、偏角が θl+π\theta_l + \pi 未満である範囲の右端 rr を求めると、r−lr - l が [θl,θl+π)[\theta_l, \theta_l + \pi) に入る星の個数です。ll が増えると rr も減らないので、尺取り法で全体 O(N)O(N) で求まります。

計算量は、偏角ソートの O(Nlog⁡N)O(N \log N) です。

偏角は atan2 などの浮動小数点数で求めると、偏角の近い星の比較で誤差が出るおそれがあります。外積を使って比べると、整数だけで正確に比べられます。座標の絶対値は 10910^9 以下なので、外積は 64 bit 整数に収まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/geometry/angle.hpp"
#include "shogo-library/utility/container_func.hpp"
#include "shogo-library/utility/two-pointers.hpp"
void solve() {
LL(N);
vec<Angle<ll>> A(N);
for (auto &a : A)
std::cin >> a;
sort(A);
rep(i, N) A.push_back(A[i].next_turn());
auto right = two_pointers(2 * N, [&](ll l, ll r) { return A[r] < A[l].opposite(); });
ll ans = 0;
rep(l, N)
chmax(ans, right[l] - l);
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

Angle<ll> はベクトル (x,y)(x, y) の偏角を表す型で、周回数 turn を持ち、偏角 2π⋅turn+[0,2π)2\pi \cdot \mathrm{turn} + [0, 2\pi) として外積で比べます。next_turn() は偏角に 2π2\pi を足したもの、opposite() は π\pi を足したもの(逆向きのベクトル)です。

sort(A) で偏角の順に並べ、next_turn() で 2π2\pi を足した写しを後ろにつなげます。two_pointers(n, can_add) は、各 l について、区間 [l, r) に r を加えてよい(can_add(l, r) が真)間だけ r を伸ばし、伸ばし終えた r を並べた列を返します。ここでは「A[r] の偏角が A[l] の偏角 +π+ \pi 未満」を条件にしています。

使用ライブラリ:cpp_include@4b58304