AGC049 A - Erasing Vertices - 輪郭をなぞるだけのブログ

リンク

atcoder.jp

問題概要

$N$ 頂点有向グラフが与えられる。
グラフの頂点をランダムに選び、選んだ頂点から到達可能な頂点を消す作業を、グラフが空になるまで繰り返す。
このときの操作回数の期待値を求める。

制約

$1 \leq N \leq 100$

(考察)

同じような考え方を用いる問題を解いたことあるけど、解けなかった、反省。
強連結成分分解を長時間考えてしまったが、問題の配置的に本当にそうかと疑っていたら、案の定違った。

まず、期待値の線形性を用いて問題を言い換える。
本番中この考え方には至ったのだが、確率変数よく分かっていないので、考えきれなかった。

操作回数の確率変数を $X$ とする。
この期待値を $E[X]$ と表すと、これが求める期待値である。

期待値には線形性があり、
(和の期待値) $=$ (期待値の和)
が成り立つ。
これは確率変数 $A, B$ があるとき、
$E[A + B] = E[A] + E[B]$
が成り立つというものである。
この性質を使うために、操作回数の部分を言い換える。

操作中に頂点 $k$ を選ぶか選ばないかを表す確率変数を $X_{k}$ とする。
選ぶときは $X_{k} = 1$ 、選ばないときは $X_{k} = 0$ である。
このとき、操作回数 $X$ は
$X = X_{1} + X_{2} + ... + X_{N}$
$\ \ \ \ = \sum_{k=1}^{N}X_{k}$
と表せる。

あとは、期待値の線形性より
$E[X] = E[X_{1}] + E[X_{2}] + ... + E[X_{N}]$
$\ \ \ \ \ \ \ \ \ = \sum_{k=1}^{N}E[X_{k}]$
であるので、頂点が選ばれる期待値を個別に求められればよい。

これは、頂点 $k$ が操作中に選ばれる確率に等しい。
操作中に頂点 $k$ を選ぶ確率を $P(X_{k} = 1)$ で表すとき、
$E[X_{k}] = 1 \times P(X_{k} = 1) + 0 \times P(X_{k} = 0)$
$\ \ \ \ \ \ \ \ \ \ \ =P(X_{k} = 1)$
になるからである。
この確率は、初期状態のグラフで頂点 $k$ に到達可能な頂点数を $V$ とすると、
$P(X_{k} = 1) = 1 / V$
である。
これは、操作中に頂点 $k$ が選ばれるのは、 $V$ 個の頂点の中で頂点 $k$ が一番最初に選ばれるときだからである。
$V$ 個の頂点の中で頂点 $k$ 以外が最初に選ばれると、頂点 $k$ は消滅してしまい選ばれることはない。
(これに似た考えを用いる問題 : B - Removing Blocks)

あとは、到達可能な頂点数を求められればよい。
制約がゆるいので方法はいろいろある。

各頂点から DFS, BFS
ワーシャルフロイド (実装が一番楽)
強連結成分分解からグラフを作り変える

ステップをまとめると、

操作回数の期待値を、各頂点が操作中に選ばれる回数の期待値に言い換える。
頂点が選ばれる期待値 ( $=$ 確率) は、到達可能な頂点数に等しいので、到達可能性を調べる。

コード

#include <iostream>
#include <iomanip>
using namespace std;

int g[105][105];

int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            char ch;
            cin >> ch;
            g[i][j] = ch - '0';
        }
    }
    for(int i = 0; i < N; ++i)  g[i][i] = 1;
    
    for(int k = 0; k < N; ++k){
        for(int i = 0; i < N; ++i){
            for(int j = 0; j < N; ++j){
                g[i][j] |= g[i][k] & g[k][j];
            }
        }
    }
    
    double ans = 0.0;
    for(int i = 0; i < N; ++i){
        int V = 0;
        for(int j = 0; j < N; ++j){
            V += g[j][i];
        }
        ans += 1.0 / V;
    }
    
    cout << fixed << setprecision(15);
    cout << ans << endl;
}

雑記

B のみの 1 完で、頭の中で問題の条件がすり替わっていて時間を食った。
黄パフォで稼いだレートを日々溶かしていて悲しい...

HTTF2021 は就活枠で本戦に進めるらしい。
本戦に進むようなことはないと思っていたので嬉しい！
マラソンはほとんどやっていないので、本戦で戦えるようにちゃんと勉強しないとな...