概要

各銘柄の株価データから、隣接する日同士の株価の差の絶対値の合計（変動幅）を計算し、最も変動幅が大きい銘柄の番号を求めます。複数ある場合は最も番号が小さいものを選択します。

考察

この問題では、各銘柄ごとに株価の時系列データが与えられ、隣り合う日同士の株価の差の絶対値の和を計算する必要があります。これは単純に前から順に処理していくことで求めることができます。

例えば銘柄 \(i\) の株価が \([100, 120, 110]\) のとき、変動幅は \(|120 - 100| + |110 - 120| = 20 + 10 = 30\) となります。

各銘柄の変動幅を計算して最大値を更新しながら保持することで、最後に最も大きな変動幅を持つ銘柄を特定できます。また、同じ変動幅の場合は番号が小さい方を選ぶ必要があるため、番号順に処理して初めて最大値を超えるときだけ更新するようにすれば自然に満たされます。

素朴な方法でも特に計算量的に問題はなく、全銘柄に対して隣接項の差分を取るだけで十分高速に動作します。

アルゴリズム

1. 各銘柄について以下を行う：
   • 株価データを受け取る。
   • 隣接する日同士の株価の差の絶対値を足し合わせて変動幅を計算する。
2. 変動幅の最大値とそのときの銘柄番号を記録しておく。
3. 新たな銘柄の変動幅がこれまでの最大値より大きければ更新する。
4. 最後に記録された銘柄番号を出力する。

計算量

• 時間計算量: \(O(N \times M)\)
  各銘柄について \(M-1\) 回の減算と絶対値計算を行うため、全体で \(N(M-1)\) 回程度の演算となる。
• 空間計算量: \(O(M)\)
  各銘柄の株価リストを一時的に保存するために \(M\) 個分の配列が必要。

実装のポイント

• volatility の初期化は各銘柄ごとに行う。

• 最大値比較時に初めて超えた場合のみ銘柄番号を更新することで、「複数ある場合は番号が小さい方」の条件が自動的に満たされる。

• 入力は一行ずつ読み込んで処理すれば、すべてを同時にメモリに持つ必要がないため効率的。

  ソースコード

N, M = map(int, input().split())
max_volatility = -1
result_index = -1

for i in range(N):
    prices = list(map(int, input().split()))
    volatility = 0
    for j in range(M - 1):
        volatility += abs(prices[j + 1] - prices[j])
    
    if volatility > max_volatility:
        max_volatility = volatility
        result_index = i + 1

print(result_index)

この解説は qwen3-coder-480b によって生成されました。