Codeforces ECR #162 : F. Shrink-Reverse

https://codeforces.com/contest/1923/problem/F

問題

N文字のバイナリ文字列Sと、整数Kが与えられる。
Sに以下の処理をK回まで行ったとき、Sを二進数とみなして最小どんな値にできるか。

• 2文字を入れ替える
• SのLeading Zeroを消した後反転する。

解法

後者は0回または1回だけ行えばよい。
0回の場合、Sの最小化は自明で、最も大きな桁の1を、最も小さな0とswapしていけばよい。
1回の場合、反転後で最も上位の1の来る桁を総当たりしよう。その場合、元のSを反転後、桁数が最少となるようにいくつか1を0の場所に移動してくることを考える。
そのようなSの最小値は、反転後のSのSuffixArrayを用いて求められる。

int N,K;
string S,A,B;
set<int> C;
const ll mo=1000000007;

int len[505050];

template<typename ST=string>
struct SuffixArray {
	int N; vector<int> rank,lcp,sa,rsa; ST S;

	void build(ST S){
		this->S=S;
	}
	
	SuffixArray(ST S) : S(S){
		int i,h=0; vector<int> tmp;
		N=S.size(); rank.resize(N+1); sa.resize(N+1); tmp.resize(N+1);
		FOR(i,N+1) sa[i]=i, rank[i]=i==N?-1:S[i];
		
		for(int k=1; k<=N; k<<=1) {
			auto pred2 = [k,this](int& a,int &b)->bool{ return (((a+k<=N)?rank[a+k]:-1)<((b+k<=N)?rank[b+k]:-1));};
			auto pred = [pred2,k,this](int& a,int &b)->bool{ return (rank[a]!=rank[b])?(rank[a]<rank[b]):pred2(a,b);};
			int x=0;
			if(k!=1) for(i=1;i<N+1;i++) if(rank[sa[i]]!=rank[sa[x]]) sort(sa.begin()+x,sa.begin()+i,pred2), x=i;
			sort(sa.begin()+x,sa.end(),pred);
			FOR(i,N+1) tmp[sa[i]]=(i==0)?0:tmp[sa[i-1]]+pred(sa[i-1],sa[i]);
			swap(rank,tmp);
		}
		lcp.resize(N+1); rsa.resize(N+1);
		FOR(i,N+1) rsa[sa[i]]=i;
		FOR(i,N) {
			int j=sa[rsa[i]-1];
			for(h=max(h-1,0);i+h<N && j+h<N; h++) if(S[j+h]!=S[i+h]) break;
			lcp[rsa[i]-1]=h;
		}
	}
};


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	int cnt=0;
	FOR(i,N) {
		S[i]-='0';
		if(S[i]) cnt++,C.insert(i);
	}
	if(C.size()<=K) {
		ll ret=0;
		FOR(i,C.size()) ret=(ret*2+1)%mo;
		cout<<ret<<endl;
		return;
	}
	A=S;
	int lef=K;
	for(i=N-1;i>=0;i--) if(lef&&A[i]==0) {
		if(C.size()&&*C.begin()<i) {
			A[i]=1;
			A[*C.begin()]=0;
			C.erase(C.begin());
			lef--;
		}
	}
	reverse(ALL(A));
	while(A.back()==0) A.pop_back();
	reverse(ALL(A));
	
	reverse(ALL(S));
	int n1=0;
	int mi=N+1;
	for(int L=0,R=0;L<N;L++) {
		while(R<N&&n1+(K-1)<cnt) n1+=S[R++];
		if(n1+(K-1)<cnt) len[L]=N+1;
		else len[L]=R-L;
		if(S[L]==1) n1--;
		mi=min(mi,len[L]);
	}
	SuffixArray sa(S);
	B=S;
	FOR(i,N+1) if(len[sa.sa[i]]==mi) {
		B=S.substr(sa.sa[i],mi);
		int lef=K-1;
		for(i=B.size()-1;i>=0;i--) if(lef&&B[i]==0) lef--,B[i]=1;
		while(lef--) B+=(char)1;
		break;
	}
	
	if(A.size()>B.size()) A=B;
	else if(A.size()==B.size()&&A>B) A=B;
	
	ll ret=0;
	FORR(a,A) ret=(ret*2+a)%mo;
	cout<<ret<<endl;
	
	
	
}

まとめ

数値になったとたん、比較でSuffixArray使うの忘れがち。