kmjp's blog

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

Codeforces #290 Div1 A. Fox And Names

3問早解きでそこそこいい順位に入った。
http://codeforces.com/contest/512/problem/A

問題

この問題に置いて、アルファベットの順序は一般的なものではないとする。
N個の文字列S[i]が与えられる。
S[i]が辞書順に並んでいるとみなせるようなアルファベット順は存在するか。
存在するならそれを示せ。

解法

S[i]とS[i+1]を比較し、先頭から初めて異なる文字が現れるのがx文字目とする。
その場合、S[i][x]の文字はS[i+1][x]の文字より前に来る、という順序関係が得られる。

あとはこれらの順序関係をトポロジカルソートできればそれが答え。
順序関係が循環している場合、トポロジカルソートに失敗し、解無しとなる。

class TopologicalSort {
public:
	static const int MV = 100;
	int NV,NIE[MV];
	vector<int> OutEdge[MV];
	
	TopologicalSort(int nv){init(nv);}
	void init(int nv) { NV=nv; for(int i=0;i<NV;i++) OutEdge[i].clear(), NIE[i]=0;}
	void add_edge(int x,int y) { OutEdge[x].push_back(y); NIE[y]++;}
	
	vector<int> sort() {
		int i,nv=0;
		vector<int> NI,R;
		NI.reserve(NV);
		R.reserve(NV);
		queue<int> S;
		FOR(i,NV) {
			NI.push_back(NIE[i]);
			nv+=OutEdge[i].size();
			if(NIE[i]==0) S.push(i);
		}
		
		while(!S.empty()) {
			int cur=S.front();
			S.pop();
			R.push_back(cur);
			ITR(it,OutEdge[cur]){
				nv--;
				if(--NI[*it]==0) S.push(*it);
			}
		}
		if(nv) return vector<int>();
		return R;
	}
};

int N;
string S[1010];
int mat[27][27];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	FOR(i,N-1) {
		bool hoge=false;
		FOR(j,min(S[i].size(), S[i+1].size())) {
			if(S[i][j]!=S[i+1][j]) {
				mat[S[i][j]-'a'][S[i+1][j]-'a']=1;
				hoge=true;
				break;
			}
		}
		if(hoge==false && S[i].size()>S[i+1].size()) return _P("Impossible\n");
	}
	
	TopologicalSort ts(26);
	FOR(i,26) FOR(j,26) if(mat[i][j]) ts.add_edge(i,j);
	vector<int> v=ts.sort();
	if(v.empty()) {
		_P("Impossible\n");
	}
	else {
		FOR(i,26) _P("%c",'a'+v[i]);
		_P("\n");
	}
}

まとめ

本番は最終的にはACだったもののかなり遠回りな解法をしてしまった。
無駄に再帰とかして、順序関係を求めるのに手間取った上1WAしてしまった。