http://codeforces.com/contest/889/problem/B
N個の文字列がある。
この文字列に対して、以下の条件を満たす文字列を構築せよ。
- 全ての部分列について、出現回数を考える
- その中で出現回数が最大の部分文字列を全て集めると与えられた文字列を全て含む集合となる
- 満たす文字列が作れないなら"NO"と答える
- もし作れるなら、その中で長さが最小で、かつ、辞書順最小のものを答える
分かりにくいので例も少し解説。
- サンプル1
- 「cfmailru」は全ての部分文字列の出現回数が1なので、OK
- サンプル2
- 「kekpreceqcheburek」と作ると、出現回数が最大の部分文字列はkとなってダメ。
- 与えられた文字列が部分列となるように、どうやって作っても、kが2つ以上となるのでダメ。
解法
http://codeforces.com/contest/889/submission/32290116
重要な考察がある
「同じ文字は2回以上出てこない」
（なぜかは説明できない。分からない）
これに気づくのが重要。
あとは、文字列から有向グラフを作る。
頂点は'a'～'z'で、文字列の隣接する文字の間に遷移関係を作る。
"lru"ならば、'l'->'r'と'r'->'u'を作る。
こうすると、このグラフの遷移関係を全て満たす文字列を作れば、部分文字列として与えられた文字列を含む文字列が作れる。
同じ文字は2回以上出てこないので、分岐やループがあると部分文字列が作れない。
それを判定して、グラフから文字列を復元すれば答え。
int N; string S[101010]; //--------------------------------------------------------------------------------------------------- int use[26], vis[26]; int E[26][26], vin[26], vout[26]; string ans = ""; int dfs(int cu) { if (!use[cu]) return 1; if (vis[cu]) return 0; ans += char('a' + cu); vis[cu] = 1; rep(i, 0, 26) if (!vis[i] and E[cu][i]) return dfs(i); return 1; } //--------------------------------------------------------------------------------------------------- #define no "NO" string solve() { int cnt = 0; rep(i, 0, N) { int M = S[i].length(); rep(j, 0, M - 1) { int a = S[i][j] - 'a'; int b = S[i][j + 1] - 'a'; if (a == b) return no; E[a][b] = 1; } fore(c, S[i]) use[c - 'a'] = 1; } rep(i, 0, 26) if(use[i]) cnt++; rep(i, 0, 26) { rep(j, 0, 26) if (E[j][i]) vin[i]++; rep(j, 0, 26) if (E[i][j]) vout[i]++; if (2 <= vin[i] or 2 <= vout[i]) return no; } rep(i, 0, 26) if(vin[i] == 0){ if (dfs(i) == 0) return no; } if(ans.size() == cnt) return ans; return no; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> S[i]; cout << solve() << endl; }
