HackerRank HourRank 28 : B. The Most Elegant Sequence

存在を完全に忘れていて遅刻した。
https://www.hackerrank.com/contests/hourrank-28/challenges/the-most-elegant-sequence

問題

数値だけで表現される文字列の列S[i]が与えられる。S[i]にはそれぞれスコアB[S[i]]が設定されている。
0～9の数字がそれぞれ最大Q回まで使えるとき、S[i]の部分集合を考える。
そのとき、0～9の登場回数の和はそれぞれQ回以下でなければならない。

S[i]の部分集合のうちある並びTを考える。
このとき、この並びTのスコアはB[T[0]] + (B[T[0]] xor B[T[1]]) + (B[T[1]] xor B[T[2]])...とする。
スコアの最大値を求めよ。

解法

Tに新たな文字列を追加するとき、スコアに影響するのは追加前の最終要素だけである。
また、各文字列は1回ずつまでしか使えないので、bitDPがよさそうである。
よって、Tに含まれる要素の集合と最終要素をキーとして状態を管理し、bitDPすればO(N^2*2^N)で解ける。

int N,Q;
string S[20];
int B[20];
int cnt[20][10];

int dp[1<<19][19];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>B[i];
	FOR(i,N) {
		cin>>S[i];
		FORR(c,S[i]) cnt[i][c-'0']++;
	}
	FOR(i,1<<N) FOR(j,N) dp[i][j]=-1<<30;
	dp[0][0]=0;
	
	int ma=0;
	for(int mask=1;mask<1<<N;mask++) {
		int C[10]={};
		FOR(i,N) if(mask&(1<<i)) {
			FOR(j,10) C[j]+=cnt[i][j];
		}
		FOR(j,10) if(C[j]>Q) break;
		if(j<10) continue;
		
		if(__builtin_popcount(mask)==1) {
			FOR(i,N) if(mask&(1<<i)) {
				dp[mask][i]=B[i];
				ma=max(ma,dp[mask][i]);
			}
		}
		else {
			FOR(i,N) if(mask&(1<<i)) {
				FOR(j,N) if(i!=j && (mask&(1<<j))) dp[mask][i]=max(dp[mask][i],dp[mask^(1<<i)][j] + (B[j]^B[i]));
				ma=max(ma,dp[mask][i]);
			}
		}
		
	}
	cout<<ma<<endl;
}

まとめ

なんか問題設定が無駄にややこしいなぁ。