JAG 模擬国内2020 H 辺が先か，頂点が先か (AOJ 3208 Edge or Vertex)

問題文 : Aizu Online Judge

LPの定式化から2つのアプローチができて面白かったのでそれについて説明する。

考察1

先手が初めに各辺に確率を割り振り、後手はそれに応じてを確率で選ぶとする。値 を先手は最大化、後手は最小化する時、Xの値はいくらかという問題になる。 まず後手はあるpure strategy(ある選択肢を確立1で選ぶ)が最適になる。すなわち、先手の戦略に対し、各頂点ごとにを計算し、これが最小となる頂点を確立1で選ぶのが後手の最適な戦略である。この考察を踏まえると、次のようにLPで定式化できる。

考察2

与えられるグラフに閉路が存在する場合、pは閉路の辺に均等に確率を割り振ればXの値を0にできる。また、後手はすべての頂点に均等に確立を割り振る戦略でXの値を必ず0以下にできる。 よって、グラフに閉路が存在するなら、解は0が言える。

そうでないとき、が負になる頂点が少なくとも１つは存在する。よってDAGの時、解は負の数が言える。

LP解法1

考察1での定式化では、maximizeの対象にminが入っており扱いづらい。こういう際の常套手段として新しい変数を加えminを不等式制約で表現するというのがある。それを行うと、

自分はここで詰まってしまった。双対とっても綺麗になりそうもないし(もしかしたらなるかもしれませんが)いかんせんの制約が邪魔で変形や解釈が難しかった。

ここ(Lesson 35: Game Theory and Linear Programming)のスライドを眺めてみると、Sの符号がわかっているときは(より一般にmatrix gameでできる)いい感じの変形があるということがわかった。今回の場合、考察2からDAGで解が負になる場合だけを考えればよいためこの変形が利用できる。 具体的にはとおくと、

となるが、よく見るとSが消去できることがわかる。よって問題は

となる。これは「各頂点を始点とするパスの長さの合計を最大化」するグラフの問題と解釈でき、今回グラフはDAGなので各頂点までの最長パスはDPで簡単に求まるので解けた。 (解説にはラグランジュ双対を取ると書いてあるけど和が1の制約とかが邪魔でどうやったら取れるのかわからない...誰か教えてください)

LP解法2

LPで定式化した際に現れるという式は各頂点への相対流入量を表しているので、をただの辺に割り振られた確率とみるのではなくフローとみなすことが有効かもしれないことがわかる。すなわち、「各頂点の相対流入量が以上ですべての辺の合計流量が1となるようなフローが存在するの最大値をもとめる」問題だと解釈できる。ここでそのようなフローが存在するかどうかはに関して単調であるので、二分探索をすることにすると次の問題を解きたくなる。

双対をとると

となり、実はは無関係で二分探索が必要ないことがわかる。答えはこの問題の最適解でのとなる。(合計流量を1以上にできる境目を見つけたいので) そして上の問題はいわゆる牛ゲー(差分制約による最短(長)経路問題のポテンシャルの最大(小)化)に近い形であり、各頂点からの最長路の長さの和が最適値であることがわかる。よって解けた。

提出

Aizu Online Judge

bool solve() {
  int N, M;
  cin >> N >> M;
  if (N == 0 && M == 0) return false;
  vector<vector<int>> g(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
  }
  vector<int> vs;
  vector<bool> used(N, false);
  vector<int> ord(N);
  function<void(int)> dfs = [&](int v) {
    used[v] = true;
    for (int u : g[v]) {
      if (!used[u]) dfs(u);
    }
    vs.push_back(v);
  };
  for (int i = 0; i < N; i++) {
    if (!used[i]) dfs(i);
  }
  reverse(all(vs));
  for (int i = 0; i < vs.size(); i++) { ord[vs[i]] = i; }
  for (int i = 0; i < N; i++) {
    for (int j : g[i]) {
      if (ord[i] > ord[j]) {
        cout << 0 << endl;
        return true;
      }
    }
  }
  vector<int> dp(N, 0);
  for (int i = N - 1; i >= 0; i--) {
    int v = vs[i];
    for (int u : g[v]) { chmax(dp[v], dp[u] + 1); }
  }
  cout << setprecision(30) << -1.0 / (long double)(accumulate(all(dp), 0))
       << endl;
  return true;
}