解説

問題の概要

\(N\) 枚の板が位置 \(A_1 < A_2 < \cdots < A_N\) に立っている。隣り合う板の間には \(N - 1\) 個の隙間があり、左から \(i\) 番目の隙間の幅は \(A_{i+1} - A_i\) である。最も幅の広い隙間の番号を求める。同じ最大幅を持つ隙間が複数ある場合は、最も左のものを答える。

アルゴリズム

隙間を左から順に 1 回だけ走査する。現在までに見つかった最大の隙間幅 best と、その隙間の番号 ans を保持する。

• 初期値として、1 番目の隙間の幅 \(A_2 - A_1\) を best、\(1\) を ans とする。
• \(i = 2, 3, \ldots, N - 1\) について、隙間 \(i\) の幅 \(w = A_{i+1} - A_i\) を計算し、\(w > \text{best}\) ならば best と ans を更新する。

タイブレークについて

更新条件を「厳密に大きい (\(>\))」とすることで、同じ幅の隙間が後に現れても更新されない。走査は左から右へ行うため、最大幅を最初に達成した（＝最も左の）隙間の番号がそのまま残る。これは問題文の「最も広い隙間が複数ある場合は、そのうち最も左のものを答えてください」という条件に正確に対応する。

正しさの証明

補題: \(i\) 番目の隙間を処理した直後の時点で、ans は \(1\) 番目から \(i\) 番目までの隙間のうち、最大の幅を持つ最も左の隙間の番号であり、best はその幅に等しい。

証明（帰納法）: \(i = 1\) のとき、ans = 1、best = A_2 - A_1 であり、考慮対象は隙間 1 のみなので明らかに成立する。\(i - 1\) までで成立すると仮定する。隙間 \(i\) の幅を \(w\) とする。

• \(w > \text{best}\) の場合: 隙間 \(i\) は隙間 \(1, \ldots, i - 1\) のすべてより厳密に広いので、\(1\) から \(i\) の中で最大幅を持つ最も左の隙間は \(i\) である。更新により ans = i、best = w となり成立。
• \(w \leq \text{best}\) の場合: 隙間 \(i\) は最大幅を持たないか、持っても最左ではないので、答えは変わらない。更新しないため、帰納法の仮定より成立。

よって \(i = N - 1\) まで処理した時点で、ans は全 \(N - 1\) 個の隙間のうち最大幅を持つ最も左のものの番号である。\(\blacksquare\)

計算量

• 時間計算量: \(O(N)\)（各隙間を 1 回ずつ調べる）
• 空間計算量: 入力配列を除けば \(O(1)\) の補助空間。入力全体を配列に保持する実装では \(O(N)\)。なお、入力をストリーム的に読み「直前の板の位置」だけを保持すれば真の \(O(1)\) 空間でも実装可能であるが、\(N \leq 100\) なので不要である。

\(N \leq 100\)、\(A_i \leq 10000\) という制約のもと、このアルゴリズムは十分高速である。