読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 689 Div2 Hard ColorfulGardenHard

SRM

これDiv2とはいえ900ptでいいんじゃないかな…。
https://community.topcoder.com/stat?c=problem_statement&pm=14247

問題

文字列Gを並べ替えたい。
並べ替えた後の文字列のうち、その際以下の条件を満たすものは何通りか。

  • 同じ長さの文字列Fに対し、G[i]=F[i]となるiが1つもない
  • 隣接する要素は一致しない

なお、並べ替え方が異なっても、結果得られる文字列が同一の場合、1つと数える。

解法

Gの長さが短いので、bitDPで解こう。
先頭から1文字ずつ決めていく。
dp(bitmask,last) := Gのうちbitmaskのたったビットに相当する文字列を使用し、かつ最後がG[last]であるような文字列の数

1点注意点は、同一文字列は多重カウントできない点。
これは同種の文字を使う際はそのうち左端の未使用文字から順に使う、といったルールを適用しながらDPすればよい。

ll dp[1<<16][16];
ll mo=1000000007;

class ColorfulGardenHard {
	public:
	int count(string G, string F) {
		int i,j;
		int N = G.size();
		
		sort(G.begin(),G.end());
		ZERO(dp);
		
		FOR(i,N) if((i==0 || G[i]!=G[i-1]) && G[i]!=F[0]) dp[1<<i][i]=1;
		for(int mask=1;mask<1<<N;mask++) {
			int num=__builtin_popcount(mask);
			FOR(i,N) if((mask&(1<<i)) && dp[mask][i]) {
				FOR(j,N) {
					if(mask&(1<<j)) continue;
					if(G[i]==G[j]) continue;
					if(j&&G[j]==G[j-1]&&((mask&(1<<(j-1)))==0)) continue;
					if(F[num]==G[j]) continue;
					(dp[mask | (1<<j)][j] += dp[mask][i])%=mo;
				}
			}
		}
		ll tot=0;
		FOR(i,N) tot += dp[(1<<N)-1][i];
		return tot%mo;
		
	}
}

まとめ

妙に簡単。

広告を非表示にする