Google Code Jam 2020 Round 2 : C. Wormhole in One

これはサンプルのお陰で助かった。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019ffb9/00000000003386d0

問題

2次元座標中に、N個の点が与えられる。
これらの点がゴルフのホールだと考える。
このうち、任意のホール対について、2つの点を結ぶようにできるとする（各ホールは他の1つのホールとしか対になれない）。

任意の点から任意の角度でボールを打ち出したとき、そのボールは等速直線運動で動き続ける。
途中、対になっていないホールに到達したらそこで終了する。
対になっているホールに到達したら、対のホールの位置にワープして、また運動を続ける。
同じホールに複数回入ってもよい。

最大で何か所のホールを経由することができるか。

解法

ワープ後に飛び出たボールが、また他のホールに入る可能性を考えると、射出の角度はO(N^2)通りを考えればよい。
そこで、これらの角度を総当たりしよう。
角度を決めたら、その角度で互いに行き来可能なホール対を互いにグループにしていこう。

偶数個のホールからなるグループは、グループ外のホールから、グループ内の端のホールにワープしてくることで、グループ内の全ホールをたどってまたグループ外に出ることができる。
また、サンプルからわかる通り、3個以上のホール2個のグループで、偶数個のホールのグループ同様にみなすことができる。

よって、これらを順につなげればこれらは全部たどることができる。
残りは、1個のホールからなるグループがいくつかと、3個以上奇数個のホールからなるグループ1個以下である。
最初のスタートと、最後のゴールでこのうち2グループまで選ぶことができるので、ホール数の多い2個を連結させよう。

int N;
ll X[101],Y[101];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	
	if(N<=3) {
		_P("Case #%d: %d\n",_loop,N);
		return;
	}
	
	int ma=3;
	FOR(j,N) FOR(i,j) {
		map<pair<ll,ll>,int> M;
		if(X[i]==X[j]) {
			FOR(x,N) M[{X[x],1}]++;
		}
		else {
			ll dx=X[i]-X[j];
			ll dy=Y[i]-Y[j];
			if(dx<0) dx=-dx,dy=-dy;
			
			FOR(x,N) {
				ll p=Y[x]*dx-dy*X[x];
				ll q=dx;
				ll g=__gcd(p,q);
				p/=g;
				q/=g;
				M[{p,q}]++;
			}
		}
		int sum=0;
		int num=0;
		vector<int> C;
		FORR(m,M) {
			if(m.second%2==0) sum+=m.second;
			else C.push_back(m.second);
		}
		sort(ALL(C));
		while(C.size()>=2 && C[C.size()-2]>=3) {
			sum+=C.back();
			C.pop_back();
			sum+=C.back();
			C.pop_back();
		}
		
		if(C.size()==1) {
			sum+=C[0];
		}
		else if(C.size()>=2) {
			sum+=C.back();
			C.pop_back();
			sum+=C.back();
			C.pop_back();
		}
		
		ma=max(ma,sum);
		
	}
	
	
	_P("Case #%d: %d\n",_loop,ma);
}

まとめ

ちょっと自信なかったけど通ってよかった。