RankingStudents [SRM 782 Div1 Med]

解法

簡単に書いておく。
貪欲法で解ける。

先頭から埋めていくことを考えると使える要素がどんどん少なくなっていく。
だが、末尾から埋めていくことを考えると使える要素がどんどん多くなっていく。
多くなる方がうまくいく場合が多いので、そっちでまず考えてみる。

順番の関係も追加で与えられているが、それは、b[i] -> a[i]に辺をはることで、b[i]が登場したらa[i]も登場できるという感じに表現できる。
これで有向グラフを構築したときに、ループがあれば、構築不可能。
自分はこれをトポロジカルソートのライブラリで判定した。
（判定したが、別に判定しなくても大丈夫だと思う。たぶん）

あとは、後ろから貪欲に確定させていく。
「まだ使われていない、かつ、有向辺の入ってくる頂点がすべて選択済み、かつ、その時点で使える要素である」を満たす要素が出たら使っていけばいい。 複数選択肢がある場合では、どれを選んでも問題ない。 これはA,Bが選択可能であるときに、ABと選ぶのと、BAと選ぶのはどちらも可能であり、かつ、結果はどちらも同じになるためである。 この性質がすべての組に対して言えるので、どれを選んでも問題ない。

struct TopologicalSort {
    vector<vector<int>> E; TopologicalSort(int N) { E.resize(N); }
    void add_edge(int a, int b) { E[a].push_back(b); }
    bool visit(int v, vector<int>& order, vector<int>& color) {
        color[v] = 1;
        for (int u : E[v]) {
            if (color[u] == 2) continue; if (color[u] == 1) return false;
            if (!visit(u, order, color)) return false;
        } order.push_back(v); color[v] = 2; return true;
    }
    bool sort(vector<int>& order) {
        int n = E.size(); vector<int> color(n);
        for (int u = 0; u < n; u++) if (!color[u] && !visit(u, order, color)) return false;
        reverse(order.begin(), order.end()); return true;
    }
};



#define yes "Possible"
#define no "Impossible"
bool used[1010];
int rest[1010];
struct RankingStudents {
    string rankingPossible(int n, vector <int> f, vector <int> a, vector <int> b) {
        TopologicalSort ts(n + 1);
        rep(i, 0, a.size()) ts.add_edge(b[i], a[i]);
        rep(i, 0, a.size()) rest[a[i]]++;
        vector<int> ord;
        auto res = ts.sort(ord);
        if (!res) return no;

        rrep(re, n - 1, 0) {
            bool ng = true;
            rep(i, 0, n) if (!used[i] && rest[i] == 0 && re <= f[i]) {
                used[i] = true;
                fore(to, ts.E[i]) rest[to]--;
                ng = false;
                break;
            }
            if (ng) return no;
        }

        return yes;
    }
};