UTPC 2011 G: プログラミングコンテストチャレンジブック

keyword

乱択アルゴリズム　C++

問題概要

N(<10^5)個の長さの棒がある。このうち6本を選んで三角形を二つ作りたい。辺の長さの和を最大化する問題。

解法

三角形が1つなら長さをソートして連続する3つを順に見ていけば良い。なので、問題を分割する。棒を半分に分けてそれぞれ三角形を1個ずつ作る。棒を半分に分けたとき、ただしく分割される確率は1/32なので、試行回数を増やせば何とか通りそう。
で、通る確率について考えてみよう。まず、テストケース1個あたりの反復回数をKとする。また、テストケースの個数をT個とすると、全て通る確率は(1-(1-1/32)^K)^T。これにT=70を代入してプロットしてみればわかるけど、K=100~200の範囲で急激に増加していることがわかる。K=100だと落ちる確率の方が高いのだけど何とかAcceptされた。
想定解法はもっと綺麗にgreedyで解いている。

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

typedef long long int64;

int64 as[100009];
int N;

inline bool canMake(int64 a, int64 b, int64 c){
	return a<b+c;
}

int64 solve(){
	vector<int64> cur;
	for(int i=0; i<N; i++){
		cur.push_back(as[i]);
	}
	int64 ret = 0;
	int len  = N/2;
	for(int loop=0; loop<100; loop++){
		random_shuffle(cur.begin(), cur.end());
		vector<int64> bs, cs;
		for(int i=0; i<len; i++)bs.push_back(cur[i]);
		for(int i=len; i<N; i++)cs.push_back(cur[i]);
		int64 a = -1, b = -1;
		sort(bs.rbegin(),bs.rend());
		for(int i=0; i<(int)bs.size()-2; i++){
			if(canMake(bs[i],bs[i+1],bs[i+2])){
				a = bs[i] + bs[i+1] + bs[i+2];
				break;
			}
		}
		if(a==-1) continue;
		sort(cs.rbegin(), cs.rend());
		for(int i=0; i<(int)cs.size()-2; i++){
			if(canMake(cs[i],cs[i+1],cs[i+2])){
				b = cs[i] + cs[i+1] + cs[i+2];
				ret = max(ret, a + b);
				break;
			}
			else if(3*cs[i] < ret - a) break;
		}
	}
	return ret;
}

int main(){
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf("%lld",as+i);
	}
	printf("%lld\n",solve());
	return 0;
}