Hatena::Grouptopcoder

cafelier@SRM

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

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

|

2012-10-20

SRM558 275

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

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

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/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ってことはない。

トラックバック - http://topcoder.g.hatena.ne.jp/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 は奇数

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

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/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 は比較的簡単です。

続きを読む

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20120712

2012-07-03

二分探索

23:09 | はてなブックマーク - 二分探索 - cafelier@SRM

みなさま二分探索ってどういう風に考えながらコードを書くのでしょうか、ということがちょっと気になりました。特に実数ではなくて整数のもの。問題:

private int X = 1 以上 9_9999_9999 以下の秘密の整数;
bool query(int x) { return X <= x; }

X を直接読まずに query() 関数を何回か呼び出すことで X を求めなさい。

自分の場合、こう考えながら書いています。

int solve()
{
  int L = 0;            // 条件を満たさないとわかっている数を適当に
  int R = 10_0000_0000; // 条件を満たすとわかっている数を適当に

  // 不変条件: 「常に答えは半開区間 (L, R] の範囲にある」

以下、意地でもこの条件を崩さないことだけを念頭においてコーディング。

以下、意地でもこの条件を崩さないことだけを念頭においてコーディング。(重要なので二回)

  while( R-L > 1 ) // 答えの範囲が整数一つになるまで繰り返し
  {
     int C = (L+R)/2; // 二分探索なので真ん中をとる
     (query(C) ? R : L) = C;
     // (query(C) ? L : R) = C; ではない。(L,R] が答えの範囲なので R が条件満たす方、L が満たさない方
  }
  return R; // 答えは (L,R] にあるのだから L じゃなくて R が答え
}

Topcoderにサブミットした二分探索のコード全部に半開区間の不変条件がコメントで書いてあります。これを念じていないと「ループ終了条件」「どっちの場合にLとRのどっちを更新するんだっけ?」「最後に返す値はどれ?」の3カ所で、USB端子の差し込み方向並に毎回迷ってしまうので。

チャレンジフェーズで他の人のコードを見ていると、違う考え方でコード書いている人が結構多いようなので興味が湧いています。if(query(C)) R=C; else L=C+1; みたいな形の更新式になるコードとか。気になります。

追記:反応集 http://togetter.com/li/331840

ほげほげ2012/07/04 00:51自分は while(L<R) で回して if(query(C)) R=C; else L=C+1; の更新式でした。
閉区間[L,R]で考えて、query(C) == false の時は C を閉区間から追い出して良いので次の範囲は[C+1,R]になる感じです。
ループ終了条件と返す値は分かり易いのですが、条件を満たす側が逆な場合等に丸め方向と更新式を変える必要があるのがネックでした。
半開区間の方が扱い易そうですね。

cafeliercafelier2012/07/04 02:21コメントありがとうございます。

> query(C) == false の時は C を閉区間から追い出し
こういう考え方を知りたかったのです!なるほど、閉区間で書くイメージもできてきました。

どのやり方も一長一短あるとは思うのですが、特にTopcoderで他人のコードを読むときに、自分のスタイルと違うのを見て詰まってしまう自分が勿体ないなあと思いまして。

cafeliercafelier2012/07/22 18:09「閉区間 & trueでもfalseでもmidを常に追い出す」という方針を教えていただいた。なるほど。
https://twitter.com/nabesan_tofu/status/226959241632690178
https://twitter.com/nabesan_tofu/status/226964459439136768

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20120703
|

presented by cafelier/k.inaba under CC0