山田山本問題 [天下一プログラマーコンテスト2016予選A : C]

問題

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualC_a

N個の文字列の組AiとBiが与えられる。
辞書順で Ai のほうが Bi よりも小さいようにアルファベット順を変えたい。
全ての文字列について、辞書順が満たされるようなアルファベット順を答えよ。
無ければ"-1"、複数あればその中で辞書順（普通の）最小のものだけ答える。

1 <= N <= 10^3
1 <= |Ai|,|Bi| <= 10^3

考察

1. 文字列とあるが実際に関係してくるのは、頭から違いを見ていって最初に違う文字だけ
2. それを各組確かめていって、「E[i][j] = iのほうがjより先に来ないと行けない」を作ります
（文字a,b,...,zは0,1,...,25としておきます）
3. このときに片方がもう片方の部分文字列の時には、Aiの方が大きければ辞書順変更ができないので"-1"
（親切にも例4にある）

4. これをどうするかなーという所ですね
5. 真っ先に思いつきそうなのでトポロジカルソートです
6. 「iがjよりも先 -> iからjへの有向辺」という考えはよく使われます
7. うまい具合にトポロジカルソートしてやれば良さそうですが、にわかの俺は無理でした

8. 凄い考えると違う方法があったので、そっち使いました
9. アルファベット順を先頭から順に決める方法を取りました
10. 先頭から決めていくので26回の決定があるわけですが、毎回aから順番におけるかどうか考えてみます
11. ある文字 c があり、これが置けるかどうかは、「これまでに置いたか」と「E[i][j]が満たされているか」をチェックするだけでいいです
12. 貪欲解な気がしますが、これで通せます

実装

http://tenka1-2016-quala.contest.atcoder.jp/submissions/823345

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
 
int N;
bool E[26][26];
//-----------------------------------------------------------------
string solve() {
	rep(i, 0, 26) rep(j, 0, 26) E[i][j] = false;
 
	rep(i, 0, N) {
		string A, B; cin >> A >> B;
		int cnt = 0;
		int len = min(A.size(), B.size());
		while (cnt < len) {
			if (A[cnt] != B[cnt]) break;
			cnt++;
		}
		if (cnt == len && A.size() > B.size()) return "-1";
		if (cnt == len) continue;
		
		int a = A[cnt] - 'a';
		int b = B[cnt] - 'a';
		E[a][b] = true;
	}
 
	bool flag[26];
	rep(i, 0, 26) flag[i] = false;
 
	vector<int> ans;
	rep(cnt, 0, 26) {
		rep(i, 0, 26) if(!flag[i]){
			bool ok = true;
			rep(j, 0, 26) if (E[j][i] && !flag[j]) ok = false;
			if (ok) {
				ans.push_back(i);
				flag[i] = true;
				break;
			}
		}
	}
 
	if (ans.size() != 26) return "-1";
 
	string ret = "";
	for (int i : ans) ret += char('a' + i);
	return ret;
}
//-----------------------------------------------------------------
int main() {
	cin >> N;
	cout << solve() << endl;
}