SRM 670 div1 med:Treestrat - mayoko’s diary

これ本番出てたら「あぁ med やっておけば良かった…」とかなりそう(easy はわからなかったけどこっちは考えたらわかったので)。

問題

解法

B さんは, A さんのどれかのトークンに狙いを定めてそれを集中狙いするのが得です。よって, A さんのトークンそれぞれに対して B さんが勝つためには何回移動すべきなのかを計算し, その最小値が答えになるわけです。
一方で A さんはそれぞれのトークン a がなるべくターンを稼げるようにしたいです。そのために, 「a が最終的にどの頂点にいるか」というので場合分けをして, 生き残るターン数が多いものを採用すれば良いです。

頂点 i に a が向かうとすると, a は i に向かう時寄り道する必要は無いです。その最短経路までに B のいずれかのトークンが邪魔出来てしまうと i にたどり着くことが出来ないことになります。たどり着くことができる場合は, B のいずれかのトークンがそこにたどり着くまでに何ターンかかるかを計算し, その最大値を求めます。

…とかやりましたがとーらすさんの解法のほうがスッキリしてますね…torus711.hatenablog.com

vector<vi> G;
vector<vi> d;
const int INF = 1e9;

class Treestrat {
public:
    int roundcnt(vector <int> tree, vector <int> A, vector <int> B) {
        int n = tree.size() + 1;
        G.resize(n);
        d.resize(n);
        for (int i = 0; i < n; i++) {
            d[i].resize(n);
            for (int j = 0; j < n; j++) d[i][j] = INF;
        }
        for (int i = 1; i < n; i++) {
            G[i].push_back(tree[i-1]);
            G[tree[i-1]].push_back(i);
            d[i][tree[i-1]] = d[tree[i-1]][i] = 1;
        }
        for (int i = 0; i < n; i++) d[i][i] = 0;
        int ret = INF;
        for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
        for (int a : A) {
            int maxi = 0;
            for (int i = 0; i < n; i++) {
                vector<int> path;
                int cur = a;
                path.push_back(a);
                while (cur != i) {
                    for (int v : G[cur]) {
                        if (d[a][v] == d[a][cur]+1 && d[i][cur] == d[i][v]+1) {
                            cur = v;
                            break;
                        }
                    }
                    path.push_back(cur);
                }
                bool ng = false;
                for (int v : path) {
                    for (int b : B) {
                        if (d[b][v] <= d[a][v]) {
                            ng = true;
                            break;
                        }
                    }
                }
                if (!ng) {
                    int mini = INF;
                    for (int b : B) mini = min(mini, d[b][i]);
                    maxi = max(maxi, mini);
                }
            }
            ret = min(ret, maxi);
        }
        return ret;
    }
};