ABC071 C - Make a Rectangle を自力で WA => AC まで持ち上げてみた

問題

一発目の WA はコチラ。

abc071.cpp

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

int main() {
	int N,A; cin >> N;
	map<int, int>nums;
    //入力 受け取り
	for (int i = 0; i < N; i++) {
		cin >> A;
		nums[A]++; // 入力で map を生成 , 各要素の重複数をカウント
	}

	vector<long long>area; // 正方形 用の要素を格納
	vector<int> factor;    // 長方形 用の要素を格納
	for (auto x : nums) {
		if (x.second >= 4) // 要素が 4 つあれば正方形に利用
			area.push_back(x.first);
/*bat */else if (2 <= x.second && x.second <= 3) // 要素が 2 以上 3 以下であれば
			factor.push_back(x.first);           // 長方形に利用
	}

	long long square = 0;
	if(area.size()>0){//そもそも　4つも重複していない可能性がある
		sort(area.begin(), area.end(), greater<long long>());
		square = area[0] * area[0]; // 最大の辺を使用
	}
	long long rectangle = 0;
	if(factor.size()>1){//そもそも 長方形用の要素が無いかも
		sort(factor.begin(), factor.end(), greater<int>());
		rectangle = (factor[0] * factor[1]); // 最大の辺を使用
	}

	cout << max(square, rectangle); // 大きい方を output
	//while (1) {}
	return 0;

}

テストケースを探したが見当たらなかった、残念。

だが、上記で/*bat */と記述した点に違和感をおぼえた。なぜなら
正方形の要素としてカウントしたものも、長方形としても検討して良いからだ。

その他にも、他のミスが無いか検討したが、
見当たらないので以下で提出したが、WA.
(少し視認性を上げた。。)

abc071.cpp

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

int main() {
	int N,A; cin >> N;
	map<int, long long>nums;
	for (int i = 0; i < N; i++) {
		cin >> A;
		nums[A]++;
	}

	vector<long long>factor_S;// 正方形 用の要素を格納
	vector<long long>factor_R;// 長方形 用の要素を格納
	for (auto x : nums) {
		if (x.second >= 4)
			factor_S.push_back(x.first);
/*bat */else if (x.second >= 2)
			factor_R.push_back(x.first);
	}

	long long square = 0;
	if(factor_S.size()>0){
		sort(factor_S.begin(), factor_S.end(), greater<long long>());
		square = factor_S[0] * factor_S[0];
	}
	long long rectangle = 0;
	if(factor_R.size()>1){
		sort(factor_R.begin(), factor_R.end(), greater<long long>());
		rectangle = (factor_R[0] * factor_R[1]);
	}

	cout << max(square, rectangle);
	//while (1) {}
	return 0;

}

御覧の通り /*bat */ でミスを発見。
if ~ , else if だと、条件にはまる何れかを実行。
いやいや、正方形の要素、長方形の要素 を同時に取り込んで欲しい。
つまり、if ~ , if ~ が正解だ。

そこに気付いて以下で AC.

abc071.cpp

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

int main() {
	int N,A; cin >> N;
	map<int, long long>nums;
	for (int i = 0; i < N; i++) {
		cin >> A;
		nums[A]++;
	}

	vector<long long>factor_S;
	vector<long long>factor_R;
	for (auto x : nums) {
		if (x.second >= 4)
			factor_S.push_back(x.first);
		if (x.second >= 2)
			factor_R.push_back(x.first);
	}

	long long square = 0;
	if(factor_S.size()>0){
		sort(factor_S.begin(), factor_S.end(), greater<long long>());
		square = factor_S[0] * factor_S[0];
	}
	long long rectangle = 0;
	if(factor_R.size()>1){
		sort(factor_R.begin(), factor_R.end(), greater<long long>());
		rectangle = (factor_R[0] * factor_R[1]);
	}

	cout << max(square, rectangle);
	//while (1) {}
	return 0;

}