概要

各村人の畑の面積を計算し、最大の面積を持つ村人の番号を求めます。同じ最大面積の村人が複数いる場合は、最も小さい番号を選びます。

考察

長方形の面積は「縦の長さ × 横の長さ」なので、村人 \(i\) の畑の面積は \(A_i \times B_i\) です。

\(N \leq 100\) と小さいため、すべての畑の面積を調べる素朴な方法で十分間に合います。高速な探索や並べ替えは必要ありません。

注意するのは、最大面積が同じ場合は、番号が最も小さい村人を選ぶという条件です。最大面積であることだけを確認して適当な村人を選ぶと、誤答になる可能性があります。

そこで、村人の番号順に面積をリストへ保存し、最大値が最初に現れる位置を探します。Python の list.index() は、指定した値が最初に現れる位置を返すため、この条件をそのまま満たせます。

例えば、面積のリストが [12, 20, 20, 15] の場合、最大面積は \(20\) です。最初に現れるのは村人 \(2\) の位置なので、答えは \(2\) となります。

アルゴリズム

1. 村人の人数 \(N\) を読み込みます。
2. 空のリスト areas を用意します。
3. 村人の番号順に \(A_i, B_i\) を読み込み、面積 \(A_i \times B_i\) を areas に追加します。
4. max(areas) で最大面積を求めます。
5. areas.index(max(areas)) で、最大面積が最初に現れる位置を求めます。
6. リストの位置は \(0\) 始まり、村人の番号は \(1\) 始まりなので、求めた位置に \(1\) を加えて出力します。

面積は番号順に保存されているため、最大値が最初に現れる位置を選べば、最大面積を持つ村人のうち最も小さい番号が得られます。

計算量

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

面積のリスト作成、max() による最大値の探索、index() による位置の探索は、それぞれ \(O(N)\) です。これらを順に行うので、全体でも \(O(N)\) となります。

また、\(N\) 個の面積をリストに保存するため、空間計算量は \(O(N)\) です。

実装のポイント

• areas.index() は、同じ値が複数ある場合に最初の位置を返します。同率の場合の処理を別に書く必要はありません。

• 出力時の + 1 を忘れないようにしましょう。

• \(N \geq 1\) が保証されているため、areas が空になることはなく、max(areas) を安全に使用できます。

  ソースコード

# 問題文から独立に実装: 面積のリストを作り、最大値の最初の位置
n = int(input())
areas = []
for _ in range(n):
    a, b = map(int, input().split())
    areas.append(a * b)
print(areas.index(max(areas)) + 1)

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