yukicoder : No.849 yuki国の分割統治

久々に時間通り参加。
https://yukicoder.me/problems/no/849

問題

2次元座標において、2つのベクトル(a,b)と(c,d)が与えられる。
今、N人の人がいて、その座標(X[i],Y[i])が与えられる。
今いる座標に、両ベクトルを任意回数足したり引いたりした位置に移動できるとき、互いに移動可能な人を同一グループにいるとみなすと、N人はいくつのグループに分かれるか。

解法

各人、2つのベクトルを用いて移動できる範囲のうち、できるだけX座標が0に近く、次にY座標が0に近い場所に移動することを考える。
そうすると、互いに行き来できる人は皆同じ場所に到達するはずである。

もしこれが1次元なら、2つのベクトルのGCDを取ることがすぐ思いつくはず。
なのでそれを2次元に応用しよう。

もしa=c=0なら、gcd(b,d)単位で任意に上下に動けるので、Y[i] %= gcd(b,d)に移動すればよい。b=d=0の場合も同じ。
a!=0かつc!=0の場合、a=0かc=0となるまで２次元ベクトルのX座標に関し拡張ユークリッドの互除法の要領でより小さいベクトルに変換していこう。
例えば0＜a≦cなら、(c,d)を(c-a*floor(c/a),d-b*floor(c/a)で置き換える、ということを繰り返す。
その結果、2つのベクトルは(0,b),(c,d)といずれ片方X成分が0になる。
あとは後者のベクトルを使ってX座標を0に近づけ、前者のベクトルを使ってY座標を0に近づけよう。

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	ll x1,y1,x2,y2;
	
	cin>>x1>>y1>>x2>>y2;
	
	if(x1==0 && x2==0) y1=__gcd(y1,y2);
	else if(y1==0 && y2==0) x1=__gcd(x1,x2);
	else {
		if(x2<x1) swap(x1,x2),swap(y1,y2);
		while(x1&&x2) {
			ll d=x2/x1;
			x2=x2-x1*d;
			y2=y2-y1*d;
			if(x2<x1) swap(x1,x2),swap(y1,y2);
		}
		if(x2<x1) swap(x1,x2),swap(y1,y2);
		
	}
	set<pair<ll,ll>> S;
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		if(x1==0 && x2==0) Y[i]%=y1;
		else if(y1==0 && y2==0) X[i]%=x1;
		else {
			ll d=X[i]/x2;
			X[i]-=x2*d;
			Y[i]-=y2*d;
			if(y1) Y[i]=(Y[i]%y1+y1)%y1;
		}
		
		S.insert({X[i],Y[i]});
	}
	
	
	cout<<S.size()<<endl;
}

まとめ

方針はすぐ立ったけど、ちょっと手間取った。