競プロ日記

ACコード - O(NM)
ACコード - O(M)

O(M)コード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst) : src(src), dst(dst) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector;
using Graph = vector;

void edges_to_graph(Graph &graph, const Edges &edges, const int vertices, const bool directed = true) {
  graph.resize(vertices);
  for (const auto &e : edges) graph[e.src].emplace_back(e);
  if (!directed) for (const auto &e : edges) graph[e.dst].emplace_back(Edge(e.dst, e.src, e.weight));
}

int main(void) {
  int n, m;
  cin >> n >> m;
  Graph graph;
  Edges edges(m);
  rep (i, m) {
    int s, t;
    cin >> s >> t;
    edges[i] = {--s, --t};
  }
  edges_to_graph(graph, edges, n);
  vector svp(n), nv(n);
  svp[0] = 1;
  rep (i, n - 1) {
    double p = svp[i] / graph[i].size();
    allrep (e, graph[i]) svp[e.dst] += p;
  }
  rrep (i, n - 1) {
    double sum = 0;
    allrep (e, graph[i]) sum += nv[e.dst];
    nv[i] = sum / graph[i].size() + 1;
  }
  double maxdec = 0;
  rep (i, n - 1) {
    const int en = graph[i].size();
    if (en == 1) continue;
    double maxi = -1;
    allrep (e, graph[i]) maxi = max(maxi, nv[e.dst]);
    double newnv = ((nv[i] - 1) * en - maxi) / (en - 1) + 1;
    maxdec = max(maxdec, (nv[i] - newnv) * svp[i]);
  }
  cout << nv[0] - maxdec << endl;
  return 0;
}

「部屋1から移動する前に」を「部屋を1つ移動する度に」と読み間違えて全く手も足も出なかった。
YouTubeの解説で、道を塞がない場合の期待値を計算して、その後どうやるんだろうと眺めてたらさらっと流して実装に移ってしまったので、改めて問題を読み直して気がついた。
結構問題読み間違えがちだが、今回ほど難しく読んだことはない気がする。
解説でも気付いていない人が結構いたっぽいと言っていたが、これがDAGであるというのはもちろん気付いていなかった。
もっと丁寧に問題読もうね！！！

まずはO(NM)の解法。
最初は解説も理解できなかったが、問題を正しく理解すればなんということはない。
dpの構築をN回行うというのは驚いた。
本来ならO(N^2)のところを、dpすればO(N)になってそれ単体あるいは二分探索等と組み合わせて時間内に解ける、みたいなイメージが強かったのだが、dpを繰り返すとは。
制限が緩い問題を全探索で解いているような違和感があった。
実装自体はかなり大したことなかった。

次にO(M)の解法。
正直なところ、YouTubeの解説はあまり理解していない。
理解できなかったというよりは、変数多すぎて追うのを諦めたの方が近い。
とりあえず理解したのは、毎回dpを構築するのではなくて、ある辺を塞ぐ際に影響する部分を考えるということ。
そしてそれには、頂点v-u間の辺を塞ぐ場合に、スタートからvまで、uからゴールまでの、2つの情報を分けて考えれば良いということ。
細かい部分は、あまりに変数が多くてこんがらがったYouTubeの解説は置いておいて、他の解説記事を参考に理解した。
自分の理解は大体以下のような感じ。

v-u間の辺を塞いだ際、スタートからvまでの期待値に変更はなく、変更されるのはvからゴールまでの間である。
辺を削除した後のvからゴールまでの期待値はO(1)で簡単に計算できるが、そこからO(NM)のdpと同じようにスタートまで伝搬させていくと結局O(NM)になってしまう。
そこで、元のuからゴールまでの期待値と、辺を削除した後のuからゴールまでの期待値の差を考えることにする。
また、頂点vから出ている辺が削除された際の全体の期待値の変化は、頂点vに到達する確率に影響される。
これは感覚的にも分かりやすい。
例えば、ゴールに到達するまでに必ず通る頂点があった場合、その変化は当然全体の期待値にも直接影響する。
全ルートのうち半分しか通らない頂点xがあった場合、全体の期待値は、[(頂点xを通らないルートの期待値)+(頂点xを通るルートの期待値)] / 2で表すことができるので、その変化は1/2の割合で影響していることが分かる。
この2つから、全体の期待値に与える変化は以下のようになる。
[(元の頂点vからゴールまでの期待値) - (辺を削除した後の頂点vからゴールまでの期待値)] × (頂点vを通る確率)

まず、頂点vを通る確率は頂点の昇順でdpすることで求められる。
次に、元の頂点vからゴールまでの期待値は、O(NM)と同様の、降順のdpで求められる。
最後に、辺を削除した後の頂点vからゴールまでの期待値は、元の期待値から単純な確率計算を行うことで求められる。
通常の確率ではなく通る辺の期待値のため、+1がある分多少ややこしい計算になるが、やっていることは「確率×ルート数=総量から減る分を引き、1減ったルート数で割って確率に戻す」というような通常の確率計算と同じものである。
頂点1～N-1までループを回してこの変化量が最も大きい辺を見つけ、全体の期待値から引くことで答えが求められる。
頂点ごとに塞ぐ辺を見つけるためにループを回すが、辺の総数はMなのでO(M)になるはず。

確かにこれで計算量は改善でき、実行時間も短くなった。
・・・のだが、使う変数が少ない・・・。
一体YouTubeの解説のあの圧倒的な変数量はなんだったんだ・・・。
式変形なんて全くやっていない。
+1のせいでややこしくなる計算部分を簡単にするために色々保持してるんだろうなと予想はしているが、個人的には自分の実装の方が分かりやすい。
最初あの解説を見て、通るならO(NM)でいいや、と思ったのだが、前述の通り全探索のような違和感があったのでO(M)にも挑戦してみた。
実際解いてみて、やはりO(M)の解法の方が自然でスマートな感じがする。
削除した辺以前の値は全て変わるとは言え、毎回dpを構築し直すのは無駄が多すぎる。
解説記事はO(M)の解法が多かった(と思う)のだが、O(M)の方が自然に思いつきそうだなというのは納得である。