Codeforces #557 Div1 B. Chladni Figure

相変わらずCodeforcesが2か月分たまった状態だけど、GCJも一段落ついたし徐々に消化していくか。
https://codeforces.com/contest/1161/problem/B

問題

円周上に等間隔にN個の点がある。
ここで、２つの辺を選んで線分で結んだものがM個あったとする。

この図形を、(360度以外で)回転させた場合元と同じ形状になるケースはあるか判定せよ。

解法

各頂点、そこからどの相対位置の点に対して線分を持つかvector等でその一覧を管理しよう。
あとはこのvectorの配列が、周期性を持つか判定するだけ。
周期の候補としてNの約数を総当たりしよう。

int N,M;
vector<int> L[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		if(x>y) swap(x,y);
		L[x].push_back(y-x);
		L[y].push_back(x-y+N);
	}
	FOR(i,N) {
		sort(ALL(L[i]));
		L[i+N]=L[i];
	}
	
	for(i=1;i<N;i++) if(N%i==0) {
		FOR(j,N) if(L[j]!=L[j+i]) break;
		if(j!=N) continue;
		cout<<"Yes"<<endl;
		return;
	}
		
	cout<<"No"<<endl;
	
}

まとめ

解法はすぐ思いついたのに、しょうもないミスしてるのもったいない。