yukicoder : No.562 超高速一人かるた small

なんとか解けて良かったです。
https://yukicoder.me/problems/no/562

問題

文字列S[i]が書かれたN枚のかるたがある。
各文字列は互いに異なっている。

読み手がN枚のかるたをランダムな順で読んでいくので、対応する取り札を取ることを考える。
取り手が取り札を取るには、読み手が文字列の先頭a文字を読んだ時点で、残った取り札のうち取り札が一意に定まるまで読み上げるのを待たなければならない。
その時疲労度がaたまる。

N枚中K枚まで読んだ時点の総疲労度の期待値×を答えよ。

解法

答えるのは(総疲労度の期待値)×(組み合わせ数)なので、あり得る読み上げ順全パターンにおける疲労度の総和を計算すればよい。

まず、かるたの対(a,b)に対して両者を区別するために読むべき最小文字列数f(a,b)を前処理で全通り求めよう。なおf(a,a)=1とする。
残されたかるたの集合をPとするとき、次にa番目のかるたが読まれた場合の疲労度はとなる。

あとはBitDPで、すでに読み上げられた取り札の集合に対し、1枚ずつ新たな札が読まれた場合の疲労度を計算して行こう。

int N;
string S[202];
ll dp[1<<20];
ll mo=1000000007;
ll fact[21];
ll ret[21];
int cost[20][20];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	FOR(x,N) FOR(y,N) {
		cost[x][y]=1;
		while(cost[x][y]<=S[x].size() && cost[x][y]<=S[y].size() && S[x][cost[x][y]-1]==S[y][cost[x][y]-1]) cost[x][y]++;
	}
	
	fact[0]=1;
	FOR(i,N) fact[i+1]=fact[i]*(i+1)%mo;
	
	
	for(int mask=0;mask<1<<N;mask++) {
		int b=__builtin_popcount(mask);
		ret[b] += dp[mask];
		FOR(i,N) if((mask&(1<<i))==0) {
			int ma=1;
			FOR(x,N) if((mask&(1<<x))==0 && (i!=x)) ma=max(ma,cost[i][x]);
			(dp[mask|(1<<i)] += dp[mask]+ma*fact[b])%=mo;
		}
	}
	
	for(i=1;i<=N;i++) cout<<ret[i]%mo<<endl;
	
}

まとめ

こちらはすんなりですね。