【C#アルゴリズム】しゃくとり法

はじめに

paiza　でしゃくとり法を用いる問題が出てきたのでそれについてまとめます。
累積和の応用アルゴリズムとなるため、累積和に関する記事もあわせて読んでみてください。

https://zenn.dev/student_blog/articles/7fc669f848841d

しゃくとり法の概要

しゃくとり法（尺取り法）は、連続する区間（部分列や部分区間）を扱う問題において効率的に解を求めるためのアルゴリズムです。主に累積和や条件を満たす部分区間の探索に使われます。

• 区間を動かす考え方
  区間の始点と終点をそれぞれ独立に動かしながら、条件を満たす範囲を探索します。

• スライドのイメージ
  区間の終点を増やしながら条件を満たすように拡張し、条件を満たさなくなったら始点を動かして調整します。（個人的には追いかけっこのイメージです）

数式的な説明

問題によって異なりますが、例えば以下のような条件を満たす部分区間を求める場合を考えます。

1. 配列 $a = \{a_1, a_2, \dots, a_n\}$ が与えられる。
2. 部分区間 $[l, r)$ について、区間内の要素の和が $S$ 以下になるような最大の長さを求める。

アルゴリズムの手順

1. left を固定し、条件を満たす間 right を 1 ずつ進めていき、right がそれ以上進めなくなったとき、right - left とすることでそれまでの条件を満たす区間の数を求めることができる
2. right がこれ以上右に進めなくなったとき、left を 1 進め、また 1 に戻る
3. ただし、left == right となったときは、right を 1 進める

• sum から A[left] を引くことを忘れない事。ただし、left == right となったときは、sum に A[left] が足されていないので引く必要はない。（僕は一度間違えました。）

C#での実装例

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int K = 15;
        int[] A = { 1, 5, 9, 1, 20, 5, 3, 6, 5, 4 }; // 配列 A
        int sum = 0; // 現在の区間の和
        int ans = 0; // 条件を満たす部分区間の個数
        int right = 0; // 区間の終点を示すポインタ
        for (int left = 0; left < A.Length; left++) // 区間の始点をループ
        {
            // 区間を広げられる限り広げる
            while (right < A.Length && sum + A[right] <= K)
            {
                sum += A[right];
                right++;
            }
            
            // 始点と終点が一致している場合の処理
            if (left == right)
            {
                right++;
            }
            else
            {
                // 条件を満たす部分区間の個数を加算
                ans += right - left;
            
                // 区間の和から始点を引く
                sum -= A[left];
            }
        }
    }
}

応用例

1. 条件を満たす長さの最大値を求める場合
2. データ分析
   • 温度センサーの値が許容範囲を超える連続時間を特定。
   • 価格変動が一定割合以下の安定区間を発見。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

累積和に関する記事
https://zenn.dev/student_blog/articles/7fc669f848841d