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); } };