cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
|
有向グラフ G=(V,E) 上のパスとは
Vの重複を含まないリスト v[1], v[2], ..., v[k] であって (v[i],v[i+1])∈E なもの)。
k=1 の場合、つまり単独の頂点一個でもパスとみなす
有向グラフ G=(V,E) のパス被覆とは
パスの集合 P であって、P に属すパスに属す頂点を全部集めると V になるもの。
有向グラフ G=(V,E) の独立パス被覆とは
パス被覆 P であって、P に属すパス同士の間に頂点の共有がないもの。
パスの集合 P={p1,p2,...,pn}
p1 = v11 -> v12 -> ... -> u1 p2 = v21 -> v22 -> ... -> u2 ... pn = vn1 -> vn2 -> ... -> un
に対してその末端の頂点の集合 {u1,u2,...,un} をter(P)と書く。
Pが独立パス被覆で、ter(Q) ⊊ ter(P) となるような他の独立パス被覆が存在しないとき、Pは極小端点独立パス被覆であるという。最小独立パス被覆は当然必ず極小端点独立パス被覆である（が、逆は必ずしもそうでもないかも。）
有向グラフ G=(V,E) の無理矢理二部グラフ化とは１個の頂点 v∈V を v<入口> と v<出口> の２個にわけて、辺v→uがあったらv<出口>→u<入口>に辺を引くようにしたグラフ。出口同士、入口同士に辺がないので二部グラフである。
有向グラフ G=(V,E) の独立点集合とは
頂点集合 X ⊆ V であって、X に属する異なる頂点同士を結ぶ辺がまったくないもの。安定集合と呼んだりもする。推移性のあるDAGでは反鎖/antichainと呼んだりもする。
|
独立パス被覆はすべてパス被覆なので当然。
以下の補題より。
証明：数学的帰納法。頂点数 1 のグラフでは両辺共に 1 なので成立する。
頂点数 k のグラフで成立したとする。頂点数 k+1 のグラフ G の極小端点独立パス被覆P={p1,p2,...,pn}を1つ適当に選ぶ。
p1 = v11 -> v12 -> ... -> v1' -> u1 p2 = v21 -> v22 -> ... -> v2' -> u2 ... pn = vn1 -> vn2 -> ... -> vn' -> un
ter(P) = {u1, ..., un} 同士を結ぶ辺が１個もなかったら、これが独立点集合なので証明終わり。u1 -> u2 という辺があった場合は、ややこしくなる。
Fact: u1 -> u2 という辺がある場合、p2は単一頂点パスp2={u2} ではない（仮にそうだとするとp1の後ろにu2を繋げてみるとPの極小端点性に反する）
主張: u2を除いたグラフを考えると、さっきのパス被覆Pからu2を除いたP'
p1 = v11 -> v12 -> ... -> v1' -> u1 p2'= v21 -> v22 -> ... -> v2' ... pn = vn1 -> vn2 -> ... -> vn' -> un
これも、u2除去後のグラフの極小端点独立パス被覆になっている。
これを認めると、帰納法の仮定より、u2除去後のグラフにはサイズ n の独立点集合がある。u2を入れ直してもこれは独立点集合である。
主張の証明: 極小じゃなかったとする。ter(Q)⊊ter(P')な被覆があったことになる。場合分け
証明終。
証明: 独立パス被覆の辺を全部使うとそれはマッチングになっている。つまり、各vについて、v<出口>から出てる辺は高々１本しか選んでないし、v<入口>に入る辺は１本しか選んでない。
独立パス被覆 P について |Pのパスの本数| + |Pに含まれる辺の数| = |V| なので、↑この作り方で |V|-|Pのパスの本数| サイズのマッチングが少なくとも得られた。
|
推移性(Transitivity)がある、とは
「頂点aからbに辺があってbからcに辺があるなら、必ずaからcにも辺がある」こと。
証明： 一般に、独立点集合の頂点同士は直接辺で結ばれていない。推移性がある場合は、パスで結ばれてもいない。よって、このようなグラフをパス被覆するには全ての独立頂点を別々のパスでカバーしないといけない。
注意: DAGというだけでは |最大独立点集合| ＝ |最小パス被覆|は成立しない。
a -> b -> c
というグラフの最大独立点集合は{a,c}だが、パス被覆は{a->b->c}の1本でカバーできてしまう。
|
証明: マッチングに属する辺を全て使うと独立パス被覆ができる。
任意のグラフでの「≦」の証明と逆向きに考えて、マッチングなので元のグラフに戻したときに枝分かれや合流はできてない。また、元がDAGなのでサイクルもできてない。よってマッチングを元のグラフに戻すとパスがたくさんという形になっている。
辺をe本使うパス被覆のパスの本数は、|V| - e なので、大きくとも|V|-|最大マッチ|のパス被覆は↑このようにして作れている。
注意: "独立"が重要。5頂点のXの字のようなDAGを考えると、独立でないパス被覆なら2パスでカバーできるが、独立パスだと3パス必要だし最大マッチングは2=|V|-3。
注意: 推移性では|V|-|最大マッチ|と等しくはならない。DAGであることが重要。反例として、N点の完全グラフを考えると、最大マッチはNなので|V|-|最大マッチ|は0になってしまうけれど、最小パス被覆が0ってことはない。
SRM | |
問題文を整理すると、
が問われている。計算量が分析できてないので考える。
|
Codeforces 129 Div1 D の本質的な部分は、こんな問題でした。（実際にはこれを左右から計算して掛け算などする。）
'B' か 'W' か 'X' の並んだ長さ100000以下の文字列 S と、1以上の整数 K が与えられます。S に含まれる全ての 'X' を 'B' か 'W' に置き換えたときに "BBB....BB" (BのK連続) が含まれるようにする置き換え方は何通りあるか、mod 1,000,000,007 で求めてください。
ただし、Sの長さが1000以下のケースを全て解けたら部分点300点が得られる、という場合、部分点狙いの O( |S|・K ) の DP は比較的簡単です。
presented by
cafelier/k.inaba
under
