問題：https://scratch.mit.edu/discuss/topic/504096/?page=11#post-6140005 解説：https://scratch.mit.edu/discuss/topic/504096/?page=14#post-7007408 トポロジカルソート(BFS) および 二分ヒープ による 優先度付きキュー が実装してあります． 文字列 → 数値 への変換は二分探索で． スペースキー/緑の旗 で実行。 最初の質問で無入力のまま確定すると，サンプルケースの値で実行できます。更に次の質問も無入力のまま確定すると(答えが-1とならないような)テストケースを自動生成してくれます。
Easy 解答例： https://scratch.mit.edu/projects/664965095/ 最悪ケースレベルの入力に対して，平均 70ms ぐらいかかります． C++ によるダミープログラム(1byte文字のみ対応) ``` #include<bits/stdc++.h> using namespace std; using ll = long long; #define REP(i,n) for(ll i=0; i<ll(n); i++) using Graph = vector<vector<int>>; int n, q; string alphabets; vector<int> topological_sort(Graph &G, vector<int> &indegree) { vector<int> sorted; priority_queue<int> que; REP(i, n) { if (indegree[i] == 0) { que.push(i); } } while (!que.empty()) { int v = que.top(); que.pop(); REP(i, G[v].size()) { int u = G[v][i]; indegree[u]--; if (indegree[u] == 0) que.push(u); } sorted.push_back(v); } return sorted; } vector<int> string_to_vector_of_number(string s) { vector<int> res(s.size()); REP(i, s.size()) { res[i] = alphabets.find(s[i]); } return res; } string vector_of_number_to_string(vector<int> v) { string res = ""; REP(i, n) { res += alphabets[v[i]]; } return res; } int main(void) { cin >> n >> q; cin >> alphabets; Graph G(n); vector<int> indegree(n); REP(i, q) { string s; cin >> s; vector<int> order = string_to_vector_of_number(s); REP(j, order.size()-1) { G[order[j]].push_back(order[j+1]); indegree[order[j+1]] += 1; } } vector<int> sorted = topological_sort(G, indegree); if(sorted.size() != n) { cout << -1 << endl; return 0; } string ans = vector_of_number_to_string(sorted); cout << ans << endl; return 0; } ```
