AtCoder BC071 C : Make a Rectangle

問題

C - Make a Rectangle
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

長方形の辺の候補となるのは2本以上存在する棒です。また、4本以上存在すれば正方形にすることが出来ます(正方形は長方形に含まれる)

 よって、同じ棒が2本現れる毎に辺の候補に追加し、その中から1番目に長いものと2番目に長いもので長方形を作れば解となります。

 なお、辺の候補が2つ以上無ければ解無しとして0を出力します。

実装

実装としては、同じ長さの棒のカウントにはmap、辺の候補の管理はvectorで行います。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    map<ll, int> m;
    vector<ll> a;

    REP(i,N){
        ll tmp;
        cin >> tmp;
        m[tmp]++;
        if(m[tmp] % 2 == 0){
            a.push_back(tmp);
        }
    }
    if(a.size() > 1){
        sort(a.begin(),a.end());
        cout << a[a.size()-1] * a[a.size()-2] << endl;
    }else{
        cout << 0 << endl;
    }

}

コメント

タイトルとURLをコピーしました