mayoko’s diary

プロコンとかいろいろ。

SRM 530 div1 med: GogoXMarisaKirisima

これ難しい…(というか気づけばやるだけ系は難易度の判定が難しそう)(競プロの問題の 8 割は気づけばやるだけ)

解法

頂点 i について, 0 -> i に到達可能でかつ i -> n-1 に到達可能である, という条件を満たすものだけを残したグラフ G を考えます。

すると, 答えは, (G の辺の数) - (G の頂点数) + 2 となります。

なぜかを考えてみます。
頂点 i について, 一回でも通ったことがあったら visit[i] = true とします。すると, 各頂点から n-1 に確実に到達することができるので, 1 度 visit[i] = true となるような進み方をしたあとは, i -> n-1 には, 一つも新しい辺を使わないで進むことが出来るようになります。また, すべての頂点について visit[i] = true となった後は, 今まで使ってない辺を 1 つだけ使って, 他には一切新しい辺を使わないで n-1 まで到達できるようになります。

あとは visit[i] = true がすべての i で成り立つまでにどれだけ道の数を稼げるかですが, 最初に visit[0] = true としておきます(まぁ任意の経路でとおる道なので)。
で, まだ通ってない辺を通るということは, visit[i] = true, visit[j] = false となっている頂点 i から j へ通るということなのです。j に到達した後は, n-1 まで行くか, visit[k] = true を満たす k まで進んで, 後はさっき k を通った時 n-1 に進んだ道を通って n-1 に行きます(visit[k] = true より, 以前に k 経由で n-1 に到達したはずなので)。

このように通るのが明らかに損をしない戦略ですが, この時 visit[j] = false となっていた頂点を K 個通ったとすると, 今まで通っていなかった辺を K+1 個通ったことになります。
このようにして, 計 m 回 n-1 まで行って, すべての頂点について visit[i] = true になったとすると, まず経路として m 個の候補があり, (n-2)+m 個の辺を使っています(各経路における K の合計は, 0 と n-1 以外の頂点の数 n-2 になるはず)。
残りの辺は M-(n-2+m) なので, 上の考察(visit[i] = true がすべての i で成り立ったら, あとは未使用の辺を 1 回ずつ使いながら n-1 に行く経路が存在する)を用いると, 答えは M-(n-2+m)+m = M-n+2 となります。

const int INF = 1e9;
vector<int> bfs(vector<string> choices, int s, int rev) {
    int n = choices.size();
    vector<int> d(n, INF);
    d[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int now = que.front(); que.pop();
        for (int i = 0; i < n; i++) {
            if (rev == 0 && choices[now][i] == 'Y') {
                if (d[i] > d[now]+1) {
                    d[i] = d[now]+1;
                    que.push(i);
                }
            }
            if (rev == 1 && choices[i][now] == 'Y') {
                if (d[i] > d[now]+1) {
                    d[i] = d[now]+1;
                    que.push(i);
                }
            }
        }
    }
    return d;
}

class GogoXMarisaKirisima {
public:
    int solve(vector <string> choices) {
        int n = choices.size();
        ll mask0 = 0, maskn = 0;
        auto d = bfs(choices, 0, 0);
        for (int i = 0; i < n; i++) if (d[i] < INF) mask0 |= 1ll<<i;
        d = bfs(choices, n-1, 1);
        for (int i = 0; i < n; i++) if (d[i] < INF) maskn |= 1ll<<i;
        ll mask = (mask0 & maskn);
        if (mask == 0) return 0;
        int M = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if ((mask0&(1ll<<i)) && (maskn&(1ll<<j)) && (choices[i][j]=='Y')) M++;
        }
        return M+2-__builtin_popcountll(mask);
    }
};