天下一プログラマーコンテスト2012 決勝 : D さんかく

Dもなんとか解けた。
http://tenka1-2012-final.contest.atcoder.jp/tasks/tenka1_2012_final_d

3N個の格子点の座標が与えられるので、N個の三角形を作ったときの面積合計を十分大きくする。
最大値ではなくてよく、1000万回のランダム選択の結果に勝てばよい。

とはいえ、こちらは1000万回も繰り返す時間はないので、もう少し効率よく求めないといけない。
そこで、２つの三角形を選び、その６点の中で２つの合計が最大になるように６点の組み合わせを変える、ということを1.8秒(最大が2秒なので)繰り返したら、点が300個または3000個の時は意外とあっさりクリア。

一方、点が9個・18個と少ないときはちょくちょくWAが出た。
なのでこのときは総当たりで最大値を求めてうまく行った。

以前ARCの乱拓で、手元だとうまく行かず、AtCoderサーバでうまく行った例があったのでいまだに乱拓怖い。
CygwinとAtCoderで乱数の仕組みが違うんだろうか…。

#define rdtscll(val) do { \
     unsigned int __a,__d; \
     asm volatile("rdtsc" : "=a" (__a), "=d" (__d)); \
     (val) = ((u64)__a) | (((u64)__d)<<32); \
} while(0)

int N;
s64 X[3000],Y[3000];
s64 mina=0;
int F[1000][3];
s64 madp[1<<18];
int madpath[1<<18][18];

u64 mtime() {
	struct timeval mt;
	u64 t;
	
	gettimeofday(&mt,NULL);
	t = (mt.tv_sec * 1000) + mt.tv_usec/1000;
	return t;
	
}

s64 area(int x,int y,int z) {
	return abs((X[y]-X[x])*(Y[z]-Y[x])-(Y[y]-Y[x])*(X[z]-X[x]));
}

void swap(int f1,int f2) {
	s64 first,best,c;
	int pat=0,i1,i2;
	first = best = area(F[f1][0],F[f1][1],F[f1][2]) + area(F[f2][0],F[f2][1],F[f2][2]);
	//6通り試す
	c = area(F[f1][0],F[f1][1],F[f2][0]) + area(F[f1][2],F[f2][1],F[f2][2]);
	if(c>best){ best=c; pat=1; i1=F[f1][2]; i2=F[f2][0];}
	c = area(F[f1][0],F[f1][1],F[f2][1]) + area(F[f2][0],F[f1][2],F[f2][2]);
	if(c>best){ best=c; pat=2; i1=F[f1][2]; i2=F[f2][1];}
	c = area(F[f1][0],F[f1][1],F[f2][2]) + area(F[f2][0],F[f2][1],F[f1][2]);
	if(c>best){ best=c; pat=3; i1=F[f1][2]; i2=F[f2][2];}
	
	c = area(F[f1][0],F[f2][0],F[f1][2]) + area(F[f1][1],F[f2][1],F[f2][2]);
	if(c>best){ best=c; pat=4; i1=F[f1][1]; i2=F[f2][0];}
	c = area(F[f1][0],F[f2][1],F[f1][2]) + area(F[f2][0],F[f1][1],F[f2][2]);
	if(c>best){ best=c; pat=5; i1=F[f1][1]; i2=F[f2][1];}
	c = area(F[f1][0],F[f2][2],F[f1][2]) + area(F[f2][0],F[f2][1],F[f1][1]);
	if(c>best){ best=c; pat=6; i1=F[f1][1]; i2=F[f2][2];}
	
	if(pat>0) {
		mina += best-first;
		if(pat==1) { F[f2][0]=i1; F[f1][2]=i2;}
		if(pat==2) { F[f2][1]=i1; F[f1][2]=i2;}
		if(pat==3) { F[f2][2]=i1; F[f1][2]=i2;}
		if(pat==4) { F[f2][0]=i1; F[f1][1]=i2;}
		if(pat==5) { F[f2][1]=i1; F[f1][1]=i2;}
		if(pat==6) { F[f2][2]=i1; F[f1][1]=i2;}
	}
}

int bitcount(int n) {
	int i=0;
	while(n>0) {i += n%2; n>>=1;}
	return i;
}

s64 dfs(int mask) {
	int bc = bitcount(mask);
	int lbc= N - bc;
	int i;
	int v1,v2,v3,mask2,maxmask;
	s64 ma=0,na;
	
	if(lbc==0) return 0;
	
	if(madp[mask]==-1) {
		//3つ選択
		FOR(v1,N-2) {
			if(mask & (1<<v1)) continue;
			for(v2=v1+1;v2<N-1;v2++) {
				if(mask & (1<<v2)) continue;
				for(v3=v2+1;v3<N;v3++) {
					if(mask & (1<<v3)) continue;
					mask2 = (1<<v1) |(1<<v2)|(1<<v3);
					na = area(v1,v2,v3) + dfs(mask | mask2);
					if(na > ma){ ma=na; maxmask = mask2;}
				}
			}
		}
		
		madp[mask] = ma;
		FOR(i,lbc-3) madpath[mask][i]=madpath[mask|maxmask][i];
		FOR(v1,N) if(maxmask & (1<<v1)) madpath[mask][lbc++-3] = v1;
		
	}
	return madp[mask];
}


void solve() {
	u64 st,ct,tsc;
	s64 res;
	int f,r,i,x,y,n,m,v1,v2;
	int path[18];

	
	//combination
	N=GETi();
	FOR(i,N){
		X[i]=GETi();
		Y[i]=GETi();
	}
	
	st = mtime();
	
	if(N<=18) {
		//18以下なら決定的に行う
		MINUS(madp);
		ZERO(madpath);
		madp[(1<<N)-1]=0;
		dfs(0);
		FOR(i,N/3) _P("%d %d %d\n",madpath[0][i*3+0],madpath[0][i*3+1],madpath[0][i*3+2]);
	}
	else {
	
		//初期
		FOR(i,N) F[i/3][i%3]=i;
		FOR(i,N/3) mina += area(i*3,i*3+1,i*3+2);
		
		while(1) {
			ct = mtime();
			if(ct-st>=1800) break;
			rdtscll(tsc);
			srand(ct+tsc);
			
			FOR(n,100000) {
				int f1,f2;
				f1=rand()%(N/3);
				f2=rand()%(N/3);
				if(f1!=f2) swap(f1,f2);
			}
			
		}
		FOR(i,N/3) _P("%d %d %d\n",F[i][0],F[i][1],F[i][2]);
	}
}

まとめ

乱拓の行き当たりばったり感は置いといて、とりあえず解けて良かった。
18個以下は総当たり、というのも行き当たりばったりだけど無事解き切れてよかった。

ほかの人の回答も乱数で点を交換する方法をとってる人が多いな。
あと、18点以下と300点以上で方法切り替えてる人もいた。