概要

配列の中から、すべての要素が指定範囲 \([L, R]\) 内にある連続部分列の最大長を求める問題です。

考察

重要な気づき

この問題のポイントは、「連続する」という条件です。区間内のすべての木が糖度条件を満たす必要があるため、1本でも条件を満たさない木があると、そこで区間は途切れます。

素朴なアプローチとその問題点

素朴に考えると、すべての区間 \([l, r]\) を列挙し、各区間内の要素がすべて条件を満たすかチェックする方法があります。

• 区間の候補数: \(O(N^2)\) 通り
• 各区間のチェック: \(O(N)\)
• 合計: \(O(N^3)\)

\(N = 2 \times 10^5\) の場合、これでは到底間に合いません。

解決方法

配列を左から右へ1回走査しながら、現在の連続して条件を満たす区間の長さを追跡すればよいです。

具体例で考えてみましょう： - \(L = 5, R = 10\) - \(T = [6, 8, 7, 3, 9, 10, 8]\)

\(i\)	\(T_i\)	条件を満たす？	current_length	max_length
0	6	○	1	1
1	8	○	2	2
2	7	○	3	3
3	3	×	0	3
4	9	○	1	3
5	10	○	2	3
6	8	○	3	3

答えは \(3\) となります。

アルゴリズム

1. current_length（現在の連続区間の長さ）と max_length（最大の長さ）を \(0\) で初期化
2. 配列を左から順に走査
3. 各要素 \(T_i\) について：
   • \(L \leq T_i \leq R\) なら、current_length を \(1\) 増やし、max_length を更新
   • そうでなければ、current_length を \(0\) にリセット（区間が途切れた）
4. 最終的な max_length を出力

このアルゴリズムは「ランレングス的な考え方」とも呼ばれ、連続する同じ性質を持つ要素をまとめて処理する典型的なテクニックです。

計算量

• 時間計算量: \(O(N)\)
  • 配列を1回走査するだけ
• 空間計算量: \(O(N)\)
  • 入力配列 \(T\) の格納に必要（追加で使う変数は \(O(1)\)）

実装のポイント

• 条件を満たさない要素に出会ったとき、current_length を \(0\) にリセットすることを忘れない

• max_length の更新は、条件を満たす要素を見つけたときのみ行えばよい

• Python では L <= T[i] <= R という書き方で範囲チェックを簡潔に書ける

  ソースコード

def solve():
    N, L, R = map(int, input().split())
    T = list(map(int, input().split()))
    
    max_length = 0
    current_length = 0
    
    for i in range(N):
        if L <= T[i] <= R:
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            current_length = 0
    
    print(max_length)

solve()

---

この解説は claude4.5opus によって生成されました。