概要

\(N\) 個の銘柄それぞれについて、隣接する日の株価の差の絶対値の合計（変動幅）を計算し、変動幅が最大の銘柄番号を求める問題です。

考察

問題の理解

「変動幅」とは、株価が日ごとにどれだけ上下したかの合計です。例えば、ある銘柄の株価が \([100, 130, 110, 150]\) の4日間だった場合、変動幅は次のように計算します：

\[|130 - 100| + |110 - 130| + |150 - 110| = 30 + 20 + 40 = 90\]

アプローチ

この問題は素直にシミュレーションするだけで解けます。

• 各銘柄について変動幅を計算する → \(O(M)\)
• \(N\) 個の銘柄すべてに対して行う → \(O(NM)\)

制約が \(N \leq 100\)、\(M \leq 100\) と小さいので、\(O(NM) = O(10000)\) 程度の計算量であり、特別な工夫は不要です。TLE や WA を心配する必要はなく、定義通りに計算すれば正解できます。

同点の処理

変動幅が最大の銘柄が複数ある場合は「番号が最も小さいもの」を出力します。銘柄 \(1\) から順に見ていき、厳密に大きい場合のみ最大値を更新する（> を使う）ことで、同点のときは先に見つけた（＝番号が小さい）銘柄が保持されます。

アルゴリズム

1. \(N\) と \(M\) を読み込む。
2. 変動幅の最大値 best_val を \(-1\) で、対応する銘柄番号 best_idx を \(0\) で初期化する。
3. 銘柄 \(i = 1, 2, \ldots, N\) について：
   • 株価データ \(A_{i,1}, A_{i,2}, \ldots, A_{i,M}\) を読み込む。
   • 変動幅 \(v = \sum_{j=1}^{M-1} |A_{i,j+1} - A_{i,j}|\) を計算する。
   • もし \(v > \text{best\_val}\) ならば、best_val を \(v\) に、best_idx を \(i\) に更新する。
4. best_idx を出力する。

計算量

• 時間計算量: \(O(NM)\)（各銘柄について \(M-1\) 回の差分計算を \(N\) 銘柄分行う）
• 空間計算量: \(O(M)\)（1銘柄分の株価データを保持するだけで十分）

実装のポイント

• 更新条件は > （厳密な不等号）にする：>= にしてしまうと、同点の場合に番号が大きい方に更新されてしまい、「番号が最も小さいもの」という条件を満たせません。

• 銘柄番号は 1-indexed：コード中のループ変数 i は 0 から始まるため、銘柄番号として出力する際は i + 1 とする必要があります。

• 全銘柄のデータを配列に保存する必要はなく、1銘柄ずつ読み込んで変動幅を計算・比較すれば十分です。これにより空間計算量を抑えられます。

  ソースコード

N, M = map(int, input().split())
best_idx = 0
best_val = -1
for i in range(N):
    A = list(map(int, input().split()))
    v = sum(abs(A[j+1] - A[j]) for j in range(M-1))
    if v > best_val:
        best_val = v
        best_idx = i + 1
print(best_idx)

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