naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉AtCoder Regular Contest 093 E - Bichrome Spanning Tree

E問題(900点!)に手をつけます(@日曜日のスタバ)
ARC 093 E - Bichrome Spanning Tree

  • N頂点M辺の重みつき無向グラフが与えられる。(1\le N\le 10^3,1\le M\le 2\cdot 10^3)
  • 各辺を白か黒で塗るパターンのうち「2色入りの全域木を作ることができて、その中で重みが最小なものの重みはXである」のは何通りあるか、MOD 1000000007で答える。 (1\le X\le 10^{12})

問題文の "bichrome"は「2色の」。2色の全域木。

まずは自力で考える(制限時間1ポモドーロ≒25分)

・問題文とサンプルケースを理解するのに時間がかかる
・サンプル1:全域木は 1-2-3, 2-3-1, 3-1-2 の3つあって、それぞれ重み2で、2色入りにできる塗り方は2通りずつあるから6通り。あるいは、すべての塗りパターン2^M=2^3=8から 白only, 黒onlyな全域木を排除するから 2^3 - 2 = 6ってのは分かる
・サンプル2:重みが2になる全域木 1-2-3 とその塗りパターン2種をサンプル1から引いて4じゃない?と最初思った(けど答えは2)。そうか、重みが2になる 1-2-3 が2色入りになってしまうケースは排除した上であとの2つの全域木のことを考えないといけないのか。「辺1-2と辺2-3 は同じ色で、辺3-1がその2辺と違う色」になる2パターンだけが有効なのね。

これをN=1000,M=2000とかなるのにどう求めたらいいんだ?そもそも全域木って何種類できる?全域木を列挙しないといけない?

28分ぐらい考えてギブアップ。

公式解説を読む

Gの最小全域木T(全体の重みをSとおく)の2頂点*1u,vを結ぶT上の経路(1本だけある)上の辺の中で一番重みの大きい辺(その重みをpathMax(u,v)とおく)の代わりに、u,vを繋ぐけれどTには含まれない辺e(その重みをcとおく)に差し替えるとき、diff(e) = c - pathMax(u,v) で差し替えに伴う全体の重みの変化を表すのだけれど、D=X-S と比べた diff(e) の大小で分類して、それぞれの個数を使った式に落とし込んでる、というところまでは分かるんだけど

分からん、というか腑に落ちない
・なんでlowerの数が計算に使われていないのか
・いや、lowerな辺が1本でも含まれると全体の重みがXを下回る全域木が作れちゃうから駄目ってことなのか?
・TがMSTである以上lowerといっても負にはならないし、複数個交換すればequalかそれ以上の変化を起こしてX以上になるケースもあるんじゃないの?みたいな

【あとがき】要するに、重みXな全域木が作れるだけじゃ駄目で「その色パターンで塗った後に自分以外の誰かが適当に全域木を作ったとしても、X未満な全域木が1つでも出来てはいけない」ということか

ぐぐる

1. kmjpさんのアプローチ

kmjp.hatenablog.jp
公式解説とほぼ同じ?
分からんまま

2. kurarrrさんのアプローチ

kurkur.hatenablog.com


解釈に時間かかったけど分かった

・Gのある辺iを選び、「その辺が含まれる全域木の中で重みが最小の木」の全体の重みをa_iとする。クラスカル法とかやる時に最初にこの辺を使えばいいだけなので求めるのは容易。これをすべての辺について用意。
a_i \lt X、すなわちa_i\le X-1 な辺については、その中だけで2色入り全域木が作れてはいけないので全部同じ色で塗る。それ以上の辺については何色を選ぼうが自由。これをf(X-1)としよう。
・但し、a_i=Xな辺がそれ未満の辺と同じ色になるのは避けなければいけない。(2色入り全域木が重みXで作れなくなって条件を満たさないから)
・従って、f(X-1) から f(X) を引いたのが答え。
・f(x) は、a_i\le x な辺の個数を n とするとa_i \gt x な辺の個数は M-n になるので
$$
\left\{
\begin{array}{ll}
2^M & (n=0) \\
2\cdot 2^{M-n}=2^{M-n+1} & (otherwise)
\end{array} \right.
$$
となる。2を掛けているのはa_1\le xな側の色が「全部白」「全部黒」の二通りあるから。

分かったので自力で書いてみる

→WA(1)
https://beta.atcoder.jp/contests/arc093/submissions/2642188
テスト48+4ケースの中でまばらに8ケースだけWAが出てる

あ… f(x-1) - f(x) を普通に引き算しちゃってるわ。mod 1000000007 なの忘れてる
(スーパーに買い物に寄った帰り道に気づいた)
そこを剰余演算マクロにして
→AC
https://beta.atcoder.jp/contests/arc093/submissions/2642385

時間をかけて紐解いてみれば自分が知ってる道具だけ使って解ける問題だったのが衝撃的。

*1:MSTには全ての頂点が含まれているはずだから「"Tの"2頂点」って言う必要ないような