Codeforces #302 Div1 C. Remembering Strings

本番近い発想まで行ったのになぁ。
http://codeforces.com/contest/543/problem/C

問題

M文字であるN個の文字列S[i]が与えられる。
また、S[i][j]を別の文字にするコストA[i][j]が与えられる。

各文字列S[i]について、「j文字目がS[i][j]であるような文字列はS[i]以外にない」というjが最低1個含まれるようにしたい。
必要な最小コストを求めよ。

解法

「j文字目がS[i][j]であるような文字列はS[i]以外にない」という状態を作るには以下の何れかの方法がある。

• S[i][j]をコストA[i][j]かけて書き換える。
• 文字が重複しそうな文字列を全て書き換える。すなわちS[x][j]=S[i][j]となる文字列S[x]に対し、コストA[x][j]が最大のもの以外をA[x][j]掛けて書き換える。
  • この手順を取った場合、副作用としてS[x]もすべて題意の条件を満たせるようになる。

あとは、N個の文字列が『「j文字目がS[i][j]であるような文字列はS[i]以外にない」というjが最低1個含まれる』という状態にあるかどうかをbitmaskを用いて状態を保持し、各文字位置jにおいて上記アプローチのどちらかを取った場合の最小コストをDPで更新していけば良い。

以下のコードでは、前半パートで２つ目のアプローチのコストを先にもとめて、後半パートでBitDPをしている。

int N,M;
string S[30];
int A[30][30];
int exc[30][256];
int exm[30][256];
ll dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>S[i];
	FOR(y,N) FOR(x,M) cin>>A[y][x];
	
	FOR(i,M) {
		for(j='a';j<='z';j++) {
			int ma=0, tot=0;
			FOR(x,N) if(S[x][i]==j) {
				exm[i][j] |= 1<<x;
				ma=max(ma,A[x][i]);
				tot += A[x][i];
			}
			exc[i][j] = tot-ma;
		}
	}
	FOR(i,1<<N) dp[i]=1LL<<50;
	dp[(1<<N)-1]=0;
	for(int mask=(1<<N)-1;mask>0;mask--) {
		int mid=0;
		while((mask&(1<<mid))==0) mid++;
		FOR(i,M) {
			dp[mask ^ (1<<mid)] = min(dp[mask ^ (1<<mid)], dp[mask]+A[mid][i]);
			dp[mask & ~exm[i][S[mid][i]]] = min(dp[mask & ~exm[i][S[mid][i]]], dp[mask]+exc[i][S[mid][i]]);
		}
	}
	cout<<dp[0]<<endl;
}

まとめ

本番グラフとBitDPで迷ったんだよな…。