AtCoder ARC #150 : E - Weathercock

これは全然考察できなかった。
https://atcoder.jp/contests/arc150/tasks/arc150_e

問題

NK人の人が並んでおり、それぞれ左右どちらを向いているかが与えられる。
時間1ごとに、自分の向いている向きに、逆向きを向く人が過半数であれば向きを変える、という作業を行う。
長時間立った後、各人が向きを変える回数の総和を求めよ。

解法

右を向いている人が多数である場合を考える。
向きを変えるのは高々2回で、

• 初期状態で左を向く人が、右を向くことがある。
• 初期状態で右を向く人が、一旦左を向いたあと、また右を向く

それぞれを数え上げればよい。

int N,K;
string S;
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	
	if(count(ALL(S),'L')>count(ALL(S),'R')) {
		reverse(ALL(S));
		FORR(c,S) c='L'+'R'-c;
	}
	
	
	if(count(ALL(S),'L')==count(ALL(S),'R')) {
		int cur=0,num=0;
		FORR(c,S) {
			if(c=='L') {
				cur--;
				if(cur>=0) num++;
			}
			else {
				cur++;
				if(cur>0) num++;
			}
		}
		cout<<1LL*num*K%mo<<endl;
		return;
	}
	
	ll ret=0;
	x=N+5;
	int step=0;
	FOR(i,N) {
		if(S[i]=='L') step--;
		else step++;
		if(step>=1) x=min(x,i);
	}
	ll ma=1LL*step*K;
	int cur=0;
	FOR(i,N) {
		if(S[i]=='L') {
			cur--;
			if(i>=x) {
				ret+=K;
			}
			else {
				ret+=K-1;
			}
		}
		else {
			cur++;
			if(cur>ma) {
				ret+=2*K;
			}
			else {
				ll dif=ma+1-cur;
				dif=(dif+step-1)/step;
				if(dif<K) ret+=2*(K-dif);
			}
		}
	}
	cout<<ret%mo<<endl;
	
}

まとめ

これさっさと実験してれば2回しか反転しないと気付けたのかな…。