概要

各村人の畑の面積 \(A_i \times B_i\) を計算し、面積が最大となる村人の番号を求めます。同じ最大面積の村人が複数いる場合は、最も小さい番号を選びます。

考察

長方形の面積は「縦の長さ \(\times\) 横の長さ」で求められます。すべての村人について面積を計算し、これまでの最大面積と比較すれば答えが分かります。

この問題は \(N \leq 100\) なので、全員を順番に調べる素朴な方法で十分に間に合います。高速な探索や並べ替えは必要ありません。

注意するのは、面積が同じ場合の扱いです。村人を番号の小さい順に調べ、現在の最大面積よりも大きいときだけ答えを更新します。これにより、同じ面積の村人が後から現れても、小さい番号をそのまま残せます。

例えば、面積が順に \(12, 20, 20\) の場合、村人 \(2\) を調べた時点で答えを \(2\) に更新します。村人 \(3\) の面積も \(20\) ですが、更新しないため、正しく \(2\) を選べます。

一方、「最大面積以上なら更新する」とすると、この例では答えが \(3\) になり、誤答となります。

アルゴリズム

1. 最大面積を記録する best_area を \(-1\)、その村人の番号を記録する best を \(0\) で初期化します。
2. 村人を \(i = 1, 2, \ldots, N\) の順に調べます。
   • 縦 \(A_i\) と横 \(B_i\) を読み込みます。
   • 面積 area を \(A_i \times B_i\) として計算します。
   • area > best_area の場合だけ、best_area を area に、best を \(i\) に更新します。
3. 全員を調べた後、best を出力します。

この処理では、常に「調べた村人の中で面積が最大であり、その中で番号が最も小さい村人」を best に保持します。したがって、全員を調べ終えたときの best が答えです。

計算量

• 時間計算量: \(O(N)\)
  各村人について、面積の計算と比較をそれぞれ一度ずつ行います。
• 空間計算量: \(O(N)\)
  提示コードでは、入力全体を data に保存します。最大面積と答えの管理だけに必要な追加の空間は \(O(1)\) です。

実装のポイント

• 村人の番号は \(1\) から始まるため、range(1, n + 1) で順番に処理します。

• data[0] は人数 \(N\) です。村人 \(i\) の縦と横は、それぞれ data[2 * i - 1]、data[2 * i] に格納されています。

• 面積は必ず \(1\) 以上なので、best_area = -1 とすれば、最初の村人で必ず更新されます。

• 同じ最大面積では小さい番号を残すため、比較条件は >= ではなく > にします。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    best = 0
    best_area = -1
    for i in range(1, n + 1):
        a = int(data[2 * i - 1])
        b = int(data[2 * i])
        area = a * b
        if area > best_area:
            best_area = area
            best = i
    print(best)

main()

---

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