問題

C - Make a Rectangle

問題文

太さが無視できる棒が N 本あります． i 番目の棒の長さは Ai です．

すぬけ君は，これらの棒から 4本の異なる棒を選び，それらの棒を辺として長方形（正方形を含む）を作りたいです．作ることができる最大の長方形の面積を求めてください．

制約

* 4≤N≤105
* 1≤Ai≤109
* Ai は整数

とこんな感じ、

考えたこと

最初考えたのはハッシュ的にデータを保持できれば解けるかなと思いましたが、ハッシュを使う場合に配列の要素を 10⁹ 分の領域を確保しないといけないので、REになってしまいます。

vector + pair でデータの領域を 10⁵ に抑えられるのですが、pairの部分で該当要素を取得するまでに O(N²) を費やしてしまうので、この方法も却下になります。

ここで考えなおします。

要素は 10⁵ 以内に抑えて O(N) の計算量に抑えたいと考えます。以下のようになります。

* 要素はN個に合わせる (入力データをそのまま保持)
* 線形探索で問題を解く

これから考えると貪欲法が一番しっくりくるかなと考えました。

入力を配列に格納し、その配列をソートすれば横同士で数値が被るようになります。

そこから要素の先読みをし、その値が連番になるようならばwidth heightを更新していくことを行えば最大の横縦が求まるので後は乗算を行うことで答えが求まり、計算量とメモリ領域も足りることになります。

フロー

* 入力の受け取り

* Aiを昇順にソート

* 後ろの要素から線形探索
    * その要素から3つ先が存在する場合
        * 3つさきまで同じ要素ならば以下の処理をする 
            * width と height を更新し、要素を 3 つ先にすすめる
    * その要素から1つ先が存在する場合
        * 1つさきまで同じ要素ならば以下の処理をする
            * width と height を更新し、要素を 1 つ先にすすめる
 * width * height の出力

プログラム

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
  long long N;
  long long width,height;
  width = 0;
  height = 0;
  
  cin >> N;
  vector<long long> a;

  for (long long i = 0;i < N; i++){
    long long tmp;
    cin >> tmp;
    a.push_back(tmp);
  }
  sort(a.begin(),a.end());
  for (long long i = N - 1;i >= 0; i--){
    if(i - 3 >= 0){
      if(a[i] == a[i - 1] && a[i - 1] == a[i - 2] && a[i - 2] == a[i - 3]){
        width = width < a[i] ? a[i] : width;
        height = height < a[i] ? a[i] : height;
        i = i - 3;
      }
    }
    if (i - 1 >= 0){
      if(a[i] == a[i - 1] && height >= width){
        width = width < a[i] ? a[i] : width;
        i = i - 1;
      }else if(a[i] == a[i - 1] && width >= height){
        height = height < a[i] ? a[i] : height;
        i = i - 1;
      }
    }
  }
  cout << width * height << endl;
  return 0;
}

これでAC取れました。

xlkeiの日記

ABC071-C Make a Rectangle を解いてみた

問題

C - Make a Rectangle

問題文

制約

考えたこと

フロー

プログラム