kmjp's blog

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

Codeforces #639 Div1 A. Hilbert's Hotel

ようやく5月分に突入。
https://codeforces.com/contest/1344/problem/A

問題

部屋が無限個あり、各部屋には(ゼロや負を含む)すべての整数が1個ずつ振られている。
また、各部屋に1人ずつ人がいる。
今ここでN要素の数列Aが与えられる。
k番目の部屋の人が、k+A[k%N]番目の部屋に移動したとき、1つの部屋に2人以上いることがないか判定せよ。

解法

Nで割った余りが同じ部屋の人は、移動後もかち合うことがない。
言い換えれば、そのような人の誰かは0~(N-1)のどこか1か所だけに行く人は1人はいるはずである。
そこで、部屋0~(N-1)の人をを移動させてみて、mod Nを取り、かち合わないことを確認しよう。

int T;
int N;
int A[202020];
int C[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) C[i]=0;
		FOR(i,N) {
			cin>>x;
			x+=i;
			x%=N;
			if(x<0) x+=N;
			C[x]++;
		}
		
		if(count(C,C+N,1)==N) {
			cout<<"YES"<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
		
	}
}

まとめ

解法よりも問題設定を理解するのに戸惑う。