Codeforces ECR #047 : G. Allowed Letters

あと少しだったのに。
http://codeforces.com/contest/1009/problem/G

問題

a～fの６種類の文字で構成される文字列Sが与えられる。
Sを並べ替えてできる文字列のうち、辞書順最小の物を求めよ。
ただし、一部の位置に関して、配置可能な文字が指定される場合がある。

解法

辞書順最小な文字列を構築する問題なので、定番テクということで先頭位置から順に
「a～fを置くことを順に試みたとき、以降の位置が条件を満たす配置が可能か判定する」
ということを行えばよい。

あとは「以降の位置が条件を満たす配置が可能か判定する」が高速に行えればよい。
問題の入力から、各位置に対し置ける文字種別のbitmaskがわかる。
累積和の要領で、その位置以降において種別がbitmaskとなる箇所の数を求めておこう。

さらに前述のbitmask毎の位置の総数について、高速ゼータ変換の要領で「bitmaskに含まれるbitmaskの位置の総数」を求めておく。
あとはホールの定理の要領で、各bitmaskについて、それに含まれるbitmaskの位置の総数が、利用できる文字数以下であることを確認すればよい。

string S;
int N,M;
int C[6];
int mask[101010];
int pat[101010][64];
string T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FORR(c,S) C[c-'a']++;
	FOR(i,N) mask[i]=(1<<6)-1;
	
	cin>>M;
	FOR(i,M) {
		cin>>x>>s;
		x--;
		mask[x]=0;
		FORR(c,s) mask[x] |= 1<<(c-'a');
	}
	for(i=N-1;i>=0;i--) {
		FOR(x,64) pat[i][x]=pat[i+1][x];
		pat[i][mask[i]]++;
	}
	FOR(i,N) {
		FOR(x,6) {
			FOR(y,64) if(y&(1<<x)) pat[i][y] += pat[i][y^(1<<x)];
		}
	}
	
	FOR(i,N) {
		FOR(j,6) if(C[j] && (mask[i]&(1<<j))) {
			C[j]--;
			int m;
			FOR(m,64) {
				int tot=0;
				FOR(x,6) if(m&(1<<x)) tot+=C[x];
				if(tot<pat[i+1][m]) break;
			}
			
			if(m==64) {
				T+='a'+j;
				break;
			}
			
			
			C[j]++;
		}
		if(j==6) return _P("Impossible");
	}
	cout<<T<<endl;
	
}

まとめ

シンプルな題材だけど、高速ゼータ変換とかホールの定理とか小技が効いて気持ちよく解ける問題。