Mail.Ru Cup 2018 Round 3 : G. Take Metro

なぜこれでいいのかわからん。
http://codeforces.com/contest/1056/problem/G

問題

1～Nの駅が時計回り順に環状に並んでいる。
1～Mの駅の内装は赤く、(M+1)～Nは青い。

初期状態で駅Sにおり、あるパラメータ初期値がTとする。
以下の手順を繰り返したとき、最後に降り立つ駅はどこか。

• Tが0なら終了。
• Tが正の場合、今いる駅の内装が赤いなら時計回り、青いなら反時計回りにT駅移動したのち、Tをデクリメントする。

解法

Editorialやコメントでも「証明できていないがこれで解ける」と書いてある方法なので、以下確証はない。
まずT mod Nが0になるまで、上記手順を愚直に繰り返そう。

移動距離は実質T mod Nで決まる。
一旦T mod N=0になると、以後T'=N-1から0まで、という移動パターンをT/N回繰り返すことに等しい。
ここで重要な知見として、「T'=N-1から0まで」という移動パターンを愚直に行うと、直感的にはサイクルに落ちるまでO(N)程度かかりそうだが、なんとO(√N)程度でサイクルに落ちるらしい。
よってサイクルを検出するまで移動を繰り返せば、あとはO(1)で解を求められる。

int N,M,B;
int S;
ll T;

vector<int> hist;
int vis[303030];

int nex(int S,ll T) {
	if(S<M) S+=T%N;
	else S+=N-T%N;
	return S%N;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	B=N-M;
	cin>>S>>T;
	S--;
	
	while(T%N) S=nex(S,T),T--;
	T/=N;
	
	MINUS(vis);
	FOR(i,T) {
		if(vis[S]!=-1) {
			int per=i-vis[S];
			S=hist[vis[S]+(T-i)%per];
			break;
		}
		vis[S]=i;
		hist.push_back(S);
		for(j=N-1;j>=0;j--) S=nex(S,j);
	}
	cout<<(S+1)<<endl;
	
	
	
}

まとめ

本番解いた人は実験で出したのかな…？