これは思いつかなかった。
http://tenka1-2014-final-open.contest.atcoder.jp/tasks/tenka1_2014_final_c
問題
ATGCで構成された文字列がN個与えられる。
ただし、各文字列は最大1文字ワイルドカードを持つ。
N個の文字列すべてを含むような最短の文字列Xを1つ答えよ。
解法
まずはワイルドカードを無視して考える。
いきなりEditorialを参照すると、各文字列はできるだけ左に入りすることが望ましい。
よって、bitmaskで処理済みの文字列を管理しつつ、一番右端に来ている文字列を状態として持ち、文字列長を最小化していく。
新しい文字列を追加する場合、右端が更新される場合とされない場合(短い文字列を追加すると、左端は他の文字列より右にあるが、右端は他の文字列より左に来る場合がある)に注意。
次にワイルドカード処理だが、ワイルドカードは1文字列1個しかないので、先に4通り文字列を生成してしまえば好い。
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; }
まとめ
左端にどんどん詰めていけば良い、とわかれば容易だが、本番それに気づかなかった。