概要

焼き上がるまでの時間 \(A_i\) が最も小さい肉の番号を求めます。同じ最小時間の肉が複数ある場合は、最も小さい番号を答えます。

考察

すべての肉を同時に網に乗せるため、最初に焼き上がるのは \(A_i\) が最小の肉です。時間の経過をシミュレーションする必要はなく、\(A_1, A_2, \ldots, A_N\) を順番に調べるだけで求められます。この素朴な走査で十分に高速です。

注意するのは、最小値が複数ある場合の扱いです。例えば、

\(A = (5, 2, 4, 2)\)

では、\(2\) 枚目と \(4\) 枚目が同時に焼き上がるので、答えは \(2\) です。

番号の小さい順に調べ、これまでの最小値より厳密に小さい値を見つけたときだけ答えを更新すれば、同じ最小値を持つ肉の中で最小の番号が残ります。

逆に、同じ値のときも更新すると、後に現れた大きい番号を選んでしまい、不正解になります。

アルゴリズム

次の \(2\) つの変数を管理します。

• best：これまでに調べた肉の最小の焼き上がり時間
• ans：その時間で焼き上がる肉のうち、最も小さい番号

処理は次のとおりです。

1. ans と best をそれぞれ -1 で初期化する。
2. 肉を \(1\) 枚目から \(N\) 枚目まで順番に調べる。
   • まだ答えが未設定、つまり ans == -1 なら、現在の肉を答えにする。
   • 現在の時間が best より小さければ、best と ans を更新する。
   • それ以外の場合は更新しない。
3. ans を出力する。

各時点で ans は、そこまでに調べた肉の中で最初に焼き上がる最小番号の肉を表します。したがって、すべて調べ終えたときの ans が求める答えです。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

提示コードでは入力をまとめて読み込み、data に保存するため、空間計算量は \(O(N)\) です。最小値を探す処理自体が使う追加の領域は \(O(1)\) です。

実装のポイント

• 更新条件は a < best とします。a <= best にすると、同じ時間の肉が現れたときに大きい番号で上書きされてしまいます。

• ans == -1 は、まだ肉を選んでいないことを表します。この条件により、最初の肉は必ず選ばれます。

• data[0] は肉の枚数 \(N\) であり、data[i] が \(i\) 枚目の時間です。range(1, n + 1) を使うことで、肉の番号をそのまま ans に保存できます。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    ans = -1
    best = -1
    for i in range(1, n + 1):
        a = int(data[i])
        if ans == -1 or a < best:
            best = a
            ans = i
    print(ans)

main()

---

この解説は gpt-6-astra-medium によって生成されました。