kmjp's blog

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

Codeforces #315 Div1 C. New Language

Codeforces

本番あと一歩で間に合わなかった。
http://codeforces.com/contest/568/problem/C

問題

あるL種のアルファベットを用いた言語がある。
この言語では、アルファベットは子音と母音に分類できる。

この言語においてN文字の単語を考える際、以下の形のルールがM個ある。

  • pos1文字目が(子音または母音)に一致する場合、pos2文字目も(子音または母音)でなければならない。

この言語における単語Sが与えられる。
辞書順でS以降のN文字の単語のうち、この言語で有効な(ルールに違反しない)単語で辞書順最小のものを求めよ。

解法

まずルール自身に矛盾(すなわちどうやっても満たせないルール群)がないか考える。
これは各アルファベットの子音・母音に対応する2*L頂点の有効グラフを考え、ルールに対応する有向辺を引いたとき、子音と母音が同一連結成分に入らないかどうかで判断できる。

単語がルールに合致するかはO(M)で容易に判断できる。
よってあとは単語の生成の仕方を考えればよい。

元のSがそもそもこの言語で有効ならそれを答える。
以下、S自身が有効でない場合、以下の順で候補を生成する。

  • 以下、iをNから0まで逆順にループする。
    • Sのうち(i-1)文字目まではSと一致する場合を考える。
    • Sのうちi文字目は以下の２通りを順に試す。
      • S[i]の次のアルファベット
      • (S[i]の次のアルファベット)の後に来る、子音母音が異なる最初のアルファベット
    • あとはSの(i+1)文字目以降を探索することになるが、これも以下の２通りを順に試しつつDFSする。
      • 最初のアルファベットである'a'
      • 'a'の後に来る、子音母音が異なる最初のアルファベット

1文字ずつDFSする際、毎回単語のうち確定部分が有効かどうかをチェックする枝刈りを行うとTLEを回避できる。

class SCC {
public:
	static const int MV = 5000;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

string S,R;
int L,N,M;
int nex[27];
vector<pair<int,int> > PP[202][2];

vector<int> isok(vector<int> V) {
	int i;
	FOR(i,N) if(V[i]!=2) {
		FORR(r,PP[i][V[i]]) {
			if(V[r.first]==2) V[r.first]=r.second;
			if(V[r.first]!=r.second) return vector<int>();
		}
	}
	return V;
}

void dfs(int cur,vector<int> V) {
	int i;
	if(cur==N) {
		cout<<S<<endl;
		exit(0);
	}
	
	FOR(i,2) {
		if(i&&nex[0]==L) break;
		S[cur]='a' + (i?nex[0]:0);
		vector<int> V2=V;
		if(V2[cur]!=2 && V2[cur]!=R[0]^i) continue;
		V2[cur]=R[0]^i;
		V2=isok(V2);
		if(V2.size()) dfs(cur+1,V2);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	SCC scc;
	
	cin>>R;
	L=R.size();
	FORR(r,R) r=(r=='V');
	FOR(i,L) {
		for(nex[i]=i+1;nex[i]<L;nex[i]++) if(R[nex[i]]!=R[i]) break;
	}
	cin>>N>>M;
	
	scc.init(2*N);
	FOR(i,M) {
		int p0,p1;
		string t0,t1;
		cin>>p0>>t0>>p1>>t1;
		PP[p0-1][t0=="V"].push_back({p1-1,t1=="V"});
		scc.add_edge((p0-1)*2+(t0=="V"),(p1-1)*2+(t1=="V"));
	}
	cin>>S;
	
	scc.scc();
	FOR(i,N) if(scc.GR[i*2]==scc.GR[i*2+1]) return _P("-1\n");
	
	vector<int> V(N,0),ret;
	FOR(i,N) V[i]=R[S[i]-'a'];
	ret=isok(V);
	if(ret.size()) {
		cout<<S<<endl;
		return;
	}
	
	for(i=N-1;i>=0;i--) {
		FOR(j,2) {
			if(j==0) {
				if(S[i]-'a'+1>=L) continue;
				S[i]++;
			}
			else {
				if(nex[S[i]-'a']>=L) continue;
				S[i]='a'+nex[S[i]-'a'];
			}
			
			V.clear();
			FOR(x,i+1) V.push_back(R[S[x]-'a']);
			for(x=i+1;x<N;x++) V.push_back(2);
			
			V=isok(V);
			if(V.size()) dfs(i+1,V);
		}
	}
	_P("-1\n");
}

まとめ

本番ルールの矛盾検出には気づいていなかったのでどのみちACは無理だったか。
文字列の終盤にルールの矛盾があると、今回の解法はO(2^N)程度かかるのでTLEするのよね。