dwangoプログラミングコンテスト本選 : B - コメント

こういう固有のネタをうまく問題にしてるのはいいね。
http://dwango2015-honsen.contest.atcoder.jp/tasks/dwango2015_finals_2

問題

N個の文字列S[i]を動画にコメントとして流す。
各文字列は１秒ずつタイミングをずらして流される。
また、各文字列は動画に登場後、1文字/秒の速さで画面左に流れていく。

各文字列を流す順番を適切に設定することで、動画上のある位置に同じ文字が並ぶことはあるか。

解法

Sが条件を満たしている場合、P[i]を0～(N-1)のpermutationとして、S[P[0]][x]=S[P[1]][x-1]=S[P[2]][x-2]=...=S[P[N-1]][x-(N-1)]=cとなる整数x・文字c・Permutation Pが存在することになる。
逆に考えると、S[i][x-j]=cである場合、P[i]=jで合っても良く、逆にS[i][x-j]!=cならP[i]=jであってはならない。

こう考えると、この問題は2部マッチング問題に置き換えることができる。
左右にN個ずつの頂点を置き、S[i][x-j]=cなら、左側i番目と右側jを結ぶ。
x,cを総当たりし、この２部グラフが完全マッチングする場合があるなら条件を満たせる。

ただ、愚直に２部マッチングを毎回行うと、xが(maxS-N)通り、cが小文字分26通りで計26*(maxS-N)回行う羽目になりTLEする。

ここで、xを１つずらした場合、辺が増減するのは最大N本で残り(最大N*(N-1)本)は前と同じである。
よって前回のマッチング時のグラフから差分だけ辺を増減させると、グラフ構築の手間が減り時間内に間に合う。

int N;
string S[300];

const int MV=500;
vector<int> E[MV+1];
int match[MV+1], vis[MV+1];

int bip_dfs(int v) {
	int i;
	vis[v]=1;
	FOR(i,E[v].size()) if(vis[E[v][i]]==0) {
		int tar=E[v][i];
		if(match[tar]<0 || (vis[match[tar]]==0 && bip_dfs(match[tar]))) {
			match[tar]=v;
			match[v]=tar;
			return 1;
		}
	}
	return 0;
}

int bip_match(int NV){
	int i,nmatch=0;
	MINUS(match);
	FOR(i,NV) if(match[i]==-1) { ZERO(vis); nmatch += bip_dfs(i);}
	return nmatch;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	
	FOR(i,26) {
		FOR(j,100003) {
			int ng=0;
			FOR(x,N) if(S[x].size()<=j) ng++;
			if(ng) break;
			ll ma[4]={};
			FOR(x,N) {
				E[x].clear();
				E[N+x].clear();
				FOR(y,N) if(j+y<S[x].size() && S[x][j+y]=='a'+i) {
					E[x].push_back(N+y),E[N+y].push_back(x);
					ma[y/60] |= 1LL<<(y%60);
				}
				if(E[x].empty()) {
					ng++;
					break;
				}
			}
			if(ng) continue;
			for(y=N;y<=199;y++) ma[y/60] |= 1LL<<(y%60);
			if(ma[0]!=(1LL<<60)-1) continue;
			if(ma[1]!=(1LL<<60)-1) continue;
			if(ma[2]!=(1LL<<60)-1) continue;
			if(ma[3]!=(1LL<<20)-1) continue;
			
			x=bip_match(2*N);
			if(x==N) {
				cout<<"YES"<<endl;
				return;
			}
			j+=(N-x)-1;
		}
		
	}
	cout<<"NO"<<endl;
}

まとめ

グラフの差分だけ再構築するというアイデアは面白いな。