Codeforces Global Round 10 : G. Omkar and Pies

半分は自力でたどり着けるけど、半分は無理だな…。
https://codeforces.com/contest/1392/problem/G

問題

0/1で構成される2つのk文字の文字列S,Tが与えられる。
また、Sのうち2要素をswapする命令がN個与えられる。

命令列のうちM要素以上の連続列を選び、そのとおりSに処理を加えるとTと一致する文字数が最大化するようにしたい。
選び方を求めよ。

解法

まず、SとTが完全一致するケースを考える。
Sに[L,R]の命令列を適用したらTになるとする。
この時、Sに[1,R]の命令列を適用したものと、Tに[1,L-1]を適用したものも等しいはずである。

そこで、
f(mask) := Sがmaskの状態になる最も大きなR
g(mask) := Tがmaskの状態になる最も小さなL
とすると、f(mask)-g(mask)≧Mとなるmaskを求めればよいことになる。

ただこの問題はSとTが一致しないケースもある。
そこで以下を求めよう。
f'(mask) := Sがmaskを含む状態になる最も大きなR
g'(mask) := Tがmaskを含む状態になる最も小さなL
とする。もしf'(mask)-g'(mask)≧Mであるとき、2*popcount(mask)+k-(1の総数)が一致した文字数となるので、maskを総当たりしながら左記の値が最大化されるケースを求めよう。

int N,M,K;
string S,T;
int L[1010101],R[1010101];
int to[20];
int SS[1010101],TT[1010101];

int lef[1<<20],ri[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(lef);
	cin>>N>>M>>K;
	cin>>S>>T;
	
	FOR(i,N) {
		cin>>L[i]>>R[i];
		L[i]--,R[i]--;
	}
	
	FOR(i,1<<20) {
		lef[i]=N+1;
		ri[i]=-1;
	}
	
	FOR(i,K) {
		to[i]=i;
		if(T[i]=='1') TT[0]|=1<<to[i];
		if(S[i]=='1') SS[0]|=1<<to[i];
		lef[SS[0]]=0;
		ri[TT[0]]=0;
	}
	
	FOR(i,N) {
		swap(to[L[i]],to[R[i]]);
		
		FOR(j,K) {
			if(T[j]=='1') TT[i+1]|=1<<to[j];
			if(S[j]=='1') SS[i+1]|=1<<to[j];
		}
		lef[SS[i+1]]=min(lef[SS[i+1]],i+1);
		ri[TT[i+1]]=i+1;
	}
	
	FOR(i,20) {
		FOR(x,1<<20) if(x&(1<<i)) {
			lef[x^(1<<i)]=min(lef[x^(1<<i)],lef[x]);
			ri[x^(1<<i)]=max(ri[x^(1<<i)],ri[x]);
		}
	}
	
	int ma=-1;
	FOR(i,1<<20) {
		if(__builtin_popcount(i)>ma && ri[i]-lef[i]>=M) {
			ma=__builtin_popcount(i);
			x=lef[i];
			y=ri[i];
		}
	}
	int A=count(ALL(S),'1')+count(ALL(T),'1');
	
	cout<<(2*ma+S.size()-A)<<endl;
	cout<<(x+1)<<" "<<(y)<<endl;
	
	
	
}

まとめ

後半の考察が思い浮かばないなぁ。