Codeforces 222 A. Shooshuns and Sequence

問題

n項からなる数列a[i]と、1≦k≦nを満たす整数kが与えられる。
このとき、数列に対して次の操作を繰り返す。

• 数列のk番目の項と同じ数字を、現在の数列の末尾に付け足す
• 数列の1番目の項を削除する

この操作を繰り返したとき、数列の全ての項が一致するなら、
必要な操作の回数の最小値を、そうでないなら-1を出力せよ。

制約条件

1≦k≦n≦10^5
1≦a[i]≦10^5

方針

十分な回数シミュレーションして、全部の数字が同じになるかを見る。
全部の数字が同じになるかは、
それぞれの値が何回数列に現れているかを数えておくことでO(1)で出来る。

ソースコード

int n, k, a[400000], cnt[200000];

int main(){
	cin >> n >> k;
	k--;
	rep(i, n){
		cin >> a[i];
		cnt[a[i]]++;
	}
	int b = 0;
	rep(i, 200000) if(cnt[i]) b++;
	
	if(b == 1){
		cout << 0 << endl;
		return 0;
	}
	
	rep(i, 2 * n){
		a[i + n] = a[i + k];
		if(++cnt[a[i + k]] == 1) b++;
		if(cnt[a[i]]-- == 1) b--;
		
		if(b == 1){
			cout << i + 1 << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	
	return 0;
}