TopCoderOpen 2017 New Round3B Easy ChromosomalCrossover

なんとか1Chal取ったのでレートを割と回復できた。
https://community.topcoder.com/stat?c=problem_statement&pm=14685

問題

２つの同じ長さの文字列A,Bが与えられる。
A,Bのprefixを選びswapするという処理が任意回数行えるとする。
A,B中における最長連続一致文字列の長さを求めよ。

解法

A[0..i]とB[0..i]をswap後、A[0..(i-1)]とB[0..(i-1)]をswapすると結局A[i],B[i]だけswapされた状態になる。
よってprefixの制限は無視し、任意の位置iについてA[i],B[i]はswap可能であると考えてよい。

さて、両部分文字列の開始位置が同じ場合は自明なので先にチェックするとして、開始位置がずれる場合を考えよう。
最長連続一致文字列を取り出すに当たり、両文字列の始点A[x],B[y]および長さlを総当たりし、そのようなswapがあり得るかを考えよう。
d=y-xとするとA[i]==B[i+d]という関係が成り立つようにA[j]とB[j]のswapをしなければならない。
A[i]==B[i+d]とするならA[i+d]==B[i+2d]としなければならない。

上記関係はすべて二部グラフのマッチング問題に置き換えることができるので、二部グラフの最大マッチングで検証することができる。
DPでも解けるようだ。

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 205;
	vector<edge> E[MV];
	int vis[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};

class ChromosomalCrossover {
	public:
	int maximalLength(string A, string B) {
		int N=A.size();
		
		int ma=0,x,y;
		FOR(x,N) {
			for(int len=1;x+len<=N;len++) {
				if(A[x+len-1]!=B[x+len-1]) break;
				ma=max(ma,len);
			}
		}
		FOR(y,N) FOR(x,y) {
			int dif=y-x;
			for(int len=ma+1;y+len<=N;len++) {
				MaxFlow_Ford<int> mf;
				for(int i=x;i<y+len;i++) {
					if(i%(2*dif)<dif) {
						if(i<y || i>=x+len) {
							mf.add_edge(200,i,1);
						}
						else {
							mf.add_edge(200,i,2);
						}
						mf.add_edge(i,100+i*2,1);
						mf.add_edge(i,100+i*2+1,1);
						
						if(i-dif>=x) {
							if(A[i]==A[i-dif]) mf.add_edge(100+i*2,100+(i-dif)*2,1);
							if(B[i]==A[i-dif]) mf.add_edge(100+i*2+1,100+(i-dif)*2,1);
							if(A[i]==B[i-dif]) mf.add_edge(100+i*2,100+(i-dif)*2+1,1);
							if(B[i]==B[i-dif]) mf.add_edge(100+i*2+1,100+(i-dif)*2+1,1);
						}
						if(i+dif<y+len) {
							if(A[i]==A[i+dif]) mf.add_edge(100+i*2,100+(i+dif)*2,1);
							if(B[i]==A[i+dif]) mf.add_edge(100+i*2+1,100+(i+dif)*2,1);
							if(A[i]==B[i+dif]) mf.add_edge(100+i*2,100+(i+dif)*2+1,1);
							if(B[i]==B[i+dif]) mf.add_edge(100+i*2+1,100+(i+dif)*2+1,1);
						}
					}
					else {
						if(i<y || i>=x+len) {
							mf.add_edge(i,201,1);
						}
						else {
							mf.add_edge(i,201,2);
						}
						mf.add_edge(100+i*2,i,1);
						mf.add_edge(100+i*2+1,i,1);
					}
				}
				int ret=mf.maxflow(200,201);
				if(ret==len) {
					ma=len;
				}
				else break;
			}
		}
		
		return ma;
	}
}

まとめ

だいぶ手間取ったけど1Chalのおかげで助かった。