天下一プログラマーコンテスト2012 決勝 : B よんてん

続いて２問目。
http://tenka1-2012-final.contest.atcoder.jp/tasks/tenka1_2012_final_b

(0,0)-(99,99)の座標内で、最大10000個の格子点が与えられる。
その中で４点をとったとき、どの３点も一直線にならないケースの数(を1000000007でmod取ったもの)を答える。

全体の数はで、そこからダメなケースを引くと良い。
格子点の中で、３個以上一直線になった点がM個あったとすると、以下の２つを全体の数から引く。

• M個から4つ点を選ぶケース：通り
• M個から3つ点を選び、M個以外から1つ点を選ぶケース：通り

問題は３個以上が一直線に並ぶ判定。
最初は、２点を選びその直線状に他の点が来るか判定したところ、そのまま組むとO(N^3)、座標が0-99なので、その100個の点だけ調べてもO(N^2)で、N=10000だと３秒位かかってTLEになってしまった。

そこで方針変更、３つ以上点が並ぶ場合、あり得る角度は、(-50,-50)～(50,50)しかないので、全部の点からこれらの角度で進んだとき何個点が並ぶか試してみた。
これだと座標の範囲をWとしてO(W^3)、W=100なのでどうにか行ける。
実際、400ms以下で済んだ。

int N;
s64 C[10001][10];
s64 mo=1000000007LL;
int po[100][100];
int g[100][100];
int vis[100][100];

int search(int sx,int sy,int dx,int dy) {
	//tx,tyから
	int i=0,tx,ty,c=0;
	
	while(1) {
		tx = sx+dx*i;
		ty = sy+dy*i;
		if(tx<0 || ty<0 || tx>=100 || ty>=100) break;
		c+=po[tx][ty];
		vis[tx][ty]=1;
		i++;
	}
	return c;
}

void solve() {
	s64 res;
	int f,r,i,x,y,n,m,v1,v2;
	
	//combination
	ZERO(C);
	C[0][0]=1;
	for(n=1;n<10001;n++) {
		C[n][0]=1;
		for(m=1;m<10;m++) C[n][m]=(C[n-1][m-1]+C[n-1][m])%mo;
	}
	
	//最大公約数を求める
	ZERO(g);
	FOR(y,100){
		FOR(x,y+1) FOR(i,x) if(y%(i+1)==0 && x%(i+1)==0) g[y][x]=g[x][y]=i+1;
	}
	for(y=1;y<100;y++) g[y][0]=g[0][y]=y;
		
	ZERO(po);
	N=GETi();
	FOR(i,N){
		x=GETi();
		y=GETi();
		po[x][y]=1;
	}
	
	//全体から4つ選択
	res = C[N][4];
	//縦方向
	FOR(x,100) {
		int vc=0;
		FOR(y,100) vc+=po[x][y];
		//一直線上の３点とそれ以外を使うケースを引く
		if(vc>=4) res -= C[vc][4];
		if(vc>=3) res -= C[vc][3]*(N-vc);
		res = ((res%mo)+mo)%mo;
	}
	
	//斜め
	int dx,dy,tx,ty;
	for(dx=1;dx<51;dx++) {
		for(dy=-50;dy<51;dy++) {
			if(g[abs(dx)][abs(dy)]!=1) continue;
			ZERO(vis);
			FOR(tx,100) {
				if(tx+dx>=100) continue;
				
				FOR(ty,100) {
					if(vis[tx][ty]==0 && po[tx][ty]) {
						int vc = search(tx,ty,dx,dy);
						if(vc>=4) res -= C[vc][4];
						if(vc>=3) res -= C[vc][3]*(N-vc);
						
					}
				}
			}
			res = ((res%mo)+mo)%mo;
		}
	}
	
	
	_P("%lld\n",res);
	
}

まとめ

数のカウントのアプローチは正しかったが、一直線判定の計算量を落とすのに苦労した。
このレベルの問題が５問中２問目にくるのは大変だ。