AIで解説 AtCoder攻略　尺取り法

尺取り法ページの位置づけ

項目	内容
必修度	標準
学習目安	標準〜発展
前提	文法・ライブラリ
対象問題	27問（推定値あり27問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	1
標準	0〜799	14
標準〜発展	800〜1199	6
発展	1200以上	6
未算出	—	0

正の値が並ぶ配列で、条件を満たす最短区間を左端ごとに探します。右端を戻さない単調性が計算量を下げます。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

尺取り法の見分け方

配列の要素が正である
右端を伸ばすと合計が増える
各左端に対する最短の右端を求める

尺取り法の実装前チェック

右端を進める条件と止める条件を分ける
左端を進める前に答えを更新する
空区間と配列末尾を確認する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC143 D Triangles（公式解説）を解きます。三角形の2辺を固定すると、3辺目はソート済み配列の連続区間になります。二分探索で上限位置を求め、区間の個数を一括で数えます。

from bisect import bisect_left

N = int(input())
A = sorted(map(int, input().split()))
answer = 0
for i in range(N):
    for j in range(i + 1, N):
        limit = bisect_left(A, A[i] + A[j], j + 1)
        answer += limit - (j + 1)
print(answer)

ソートO(N log N)と、各(i,j)の二分探索O(log N)で全体O(N^2 log N)です。3重ループO(N^3)より改善します。

尺取り法の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC175 B Making Triangle	公式解説	3本の長さを全列挙し、相異なることと三角不等式を満たす組だけを数える。	-51
ABC395 C Shortest Duplicate Subarray	公式解説	Slide a window while maintaining frequencies to find the shortest subarray containing a duplicate.	36
ABC212 C Min Difference	公式解説	AとBをソートして2ポインタを進め、最も近い値の差を更新する。	205
ABC401 C K-bonacci	公式解説	公式Editorialの方針を sliding window linear recurrence として整理する。	209
ABC326 C Peak	公式解説	Sort visitor counts and find the maximum number inside an interval of width M.	274

次に解く

問題	公式解説	出題意図	difficulty
ABC210 C Colorful Candies	公式解説	Slide a K-length window, updating color frequencies to maximize the number of distinct candies.	357
ABC267 C Index × A(Continuous ver.)	公式解説	長さMの連続区間について添字付き和を累積和で計算し最大値を求める。	524
ABC446 D G. Max Straight	公式解説	Sort lengths and maintain the longest consecutive window with a two-pointer scan.	550
ABC189 C Mandarin Orange	公式解説	Use a monotonic stack to evaluate the minimum of every subarray and maximize minimum times length.	565
ABC450 D G. Minimize Range	公式解説	Sort endpoints and minimize the range with a sliding window.	647

挑戦問題

問題	公式解説	出題意図	difficulty
ABC466 C Count Close Pairs	公式解説	Sort points and count pairs within the close-distance threshold.	658
ABC302 D G. Impartial Gift	公式解説	Sort both lists and maximize a+b under the difference bound with a moving pointer.	682
ABC143 D Triangles	公式解説	最長2辺を固定し、三角不等式を満たす3辺目の範囲をソート済み配列の二分探索で数える。	686
ABC265 D G. Iroha and Haiku (New ABC Edition)	公式解説	正数列の累積和上で、P,Q,Rの区間差を二ポインタまたは二分探索で探す。	727
ABC229 D G. Longest X	公式解説	窓内のドット数をK以下に保つ二ポインタで、Xに変えられる最長区間を求める。	745