概要

\(N\) 個の地点の標高が与えられたとき、隣り合う地点の標高が「前の地点 \(\leq\) 後の地点」という関係（広義単調増加）を保っている連続した区間のうち、最も長いものの地点数（長さ）を求める問題です。

考察

この問題で求めたいのは、「標高が一度も下がらずに続く最長の区間」です。

例えば、標高が [1, 2, 5, 3, 4] と並んでいる場合を考えます。 - 地点 1 から 3 までは 1 $\leq$ 2 $\leq$ 5 と増えているので、長さ 3 の登り坂です。 - 地点 3 から 4 に移動すると 5 > 3 と標高が下がるため、ここで一旦登り坂は途切れます。 - 地点 4 から 5 までは 3 $\leq$ 4 と増えているので、長さ 2 の登り坂です。 この中で最大なのは長さ 3 となります。

このように、前から順番に標高を見ていき、「今の登り坂がどこまで続いているか」を数えていけば良さそうです。

なぜ全区間を調べなくて良いのか

すべての \(l\)（始点）と \(r\)（終点）の組み合わせを調べようとすると、組み合わせの数はおよそ \(N^2 / 2\) 通りになります。\(N = 10^5\) の場合、約 50 億回の計算が必要になり、制限時間内に終わりません。 しかし、標高が下がった瞬間に「それまでの登り坂」は確定し、次の登り坂は「下がった後の地点」から新しく数え始めればよいため、配列を先頭から 1回スキャンするだけ（\(O(N)\)） で解くことができます。

アルゴリズム

1. 現在の登り坂の長さを保持する変数 current_len を 1 に、これまでの最大長を保持する変数 max_len を 1 に初期化します。
2. 地点 \(i\) と地点 \(i+1\) を \(i = 1\) から \(N-1\) まで順番に比較します。
   • もし \(A_i \leq A_{i+1}\) なら、登り坂が継続しているので current_len を 1 増やします。
   • もし \(A_i > A_{i+1}\) なら、登り坂が途切れたことになります。
     • 現在の current_len と max_len を比較し、大きい方で max_len を更新します。
     • current_len を 1（新しい登り坂の始点）にリセットします。
3. すべての地点を見終わった後、最後の登り坂の長さが最大である可能性を考慮し、再度 max_len を更新します。
4. max_len を出力します。

計算量

• 時間計算量: \(O(N)\)
  • リストを 1 回だけ先頭から末尾まで走査するため、地点の数 \(N\) に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の標高をリストに格納するために使用します。

実装のポイント

• 境界条件の処理: \(N=1\) の場合、ループが実行されませんが、初期値が 1 なので正しく 1 が出力されます。

• ループ後の更新: 標高が最後まで上がり続けた場合、ループ内の else（リセット処理）が通りません。そのため、ループが終わった直後にもう一度 max_len の更新処理を行う必要があります。

• 高速な入力: Python で \(N=10^5\) 規模の入力を扱う場合、input() を繰り返すよりも sys.stdin.read().split() などで一括で取得する方が実行時間を短縮できます。

  ソースコード

import sys

def main():
    # 入力を一括で取得し、分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    # a_1 から a_n までの標高をリストに格納
    a = list(map(int, input_data[1:]))
    
    # 地点が1つしかない場合は、登り坂の長さは1
    if n == 1:
        print(1)
        return
    
    max_len = 1
    current_len = 1
    
    # 隣り合う地点の標高を比較し、広義単調増加（非減少）であるかを確認
    for i in range(n - 1):
        if a[i] <= a[i+1]:
            current_len += 1
        else:
            # 増加が途切れたら、現在の長さを最大値と比較しリセット
            if current_len > max_len:
                max_len = current_len
            current_len = 1
            
    # 最後の区間の長さを確認
    if current_len > max_len:
        max_len = current_len
        
    print(max_len)

if __name__ == '__main__':
    main()

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