概要

各村人の畑の面積を求め、面積が最大となる村人のうち、番号が最も小さい人を探します。提示されたコードでは、各村人が答えの条件を満たすか、ほかの全員と比較して判定します。

考察

\(i\) 番目の村人の畑の面積は、縦と横の長さを掛けた \(S_i = A_i \times B_i\) です。

面積が最大であることだけを確認すると、同じ最大面積の村人が複数いる場合に、番号が最も小さい人を選べない可能性があります。そこで、村人 \(i\) が答えとなる条件を、次のように分けます。

• 番号が小さい村人について：面積が \(S_i\) 以上の人がいない。
• 番号が大きい村人について：面積が \(S_i\) より大きい人がいない。

番号が小さい人とは、面積が同じでもその人が優先されます。一方、番号が大きい人とは、面積が同じでも村人 \(i\) が優先されます。このため、前後で比較条件が異なります。

例えば、面積が順に \([6, 12, 12]\) の場合を考えます。

• 村人 \(1\) は、後ろに面積がより大きい人がいるため、答えではありません。
• 村人 \(2\) は、前に面積が \(12\) 以上の人がおらず、後ろに面積が \(12\) より大きい人もいないため、答えです。
• 村人 \(3\) は、前に同じ面積の村人 \(2\) がいるため、答えではありません。

全員同士を比較する素朴な方法でも、\(N \leq 100\) なので十分に間に合います。高速化よりも、同じ面積の場合の条件を正しく扱うことが重要です。

アルゴリズム

1. 各村人の畑の面積を計算し、配列 s に保存します。
2. 配列の添字 i を小さい順に調べます。
   • ok を true にします。
   • j < i を満たすすべての j について、s[j] >= s[i] なら ok を false にします。
   • j > i を満たすすべての j について、s[j] > s[i] なら ok を false にします。
   • 最後まで ok が true なら、村人の番号 i + 1 を出力して終了します。

この判定を通過した村人より大きい面積の人は、前にも後ろにもいません。また、同じ面積で番号が小さい人もいません。したがって、出力されるのは「面積が最大の村人のうち、番号が最も小さい人」です。

逆に、正しい答えとなる村人は必ずこの条件を満たすため、答えは確実に見つかります。

計算量

• 時間計算量: \(O(N^2)\)
  各村人について、ほかの最大 \(N-1\) 人と比較します。
• 空間計算量: \(O(N)\)
  全員の畑の面積を配列に保存します。

実装のポイント

• 前の村人には >=、後ろの村人には > を使います。 同じ面積の場合に小さい番号を優先するための重要な違いです。

• 配列の添字は \(0\) から始まりますが、村人の番号は \(1\) から始まるため、出力は i + 1 です。

• 面積の最大値は \(1000 \times 1000 = 10^6\) です。提示されたコードでは、面積と縦横の長さを long long 型で扱っています。

  ソースコード

// 問題文から独立に実装: 各村人について「自分より前に自分以上の面積がなく、後ろに自分より大きい面積がない」か調べる
#include <iostream>
#include <vector>
int main() {
    int n; std::cin >> n;
    std::vector<long long> s(n);
    for (int i = 0; i < n; ++i) { long long a, b; std::cin >> a >> b; s[i] = a * b; }
    for (int i = 0; i < n; ++i) {
        bool ok = true;
        for (int j = 0; j < i; ++j) if (s[j] >= s[i]) ok = false;
        for (int j = i + 1; j < n; ++j) if (s[j] > s[i]) ok = false;
        if (ok) { std::cout << i + 1 << std::endl; return 0; }
    }
}

---

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