概要

\(N\) 本の木からなる果樹園において、すべての木の糖度が指定された範囲 \([L, R]\) に収まっているような「連続する区間」のうち、最も長いものの長さを求める問題です。

考察

この問題の核心は、「条件を満たさない木が現れた瞬間に、それまでの連続記録が途切れる」という点にあります。

例えば、糖度が [10, 12, 5, 11, 13] で、基準が 10 以上 15 以下の場合を考えてみます。 1. 10: 範囲内（長さ1） 2. 12: 範囲内（長さ2） 3. 5: 範囲外！（ここで連続が途切れる。長さは0にリセット） 4. 11: 範囲内（長さ1） 5. 13: 範囲内（長さ2）

このように、端から順番に木をチェックしていき、「条件を満たしている間はカウントを増やし、満たさなくなったらリセットする」という操作を繰り返すことで、すべての候補となる区間を漏れなく確認できます。

なぜ全探索ではいけないのか？

すべての区間 \([l, r]\) を力任せに調べようとすると、区間の組み合わせが約 \(\frac{N^2}{2}\) 通り存在します。\(N = 2 \times 10^5\) の場合、計算回数は約 \(2 \times 10^{10}\) 回となり、一般的な制限時間（2秒程度）には到底間に合いません。そのため、配列を一度走査するだけで答えが出る効率的なアルゴリズムが必要です。

アルゴリズム

「現在の連続した長さ」を保持する変数 cur_len と、「これまでの最大長」を保持する変数 max_len を用意します。

1. 木の糖度 \(T_i\) を左から順に \(1\) 本ずつ確認します。
2. もし \(L \leq T_i \leq R\) ならば：
   • 現在の連続長 cur_len に \(1\) を加えます。
   • max_len を max(max_len, cur_len) で更新します。
3. もし範囲外ならば：
   • 連続が途切れたため、cur_len を \(0\) にリセットします。
4. すべての木を確認し終えたあとの max_len が答えとなります。

この手法は、いわゆる「走査（スキャン）」や「貪欲法」に近い考え方で、非常に効率的です。

計算量

• 時間計算量: \(O(N)\) \(N\) 本の木を最初から最後まで一度だけ確認するため、木の本数に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\) 入力された \(N\) 個のデータをリスト（配列）として保持するためにメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで \(N=2 \times 10^5\) 規模の入力を処理する場合、input() を繰り返すよりも sys.stdin.read().split() を使って一括で読み込む方が実行時間を短縮できます。

• 初期値: 条件を満たす区間が一つもない場合、max_len の初期値を 0 にしておくことで、正しく 0 を出力できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してトークン化します。
    # 大量の入力を処理する場合、sys.stdin.read().split() は高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目の N (木の本数), L (糖度の下限), R (糖度の上限) を取得します。
    n = int(input_data[0])
    l = int(input_data[1])
    r = int(input_data[2])
    
    # 2行目の各木の糖度 T_i を整数に変換するイテレータを作成します。
    # input_data[3:3+n] により、T_1 から T_N までのトークンをスライスします。
    t_values = map(int, input_data[3:3+n])
    
    max_len = 0
    cur_len = 0
    
    # 各木の糖度を順番にチェックし、条件を満たす連続区間の長さを計算します。
    for val in t_values:
        if l <= val <= r:
            # 糖度が [L, R] の範囲内であれば、現在の連続長をインクリメントします。
            cur_len += 1
            # これまでの最大長を更新します。
            if cur_len > max_len:
                max_len = cur_len
        else:
            # 範囲外の糖度が見つかった場合、現在の連続長をリセットします。
            cur_len = 0
    
    # 条件を満たす連続区間の最大長を出力します。
    print(max_len)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。