yukicoder : No.3266 岩井星人は見ずにはいられない

実装は割とシンプル。
https://yukicoder.me/problems/no/3266

問題

初期状態でプレイヤーのレートを1200とする。
以降、以下のN個のイベントを繰り返し実行する。
各イベントは以下のいずれかである。

• レートをデクリメントする
• レートが1200未満ならインクリメントする

レートのインクリメントがA回行われるのは何回目のイベントか。

解法

• N個のイベントが、インクリメントよりデクリメントの方が多い場合、2周目以降のインクリメントは必ず成功する
• そうでない場合、2周目以降はレート遷移が同じパターンを繰り返す

いずれにせよ、2周目以降はインクリメントに成功するタイミングは周期性が出るので、大きなAに対しても容易にA回目のインクリメントを求められる。

int N;
ll A;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>S;
	int C[2]={};
	//とりあえず2周
	ll cur=0;
	
	FOR(i,N) {
		if(S[i]=='0') {
			cur++;
		}
		else {
			if(cur) {
				cur--;
				A--;
			}
		}
		if(A==0) {
			cout<<i+1<<endl;
			return;
		}
	}
	vector<int> cand;
	FOR(i,N) {
		if(S[i]=='0') {
			cur++;
		}
		else {
			if(cur) {
				cand.push_back(i+1);
				cur--;
				A--;
			}
		}
		if(A==0) {
			cout<<N+i+1<<endl;
			return;
		}
	}
	ll step=2*N;
	ll a=(A-1)/cand.size();
	step+=N*a;
	A-=a*cand.size();
	cout<<step+cand[A-1]<<endl;
	
	
}

まとめ

勘でもACできそうだけど、考察して自信をもってSubmitできないな…。