概要

各銘柄ごとに、日ごとの株価の「隣り合う差の絶対値の総和（変動幅）」を計算し、その値が最大となる銘柄番号（同率なら最小番号）を求めます。

考察

銘柄 \(i\) の変動幅は定義通り
\(\displaystyle \sum_{j=1}^{M-1} |A_{i,j+1}-A_{i,j}|\)
を計算すればよいです。つまり、各行（銘柄）の株価列を左から順に見ていき、隣接差の絶対値を足し合わせるだけです。

この問題で注意する点は「最大値が同じなら番号が小さい方」を選ぶことです。
そこで、最大の変動幅 best_val を更新するときは「\(>\)（より大きい）」のときだけ更新し、「\(=\)（同じ）」のときは更新しないようにします。そうすると先に出てきた（番号が小さい）銘柄が自動的に残ります。

素朴に言っても、全データは最大でも \(N \times M \le 10000\) 個なので、全て計算しても十分高速です。むしろ、全銘柄を比較するために「変動幅を正しく合計する」「同率処理を間違えない」ことがWA回避のポイントになります。

例：株価が [10, 13, 8] なら変動幅は
\(|13-10| + |8-13| = 3 + 5 = 8\) です。

アルゴリズム

1. best_val = -1, best_idx = 1 で初期化する。
2. 銘柄 \(i=1..N\) について以下を行う：
   • 株価列 \(A_{i,1..M}\) を読み込む。
   • s = 0 とし、\(j=1..M-1\) で s += |A_{i,j+1} - A_{i,j}| を加算して変動幅 s を求める。
   • s > best_val なら best_val = s, best_idx = i に更新する。
3. best_idx を出力する。
   （同率の場合は更新しないため、最小番号が残る）

計算量

• 時間計算量: \(O(NM)\)（全銘柄の全日数について隣接差を1回ずつ計算）
• 空間計算量: \(O(M)\)（1銘柄分の株価を一時的に保持する分）

実装のポイント

• 同率のときに最小番号を選ぶため、更新条件は >= ではなく > にする。

• abs(row[j + 1] - row[j]) のように隣接差の絶対値を確実に取る。

• 入力は sys.stdin.read() でまとめて読み、イテレータで順に取り出すと簡潔に実装できます。

  ソースコード

import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(map(int, data))
    N = next(it)
    M = next(it)

    best_idx = 1
    best_val = -1

    for i in range(1, N + 1):
        row = [next(it) for _ in range(M)]
        s = 0
        for j in range(M - 1):
            s += abs(row[j + 1] - row[j])
        if s > best_val:
            best_val = s
            best_idx = i

    print(best_idx)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。