Codeforces #297 Div2 C. Ilya and Sticks

CF#297に参加。
Cで凡ミスしたものの、D,Eが解ききれて好順位。
http://codeforces.com/contest/525/problem/C

問題

N本の棒があり、それぞれの長さはL[i]である。
各棒の長さは、1だけ短くすることができる。

これらの棒を使って、棒を外枠とするようないくつかの長方形を作り、その合計面積を最大化せよ。

解法

長方形を作るには、同じ長さの棒を２本１組にした上で、それが２組なければならない。
また、同じ棒を使って長方形を作るなら、長いもの同士を用いた方が面積の総和は大きい。

よって、まず棒を長さでソートし、長い棒から順に差が１以内のものを組にする。
次に、この組に対して長い棒の組から順に２組ずつ合わせて長方形を作る。

int N;
vector<ll> L,L2;
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, L.push_back(x);
	sort(L.begin(),L.end());
	while(L.size()>=2) {
		y=L.size()-1;
		if(L[y]<=L[y-1]+1) {
			L2.push_back(L[y-1]);
			L.pop_back();
		}
		L.pop_back();
	}
	FOR(i,L2.size()/2) ret +=L2[i*2]*L2[i*2+1];
	
	cout<<ret<<endl;
}

まとめ

本番は「長い順４本が条件を長方形を作れるなら～」という処理をやってしまった。
上から３番目と４番目の長さが２以上差がある場合、３番目をあきらめて４番目と５番目を合わせた方がいい時もあるのね…。