Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

|

2012-12-02

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20121202

2012-10-20

SRM558 275

| 00:57 | はてなブックマーク -  SRM558 275 - cafelier@SRM

重ね塗りを考慮するのややこしいので、重ね塗りを考えないのが多分一番良い解き方だと思う。

続きを読む

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20121020

2012-10-11

Path Cover のいろいろ

21:08 | はてなブックマーク -  Path Cover のいろいろ - cafelier@SRM

パス (今回使う定義) / Path

有向グラフ G=(V,E) 上のパスとは

Vの重複を含まないリスト v[1], v[2], ..., v[k] であって (v[i],v[i+1])∈E なもの)。

k=1 の場合、つまり単独の頂点一個でもパスとみなす

パス被覆 / Path Cover

有向グラフ G=(V,E) のパス被覆とは

パスの集合 P であって、P に属すパスに属す頂点を全部集めると V になるもの。

独立パス被覆

有向グラフ G=(V,E) の独立パス被覆とは

パス被覆 P であって、P に属すパス同士の間に頂点の共有がないもの。

(証明のために後で使う概念) 端点集合 ter(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) の無理矢理二部グラフ化とは1個の頂点 v∈V を v<入口> と v<出口> の2個にわけて、辺v→uがあったらv<出口>→u<入口>に辺を引くようにしたグラフ。出口同士、入口同士に辺がないので二部グラフである。

独立点集合 / Independent Set

有向グラフ G=(V,E) の独立点集合とは

頂点集合 X ⊆ V であって、X に属する異なる頂点同士を結ぶ辺がまったくないもの。安定集合と呼んだりもする。推移性のあるDAGでは反鎖/antichainと呼んだりもする。

任意のグラフで成り立つ性質

21:08 | はてなブックマーク -  任意のグラフで成り立つ性質 - cafelier@SRM

|最小パス被覆| ≦ |最小独立パス被覆|

独立パス被覆はすべてパス被覆なので当然。

[Gallai & Milgram 1960] |最小独立パス被覆| ≦ |最大独立点集合|

以下の補題より。

補題: |極小端点独立パス被覆| ≦ |最大独立点集合|

証明:数学的帰納法。頂点数 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} 同士を結ぶ辺が1個もなかったら、これが独立点集合なので証明終わり。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')な被覆があったことになる。場合分け

  • v2'∈Q かつ ter(Q)⊊ter(P') なパス被覆Qがあった → Qのv2'の後ろにu2を繋げるとPの極小性に反する
  • u1∈Q かつ v2'∉Q かつ ter(Q)⊊ter(P') なパス被覆Qがあった → Qのu1の後ろにu2を繋げるとPの極小性に反する
  • u1もv2'もQに入ってないかつ ter(Q)⊊ter(P') なパス被覆Qがあった → Qにもう一個{u2}というパスを足すとPの極小性に反する

証明終。

|V| - |最小独立パス被覆| ≦ |無理矢理二部グラフ化したものの最大マッチング|

証明: 独立パス被覆の辺を全部使うとそれはマッチングになっている。つまり、各vについて、v<出口>から出てる辺は高々1本しか選んでないし、v<入口>に入る辺は1本しか選んでない。

独立パス被覆 P について |Pのパスの本数| + |Pに含まれる辺の数| = |V| なので、↑この作り方で |V|-|Pのパスの本数| サイズのマッチングが少なくとも得られた。

推移性のあるグラフで成り立つ性質

21:08 | はてなブックマーク -  推移性のあるグラフで成り立つ性質 - cafelier@SRM

推移性(Transitivity)がある、とは

「頂点aからbに辺があってbからcに辺があるなら、必ずaからcにも辺がある」こと。

推移性のあるグラフなら、|最大独立点集合| ≦ |最小パス被覆|

証明: 一般に、独立点集合の頂点同士は直接辺で結ばれていない。推移性がある場合は、パスで結ばれてもいない。よって、このようなグラフをパス被覆するには全ての独立頂点を別々のパスでカバーしないといけない。

系: 推移性のあるグラフなら、|最大独立点集合| = |最小パス被覆|

系: [Dilworth 1950] 推移性のあるDAGなら、|最大独立点集合| = |最小パス被覆|

注意: DAGというだけでは |最大独立点集合| = |最小パス被覆|は成立しない。

a -> b -> c

というグラフの最大独立点集合は{a,c}だが、パス被覆は{a->b->c}の1本でカバーできてしまう。

DAGで成り立つ性質

21:08 | はてなブックマーク - DAGで成り立つ性質 - cafelier@SRM

DAGなら、|V| - |無理矢理二部グラフ化したものの最大マッチング| ≧ |最小独立パス被覆|

証明: マッチングに属する辺を全て使うと独立パス被覆ができる。

任意のグラフでの「≦」の証明と逆向きに考えて、マッチングなので元のグラフに戻したときに枝分かれや合流はできてない。また、元がDAGなのでサイクルもできてない。よってマッチングを元のグラフに戻すとパスがたくさんという形になっている。

辺をe本使うパス被覆のパスの本数は、|V| - e なので、大きくとも|V|-|最大マッチ|のパス被覆は↑このようにして作れている。

系: DAGなら、|V| - |無理矢理二部グラフ化したものの最大マッチング| = |最小独立パス被覆|

注意: "独立"が重要。5頂点のXの字のようなDAGを考えると、独立でないパス被覆なら2パスでカバーできるが、独立パスだと3パス必要だし最大マッチングは2=|V|-3。

系:推移性のあるDAGなら、|最大独立点集合| = |最小独立パス被覆| = |最小パス被覆| = |V| - |無理矢理二部グラフ化したものの最大マッチング|

注意: 推移性では|V|-|最大マッチ|と等しくはならない。DAGであることが重要。反例として、N点の完全グラフを考えると、最大マッチはNなので|V|-|最大マッチ|は0になってしまうけれど、最小パス被覆が0ってことはない。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20121011

2012-08-18

SRM552 Div1 900

| 23:01 | はてなブックマーク - SRM552 Div1 900 - cafelier@SRM

問題文を整理すると、

  • 「upTo (≦10^10) 以下の自然数で、次の条件を満たすものの個数は?」
  • 条件:素因数分解 p1^k1 p2^k2 ... pm^km したとき
    • pi ≦ maxmalPrime (≦10^6)
    • ki は奇数

が問われている。計算量が分析できてないので考える。

続きを読む

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20120818

2012-07-12

deque で DP

21:42 | はてなブックマーク -  deque で DP - cafelier@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 は比較的簡単です。

続きを読む

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20120712
|

presented by cafelier/k.inaba under CC0