解説

問題の要約

\(N\) 枚の肉があり、\(i\) 枚目は \(A_i\) 秒後に焼き上がる。最初に焼き上がる肉(=\(A_i\) が最小の肉)の番号を答える。最小値が複数ある場合は最も小さい番号を答える。

アルゴリズム

\(A_1, A_2, \ldots, A_N\) を順番に見ていき、「今までに見た中での最小値」と「その最小値を持つ肉の番号」を保持する。

\(i\) 枚目の肉を見たとき、\(A_i\) が現在の最小値より真に小さい場合のみ最小値と番号を更新する。\(A_i\) が現在の最小値と等しい場合は更新しない。これにより、最小値が複数ある場合には自然と最も小さい番号が残る(タイブレーク)。

擬似コード:

best ← 未定義
ans ← 未定義
for i = 1 to N:
    if ans が未定義 or A_i < best:
        best ← A_i
        ans ← i
print ans

なお、入力を配列に保存する必要はなく、\(1\) 要素ずつ読みながら処理できる。

正しさの証明

主張: ループの \(i\) 回目の反復が終了した時点で、ans は \(A_1, \ldots, A_i\) の中で最小値を持つ添字のうち最小のものであり、best はその最小値である。

証明(帰納法):

• 基底(\(i = 1\)): ans が未定義なので条件が満たされ、best ← A_1、ans ← 1 が代入される。これは主張を満たす。
• 帰納ステップ: \(i - 1\) 回目終了時点で主張が成り立つと仮定する。\(i\) 回目の反復では:
  • \(A_i < best\) の場合: \(A_1, \ldots, A_{i-1}\) の最小値は \(best\) であり、\(A_i\) はそれより小さいので、\(A_1, \ldots, A_i\) の最小値は \(A_i\) で、その値を持つ添字は \(i\) のみである。best ← A_i、ans ← i と更新されるので主張を満たす。
  • \(A_i \geq best\) の場合: \(A_1, \ldots, A_i\) の最小値は \(A_1, \ldots, A_{i-1}\) の最小値 \(best\) のままであり、最小値を持つ最小の添字も変わらない(\(A_i = best\) の場合でも \(i\) は既存の最小添字より大きいので、最小添字は変わらない)。更新しないので主張を満たす。

よって \(i = N\) 回終了時点で、ans は \(A_1, \ldots, A_N\) 全体で最小値を持つ最小の添字であり、これはまさに求める答えである。\(\blacksquare\)

計算量

• 時間計算量: \(O(N)\)（入力の読み込みを含む）。
• 空間計算量: C++ は \(O(1)\)、Python は \(O(N)\)。入力・出力として保持する配列や文字列も含む。