Codeforces ECR #060 : F. Crisp String

手間取ったけど解けて良かったね。
https://codeforces.com/contest/1117/problem/F

問題

N文字の文字列Sが与えられる。
また、p種の文字の対について、それらが隣接可能かどうかの行列が与えられる。

Sについて１つの種類の文字を選びそれらを消し残りを詰める、という処理を任意回数行えるとする。
その過程において、隣接不可能な文字が隣接するケースを経由せずに到達できる最短の文字列は何文字か。

解法

まず元の文字列から、残された文字のbitmaskに対し、その状態が条件に反しないかを求めよう。
それらが求まれば、初期状態から1つずつbitを落とし、到達可能なうち総文字数の最小値を求めればよい。

あとは条件を反しないbitmaskの列挙方法である。
ここでは逆に条件に反するbitmaskを削って行こう。

今S[i]='a'とし、その後に登場する文字を始めて出た順に並べるとabcde...となったとする。
先にbcdを消した場合、aとeが隣接してしまう。この時入力の行列でaとeが隣接不可の場合、a,eが存在してb,c,dが存在しないケースは不可、となる。
このようにaとb、aとc、aとd…について間の文字が消えこれらが隣接するケースのうち、入力行列で禁止されている場合、bitmaskのうち条件を満たさないsub-bitmaskが列挙できる。
あとはそのsub-bitmaskを含むbitmaskは到達不可な状態とみなすことができる。

これ最初の手順がO(Np)で、その後がO(3^p)かな。

int N,P;
string S;
int A[17][17];
int nex[18];
int num[18];

vector<int> ngpat[1<<17];
int ok[1<<17];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P>>S;
	FOR(i,P) nex[i]=N;
	FORR(c,S) {
		c-='a';
		num[c]++;
	}
	FOR(y,P) FOR(x,P) cin>>A[y][x];
	for(i=N-1;i>=0;i--) {
		vector<pair<int,int>> V;
		FOR(j,P) if(nex[j]<N) V.push_back({nex[j],j});
		sort(ALL(V));
		int fixed=(1<<P)-1-(1<<S[i]);
		int mat=1<<S[i];
		FORR(v,V) {
			if(v.second!=S[i]) {
				fixed ^= 1<<(v.second);
				mat^= 1<<(v.second);
			}
			if(A[S[i]][v.second]==0) ngpat[fixed].push_back(mat);
			if(v.second==S[i]) break;
			mat^= 1<<(v.second);
		}
		nex[S[i]]=i;
	}
	
	int mask;
	FOR(mask,1<<P) ok[mask]=1;
	FOR(mask,1<<P) {
		sort(ALL(ngpat[mask]));
		ngpat[mask].erase(unique(ALL(ngpat[mask])),ngpat[mask].end());
		for(int submask=mask; submask>=0; submask--) {
			submask&=mask;
			FORR(p,ngpat[mask]) ok[submask|p]=0;
		}
	}
	
	int ma=0;
	FOR(i,P) ma+=num[i];
	for(mask=(1<<P)-2;mask>=0;mask--) if(ok[mask]) {
		ok[mask]=0;
		FOR(i,P) if((mask&(1<<i))==0 && ok[mask|(1<<i)]) ok[mask]=1;
		if(ok[mask]) {
			int sum=0;
			FOR(i,P) if(mask&(1<<i)) sum+=num[i];
			ma=min(ma,sum);
		}
	}
	cout<<ma<<endl;
}

まとめ

計算量自信なかったけど通ってよかった。