解説

方針

各村人 \(i\) の畑の面積は \(A_i \times B_i\) で求められます。\(i = 1, 2, \dots, N\) の順に面積を計算し、「現在までの最大面積」と「それを達成した村人の番号」を保持しながら走査します。

面積が厳密に現在の最大値より大きい場合にのみ答えを更新します。こうすることで、同じ最大面積を持つ村人が複数いた場合、先に現れた（＝番号が最も小さい）村人が保持され、タイブレークの条件「番号が最も小さい村人を答える」を自動的に満たします。

疑似コード

bestArea ← -1
best ← 0
for i = 1 to N:
    area ← A_i × B_i
    if area > bestArea:
        bestArea ← area
        best ← i
出力 best

正しさの証明

主張: アルゴリズム終了時、best は面積が最大の村人のうち番号が最小のものである。

証明: ループ不変式として「\(i\) 番目の村人を処理した直後、bestArea は \(A_1 B_1, \dots, A_i B_i\) の最大値であり、best はその最大値を達成する最小の番号である」が成り立つことを示す。

• 初期化: ループ開始前は空の集合に対する最大値として bestArea = -1 であり、\(A_i, B_i \geq 1\) より全ての面積は \(1\) 以上なので不変式は矛盾なく成立する。
• 維持: \(i\) 番目を処理するとき、\(A_i B_i > \text{bestArea}\) ならば \(i\) が新しい最大値を持つ唯一の番号なので best ← i と更新し不変式は保たれる。\(A_i B_i \leq \text{bestArea}\) ならば最大値は変わらず、\(A_i B_i = \text{bestArea}\) の場合でも既存の best の方が番号が小さい（\(i\) の方が後に処理される）ため更新しないことが正しい。
• 終了: \(i = N\) でループが終了したとき、不変式より best は全村人の中で面積が最大かつ番号が最小の村人である。

計算量

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