読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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

その他コンテスト

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

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

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

  • M個から4つ点を選ぶケース:{}_M C_4通り
  • M個から3つ点を選び、M個以外から1つ点を選ぶケース:{}_M C_3 \times (N-M)通り

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


そこで方針変更、3つ以上点が並ぶ場合、あり得る角度は、(-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];
		//一直線上の3点とそれ以外を使うケースを引く
		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);
	
}

まとめ

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

広告を非表示にする