Codeforces #691 Div1 D. Flip and Reverse

考察が難しい。
https://codeforces.com/contest/1458/problem/D

問題

01で構成される文字列Sが与えられる。
以下の処理を繰り返して得られる辞書順最小の文字列を答えよ。

• 01の登場回数が等しい連続部分文字列を選び、0,1を反転したのち左右を反転する。

解法

以下の有向グラフを考える。
v[i] := Sのprefix i文字における、(0の登場頻度)-(1の登場頻度)
とする。
この時、v[i]→v[i+1]に有向辺を張ろう。
v[*]は同じ値を複数の添え字で取ることになるので、これ多重辺ありのグラフとなる。

元の文字列に対応して辺の並びを選ぶと、オイラーパスが1つできる。
ここで、文字列に対し所定の処理を行うことは、オイラーパス内に含まれる閉路を逆順にすることに相当する。
言い換えると、このグラフにおけるどんなオイラーパスも、対応する文字列を構成可能といえる。

よって、あとはオイラーパスを構成する際に、頂点番号が増える方向の辺を優先的に選択するようにすれば、対応する文字列では0が手前に来るので、辞書順で小さい文字列を得ることができる。

int T,N;
string S;

template<int MV> class DirectedEulerPath {
public:
	int NV;
	vector<int> path;
	vector<int> E[MV];
	void add_path(int x,int y) { E[x].push_back(y);}
	
	void init(int NV){
		this->NV=NV;
		for(int i=0;i<NV;i++) E[i].clear();
		path.clear();
	}
	void dfs(int cur) {
		while(E[cur].size()) {
			int e=E[cur].back();
			E[cur].pop_back();
			dfs(e);
		}
		path.push_back(cur);
	}
	
	bool GetPath(int root=-1) {
		assert(NV);
		int te=0,i;
		vector<int> deg(NV);
		FOR(i,NV) {
			sort(ALL(E[i]));
			te += E[i].size();
			deg[i]+=E[i].size();
			FORR(e,E[i]) deg[e]--;
		}
		int d0=0,s=0;
		FOR(i,NV) {
			if(deg[i]>1 || deg[i]<-1) return false;
			if(deg[i]==0) d0++;
			if(deg[i]==1) s=i;
		}
		if(d0!=NV && d0+2!=NV) return false;
		s=root;
		dfs(s);
		reverse(path.begin(),path.end());
		return path.size()==te+1;
	}
};

DirectedEulerPath<1202020> dep;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S;
		N=S.size();
		int cur=0;
		int mi=0,ma=0;
		FORR(c,S) {
			if(c=='0') cur++;
			else cur--;
			mi=min(mi,cur);
			ma=max(ma,cur);
		}
		dep.init(ma-mi+1);
		cur=-mi;
		FORR(c,S) {
			if(c=='0') {
				dep.add_path(cur,cur+1);
				cur++;
			}
			else {
				dep.add_path(cur,cur-1);
				cur--;
			}
		}
		assert(dep.GetPath(-mi));
		string R;
		FOR(i,N) {
			if(dep.path[i]<dep.path[i+1]) R+='0';
			else R+='1';
		}
		cout<<R<<endl;
		
	}
}

まとめ

この言い換え賢いな…。