この手の問題すき。すきだから記事を書いてしまう。
問題概要
原文を参照してください → C: 山田山本問題 - 天下一プログラマーコンテスト2016予選A | AtCoder
解説
まずは、 
を 
より辞書順で小さくするには、どのような戦略が必要かを考えてみましょう。
辞書順で大きく / 小さくなる場合は
- 両方の文字列の
文字目まで一致しており、
文字目が異なっている場合
- 片方の文字列が、もう片方の文字列の prefix と完全一致している場合
の、 
通りしかありません。
番目については、各文字列の 文字目を見て、どの文字がどの文字よりも辞書順で小さくなる必要があるかを見れば十分です。例えば、 "yamamoto" と "yamada" は 
文字目まで一致していますが、
文字目が異なっているので、 文字目のアルファベットについて注目すれば十分であり、この場合だと 'm' が 'd' よりも辞書順で小さく定義される必要があります。
番目については、 番目と違って辞書順の定義を変えたらどうにかなるものではありません。どういうことなのか、もう少し掘り下げてみましょう。
文字列 
が、文字列 
の prefix と一致しているとします。
"yama"、 
"yamamoto" などがその例です。このとき、 は よりも辞書順で必ず小さくなります。 これを踏まえると、
- が の prefix と一致する場合は、条件を満たすアルファベットの順番が存在しない
と言えます。
さて、辞書順で 大きい / 小さい / そもそも不可能 かどうかの判定はこれで良いことが分かりましたが、あとはどのように構築すればよいでしょうか？
これは、各アルファベットを頂点とみなし、「アルファベット 
が 
よりも辞書順で小さく定義される必要がある」という情報を、 
の有向辺を張って*1 表現することで、糸口が見えてきます。この有向グラフが DAG であることと、条件を満たすアルファベットの順番が存在することが同値なので、トポロジカルソートをすれば良いです。
ただし、適当にトポロジカルソートをやってしまうと辞書順最小が果たせないため、少し工夫をします。例えば Kahn のアルゴリズムでは入次数 
の頂点を queue に入れてよしなにトポロジカルソートをやると思うのですが、この queue を priority_queue に変えることで、現時点で使える頂点のうち常に辞書順最小のものが手に入るため、辞書順最小のアルファベット列が構築できます。
template <typename T>
vector<int> tpsort_Kahn(const vector< vector< Edge<T> > > &g) {
const int V = g.size();
vector<int> indeg(V, 0);
priority_queue< int, vector<int>, greater<int> > S;
rep(i,0,V) rep(j,0,g[i].size())
indeg[ g[i][j].to ]++;
repr(i,V-1,0) if(indeg[i] == 0) S.push(i);
vector<int> ans;
while(S.size() > 0) {
int u = S.top(); S.pop();
ans.push_back(u);
rep(i,0,g[u].size()) {
indeg[ g[u][i].to ]--;
if(indeg[ g[u][i].to ] == 0)
S.push( g[u][i].to );
}
}
return ans;
}
int keynum(string a, string b) {
int N = a.length(), M = b.length();
rep(i,0,min(N,M)) {
if(a[i] != b[i]) return i;
}
if(N < M) return -2;
else return -1;
}
signed main() {
int N; cin >> N;
Graph<int> G(26);
bool ng = false;
rep(i,0,N) {
string a, b; cin >> a >> b;
int key = keynum(a, b);
if(key == -1) ng = true;
else if(key >= 0) {
int p = a[key] - 'a', q = b[key] - 'a';
G[p].push_back(Edge<int>(q, 1));
}
}
vector<int> tp = tpsort_Kahn(G);
if(tp.size() != 26) ng = true;
if(ng) cout << -1 << endl;
else {
string ans = "";
rep(i,0,tp.size()) {
ans += ('a' + tp[i]);
}
cout << ans << endl;
}
return 0;
}
ライブラリを少しいじらないと正解にならない問題ほんとすき。
