天下一プログラマーコンテスト2014 決勝 : C - シークエンサー

これは思いつかなかった。
http://tenka1-2014-final-open.contest.atcoder.jp/tasks/tenka1_2014_final_c

問題

ATGCで構成された文字列がN個与えられる。
ただし、各文字列は最大１文字ワイルドカードを持つ。

N個の文字列すべてを含むような最短の文字列Xを１つ答えよ。

解法

まずはワイルドカードを無視して考える。

いきなりEditorialを参照すると、各文字列はできるだけ左に入りすることが望ましい。
よって、bitmaskで処理済みの文字列を管理しつつ、一番右端に来ている文字列を状態として持ち、文字列長を最小化していく。

新しい文字列を追加する場合、右端が更新される場合とされない場合（短い文字列を追加すると、左端は他の文字列より右にあるが、右端は他の文字列より左に来る場合がある）に注意。

次にワイルドカード処理だが、ワイルドカードは１文字列１個しかないので、先に４通り文字列を生成してしまえば好い。

int N;
string S[60];
int V[50][50];
int dp[1<<12][50];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		FOR(j,s.size()) FOR(k,4) {
			if(s[j]=='.') S[i*4+k] += "ATGC"[k];
			else S[i*4+k]+=s[j];
		}
	}
	
	FOR(x,N*4) FOR(y,N*4) FOR(V[x][y],S[x].size()+1) {
		l = min(S[y].size(),S[x].size()-V[x][y]);
		if(S[y].substr(0,l)==S[x].substr(V[x][y],l)) break;
	}
	
	FOR(x,1<<12) FOR(y,50) dp[x][y]=1000000;
	FOR(x,N*4) dp[1<<(x/4)][x]=S[x].size();
	
	int mask;
	FOR(mask,1<<N) FOR(x,N*4) if(mask & (1<<(x/4))) {
		FOR(y,N*4) if((mask & (1<<(y/4)))==0) {
			if(V[x][y]+S[y].size()>=S[x].size()) {
				dp[mask | (1<<(y/4))][y] = min(dp[mask | (1<<(y/4))][y],dp[mask][x]-(int)S[x].size()+V[x][y]+(int)S[y].size());
			}
			else {
				dp[mask | (1<<(y/4))][x] = min(dp[mask | (1<<(y/4))][x],dp[mask][x]);
			}
			
		}
	}
	int ret=10000000;
	FOR(x,N*4) ret=min(ret,dp[(1<<N)-1][x]);
	cout<<ret<<endl;
}

まとめ

左端にどんどん詰めていけば良い、とわかれば容易だが、本番それに気づかなかった。