2020-11-15

AtCoder AGC 049 A - Erasing Vertices (青色, 400 点)

AtCoder AtCoder400点 AGC-A 青色diff 期待値の線形性期待値グラフ Floyd-Warshall法前処理:Floyd-Warshall法回数の期待値木の問題に対してパスの場合から考える条件の言い換え主客転倒・寄与分解個別の要素の動きに注目する浮動小数点型を扱う問題

面白い。ただ初手で強連結成分分解 (SCC) したくなるのが罠すぎる。SCC 自体は考察過程としては悪くなさそうだけど、SCC して DP...と考えると大変。

問題へのリンク

問題概要

$N$ 頂点の単純有向グラフが与えられる。以下の操作をグラフが空になるまで繰り返す。

残っている頂点からランダムに 1 つ選ぶ
その頂点、および、その頂点から辿れる頂点をすべて削除する
- それらの頂点に接続している辺もすべて削除する

グラフが空になるまでの操作回数の期待値を求めよ。

制約

$1 \le N \le 100$

考えたこと

以下のような考察過程はすべて迷走する結果になった。

強連結成分分解して DAG にする
グラフの形が実は綺麗なパラメータで表せて DP できる (？)
$k$ 回以上要する確率 $p_{k}$ を求めて、 $\sum_{k} p_{k}$ を計算する

最後のやつは、「〜になるまでの回数の期待値を求めよ」という問題では典型手法だけど、今回は上手く行かなそう。

パスグラフについて考えてみる

こういうときの常套手段として、パスグラフの場合を考えてみるのがあると思う。簡単な実験によって、

$N = 1$ のとき $1$ 回
$N = 2$ のとき $1 + \frac{1}{2}$ 回
$N = 3$ のとき $1 + \frac{1}{2} + \frac{1}{3}$ 回
$N = 4$ のとき $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}$ 回
...

となっていることがわかる。いかにもコンプガチャを連想させる綺麗な結果だけど、その方向の考察は上手くいかなそう。

むしろ、「 $N$ 頂点がすべて互いに disjoint」というケースとの対比で考えると突破口が見えた。このケースだと期待値は $N$ (むしろ確定値) になる。すべての頂点が互いに disjoint なケースでは「どの頂点もかならずその頂点が選ばれることによって削除する瞬間がある」というふうになっている。よって、その頂点の個数分の回数を要する。

これに対して、パスグラフでは、かならずしもどの頂点も「それ自身が選ばれることによって削除される瞬間」があるとは限らない。他の頂点が削除対象として選ばれることで、それに巻き込まれて消される可能性があるためだ。よって、操作回数は次のように言い換えられるのだ。

操作回数とは、「それ自身が削除対象として選ばれた頂点の個数」のことである

よって、求める期待値は

頂点 1 がそれ自身が削除対象として選ばれる瞬間がある確率 $p_{1}$
頂点 2 がそれ自身が削除対象として選ばれる瞬間がある確率 $p_{2}$
...
頂点 $N$ がそれ自身が削除対象として選ばれる瞬間がある確率 $p_{N}$

の総和となる！！！

以上のことを、ちゃんと数式でも表してみる。確率変数 $X_{1}, \dots, X_{N}$ を次のように定めると...

$X_{v}$ := 頂点 $v$ が操作過程で削除対象として選ばれるとき 1、そうでないとき 0

操作回数は $X_{1} + \dots + X_{N}$ と表せて、期待値の線形性より、求める期待値は

$E(X_{1} + \dots + X_{N}) = E(X_{1}) + \dots + E(X_{N})$
$= p_{1} + \dots + p_{N}$

と計算できる。

$p_{v}$ の計算

残る問題は、頂点 $v$ がそれ自身が削除対象として選ばれる瞬間がある確率 $p_{v}$ を計算することである。

これは実は簡単で、「頂点 $u$ を削除対象に選ぶと、頂点 $v$ も削除することになる」という条件を満たす頂点 $u$ の個数を $M(v)$ とすると、

$p_{v} = \frac{1}{M(v)}$

となる。たとえば頂点数 4 のパスグラフ (1 -> 2 -> 3 -> 4) では、次のようになっている。

頂点 1 が削除対象として選ばれる瞬間がある確率：1
頂点 2 が削除対象として選ばれる瞬間がある確率： $\frac{1}{2}$
頂点 3 が削除対象として選ばれる瞬間がある確率： $\frac{1}{3}$
頂点 4 が削除対象として選ばれる瞬間がある確率： $\frac{1}{4}$

$M(v)$ の計算は、Warshall-Floyd 法などが有効に使える！よって $O(N^{3})$ の計算量でできる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<bool>> G(N, vector<bool>(N, false));
    for (int i = 0; i < N; ++i) {
        string S;
        cin >> S;
        for (int j = 0; j < N; ++j) if (S[j] == '1') G[i][j] = true;
    }
    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (G[i][k] && G[k][j])
                    G[i][j] = true;
    double res = 0.0;
    for (int i = 0; i < N; ++i) {
        int num = 0;
        for (int j = 0; j < N; ++j) if (j == i || G[j][i]) ++num;
        res += 1.0 / num;
    }
    cout << fixed << setprecision(10) << res << endl; 
}

DP 解法？

多分頑張れば、DP に基づく他の解法も色々あると思われる。

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます