Pinely Round 5 : E. Left is Always Right

なるほど。
https://codeforces.com/contest/2161/problem/E

問題

N文字の0/1のバイナリ列Sと、奇数Kが与えられる。
Sの一部は不定である。

Sの不定の場所を0/1で埋める埋め方のうち、任意の連続するK要素において、先頭要素と多数派の要素が一致するものは何通りか。

解法

d(a,b)を、S[a....b]のうち、(1の数)-(0の数)とする。
d(1,K)＞0のケースを考える。(d(1,K)＜0のケースは、全体を0/1反転して考えればよい。)

• d(a,a+K-1)が常に1を超える場合
  • 先頭N-(K-1)要素は1である。残り(K-1)要素のうち、(K-1)/2より多く1があれば条件を満たすので、二項係数の和で計算できる
• d(a,a+K-1)が1となる箇所があり、その最小値がaである場合
  • S[1,...a]は1でなければならない
  • S[a+K]以降は周期(K-1)で同じパターンを繰り返す
  • aを総当たりし、前後が上記のパターンを取れるか判定しよう。

int T,N,A[303030];
vector<int> cand[303030];
int dp[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cand[i].clear();
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			cand[A[i]].push_back(i);
		}
		int pre=0;
		FOR(i,N) {
			reverse(ALL(cand[i]));
			int cur=pre;
			if(i) {
				x=0;
				FORR(a,cand[i]) {
					while(x<cand[i-1].size()&&cand[i-1][x]>a) {
						cur=max(cur,dp[cand[i-1][x++]]);
					}
					cur=dp[a]=cur+1;
				}
				FORR(a,cand[i-1]) pre=max(pre,dp[a]);
			}
			else {
				cur=0;
				FORR(a,cand[i]) {
					dp[a]=++cur;
				}
			}
		}
		int ret=0;
		FOR(i,N) {
			ret=max(ret,dp[i]);
		}
		cout<<N-ret<<endl;
		
	}
}

まとめ

このタイプの多数派問題始めた見たかもな。