AtCoder ABC 071 C - Make a Rectangle (4Q, 茶色, 300 点)

長さが大きい順に処理していこう！

• 問題へのリンク

問題概要

長さが の棒がある。

これらの棒を 4 個選んで長方形を作りたい。作れる長方形の面積の最大値を求めよ。長方形を作れない場合は 0 と答えよ。

制約

• 
• 

考えたこと

できるだけ大きい長さの棒を使いたい。しかし、その長さの棒が 1 種類しかないような棒は使えないことに注意しよう。

このことに注意して、次のように解ける。

---

1. 棒の長さを大きい順にソートする
2. 次のことを 2 回行う:
3. 　残っている棒の中で、最大の長さの棒 をとる
4. 　その棒と長さの等しい棒が存在しないとき： を捨てて 3 に戻る
5. 　その棒と長さの等しい棒 が存在するとき： をペアにする

---

これによって、「長さの等しい棒のペア」を 2 組作れるので、長方形を作ることができる。

以上の解法の計算量は となる（ソートがボトルネックである）。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());  // 小さい順にソートして末尾から見ることにする

    vector<long long> res;
    for (int iter = 0; iter < 2; iter++) {
        // 最大の長さの棒を抜き取る (長さ x とする)
        long long x = A.back(); 
        A.pop_back();

        // もし、その残りの棒の長さの最大値が x でなかったら、そうである限り
        while (!A.empty() && A.back() != x) {
            x = A.back();  // 残っている棒の最大の長さを x とする
            A.pop_back();
        }

        // 棒が残らなかったら長方形は作れない
        if (A.empty()) {
            cout << 0 << endl;
            return 0;
        }
        res.push_back(x);
        A.pop_back();
    }
    cout << res[0] * res[1] << endl;
}