概要

この問題は、与えられた \(N\) 個の気温データのうち、隣り合うデータの差の絶対値が基準値 \(K\) 以上となる箇所がいくつあるかを数える問題です。

考察

この問題を解くための重要なポイントは、「急変」の判定は隣り合う 2 つのチェックポイント間だけで完結しているという点です。

チェックポイント \(i\) で急変が起きたかどうかを判定するには、現在の気温 \(T_i\) と 1 つ前の気温 \(T_{i-1}\) の情報さえあれば十分です。したがって、以下の手順で進めることで正解を導けます。

1. チェックポイント \(2\) から順に、1 つ前のチェックポイントとの気温差を計算する。
2. その差の絶対値が \(K\) 以上であるかを確認する。
3. 条件を満たしていれば、カウントを 1 増やす。

制約を確認すると、チェックポイントの数 \(N\) は最大 \(10^5\) です。1 回のループで全てのチェックポイントを確認する \(O(N)\) のアルゴリズムであれば、制限時間内に十分に間に合います。

アルゴリズム

1. 入力から \(N, K\) および気温のリスト \(T\) を受け取ります。
2. 急変の回数を記録する変数 ans を \(0\) で初期化します。
3. \(i = 1, 2, \dots, N-1\) について、以下の処理を繰り返します（\(0\) オリジンのインデックスの場合）。
   • \(|T[i] - T[i-1]|\) を計算します。
   • もしその値が \(K\) 以上であれば、ans に \(1\) を加算します。
4. 最終的な ans の値を出力します。

※絶対値の計算には、多くのプログラミング言語で用意されている abs 関数を使用すると便利です。

計算量

• 時間計算量: \(O(N)\)
  • 全てのチェックポイントを 1 度ずつ確認するため、入力サイズ \(N\) に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された気温をリストに保存する場合、\(N\) 個分のメモリが必要になります。
  • （工夫次第で、入力を 1 つずつ読み込みながら処理すれば \(O(1)\) に抑えることも可能です。）

実装のポイント

• インデックスの範囲: チェックポイント \(1\) には「直前のチェックポイント」が存在しないため、ループは \(2\) 番目の要素（インデックス \(1\)）から開始する必要があります。

• 大きな入力への対応: Python の場合、input() を繰り返すと実行時間が長くなることがあります。今回の \(N=10^5\) 程度であれば、sys.stdin.read().split() などを用いて一括で読み込むことで、高速に入力を処理できます。

• 絶対値の判定: \(|T_i - T_{i-1}| \ge K\) という条件は、プログラム上では abs(T[i] - T[i-1]) >= K と書くことができます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: チェックポイントの数, K: 基準値
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 気温のリスト T (T_1, T_2, ..., T_N)
    T = list(map(int, input_data[2:]))
    
    ans = 0
    # チェックポイント 2 から N まで順に確認する
    for i in range(1, N):
        # 直前のチェックポイントとの気温差の絶対値が K 以上か判定
        if abs(T[i] - T[i-1]) >= K:
            ans += 1
            
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

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