Codeforces Round #137 (Div. 2) A : Shooshuns and Sequence

問題概要

長さN(<10^5)の数列がある。

• k番目の要素を末尾に追加する。
• 先頭の要素を消す。

を何回繰り返したら全てが同じ要素になるか求める問題。同じにならないなら指摘する。

解法

dequeを使ってシミュレーションする。収束するとしたら高々Nくらいなのでその程度回して無理なら-1を返せばよい。ちゃんと調べてシミュレーション以外の方法で求めることもできる。

acceptされたコード

#include <cstdio>
#include <deque>
#include <map>
using namespace std;

const int MAX_N = int(1e5);
int N, K;
int as[MAX_N];

void init() {
	scanf("%d%d", &N, &K);
	--K;
	for (int i = 0; i < N; ++i) {
		scanf("%d", as + i);
	}
}

int solve() {
	map<int,int> freq;
	for (int i = 0; i < N; ++i) {
		++freq[as[i]];
	}

	deque<int> deq(as, as+N);
	for (int i = 0; i < 3*N; ++i) {
		if (freq[deq[0]] == N) {
			return i;
		}
		--freq[deq[0]];
		++freq[deq[K]];
		deq.push_back(deq[K]);
		deq.pop_front();
	}
	return -1;
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}