概要

各銘柄の株価データから変動幅（隣接する日の株価の差の絶対値の合計）を計算し、変動幅が最大となる銘柄の番号を求める問題です。

考察

問題で求められているのは、各銘柄について隣接する日の株価の差の絶対値を合計した「変動幅」を計算し、その値が最大となる銘柄を特定することです。変動幅が同じ場合には番号が最小の銘柄を選択する必要があります。

この問題は単純に各銘柄の変動幅を計算して比較すればよいため、特別なアルゴリズムやデータ構造は必要ありません。制約条件が\(N, M \leq 100\)と小さいため、二重ループを使った素朴なアプローチでも十分に高速に計算できます。

アルゴリズム

1. 入力から銘柄数\(N\)と日数\(M\)を読み取る
2. 各銘柄\(i\) \((1 \leq i \leq N)\)について：
   • 株価データを読み取る
   • 変動幅\(\displaystyle\sum_{j=1}^{M-1} |A_{i,j+1} - A_{i,j}|\)を計算する
3. 計算した変動幅を比較し、最大値とその銘柄番号を記録する
4. 変動幅が同じ場合は番号が小さい方を優先する
5. 最終的に選択された銘柄番号を出力する

計算量

• 時間計算量: \(O(N \times M)\)
  • 各銘柄について\(M-1\)回の計算を行うため
• 空間計算量: \(O(N \times M)\)
  • 株価データをすべてメモリに保持するため

実装のポイント

• 変動幅の計算にはabs()関数を使って絶対値を取得する

• 最大値の初期値は-1、結果のインデックス初期値は-1に設定する

• 変動幅が同じ場合の処理を忘れずに実装する（elif variation == max_variationの部分）

• 入力データの読み取りはsys.stdin.read().splitlines()を使って効率的に行う

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n, m = map(int, data[0].split())
    max_variation = -1
    result_index = -1
    
    for i in range(1, n + 1):
        prices = list(map(int, data[i].split()))
        variation = 0
        for j in range(m - 1):
            variation += abs(prices[j + 1] - prices[j])
            
        if variation > max_variation:
            max_variation = variation
            result_index = i
        elif variation == max_variation:
            if result_index == -1 or i < result_index:
                result_index = i
                
    print(result_index)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。