Codeforces #664 Div1 C. Boboniu and String

変な問題設定。
https://codeforces.com/contest/1394/problem/C

問題

B,Nで構成される文字列S,Tの距離dist(S,T)を以下のように定める。

• Sに以下の処理を任意回数行う。
  • 1文字減らす
  • 'BN'または'NB'の並びを1つ消す
  • 1文字末尾に加える
  • 'BN'または'NB'の並びを末尾に加える
• Sを並べ替えた文字列がTになるような、最小処理回数がdist(S,T)

文字列の配列Uが与えられる。
dist(U[i],T)の最大値が最小となるようなTとその時のdist(U[i],T)の最大値を示せ。

解法

今文字列Sに含まれるB,Nの値をx,yとする。
処理で行えるのは

• xをインクリメントまたはデクリメント
• yをインクリメントまたはデクリメント
• x,yを合わせてインクリメント
• x,yを合わせてデクリメント

である。ここで、解となるdist(U[i],T)の最大値vを二分探索することを考えよう。
文字列U[i]に対応する(x,y)に対し、v回以内の処理で遷移できる領域を2次元座標上でプロットすると六角形となる。
各Uにおける六角形が共通領域を持つならば、そこはv回以内で遷移できるTに相当する。

int N;
int X[303030],Y[303030];

pair<int,int> hoge(int v) {
	int L=0,R=1<<30;
	int D=0,U=1<<30;
	int SD=-1<<30,SU=1<<30;
	int i;
	FOR(i,N) {
		L=max(L,X[i]-v);
		R=min(R,X[i]+v);
		D=max(D,Y[i]-v);
		U=min(U,Y[i]+v);
		SD=max(SD,Y[i]-X[i]-v);
		SU=min(SU,Y[i]-X[i]+v);
	}
	if(L>R) return {-1<<30,-1<<30};
	if(D>U) return {-1<<30,-1<<30};
	if(SD>SU) return {-1<<30,-1<<30};
	
	//cout<<v<<" ok"<< L<<":"<<R<<" "<<D<<":"<<U<<" "<<SD<<" "<<SU<<endl;
	vector<int> Xs={L,L+1,R};
	vector<int> Ys={D,D+1,U};
	int x,y;
	
	FORR(x,Xs) if(x<=R) {
		int y1=max(SD+x,D);
		int y2=min(SU+x,U);
		//cout<<"!"<<x<<" "<<y1<<" "<<y2<<endl;
		if(x==0&&y1==0) y1++;
		if(y1<=y2) return {x,y1};
	}
	FORR(y,Ys) if(y<=U) {
		int x1=max(y-SU,L);
		int x2=min(y-SD,R);
		//cout<<"!"<<x1<<":"<<x2<<" "<<y<<endl;
		if(x1==0&&y==0) x1++;
		if(x1<=x2) return {x1,y};
	}
	
	return {-1<<30,-1<<30};
}
/*
BBBBBBBBBBBBBBBBBBBBBBBBBBNNNNNNNNNNNN
32 24 12
14 10 
29 4

26 12
*/
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		FORR(c,s) {
			if(c=='B') X[i]++;
			else Y[i]++;
		}
		//cout<<X[i]<<" "<<Y[i]<<endl;
	}
	
	int ret=(1<<20)-1;
	for(i=19;i>=0;i--) {
		auto num=hoge(ret-(1<<i));
		if(num.first>-1<<30) ret-=1<<i;
	}
	
	auto a=hoge(ret);
	cout<<ret<<endl;
	//cout<<a.first<<" "<<a.second<<endl;
	FOR(i,a.first) cout<<"B";
	FOR(i,a.second) cout<<"N";
	cout<<endl;
	
}

まとめ

方針が見つかればあとは…と思ったけど、これはこれでめんどいな。