子供の落書き帳 Remix

15/4/13:ひと月に一度更新するブログになってしまっている

AtCoder Beginner Contest 036 木の独立集合の個数を求める
2016/06/11(土) 17:48:42

珍しく技術系っぽい記事を書く。

AtCoder Beginner Contest 036のD問題について。
D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder

問題の内容



グラフ理論の言葉で言い換えると
「与えられた木に対して、独立集合(independent set)の個数を求めよ。」となる。
独立集合 - Wikipedia

一般のグラフに対して、最大独立集合を求める問題はNP完全問題らしい。
そして独立集合の個数を数えるのも難しいらしい。↓の資料に書いてあった。
PowerPoint資料:木分解とグラフ・アルゴリズム(最適化と数え上げ)


ということは、グラフが「木であること」を利用しないと上手く解けないはずだ。
資料の中にも根付き木を利用して考える方法があったし、適当な頂点を根として計算するんだろう。

逐次的に(DPを用いて)処理するんだろうなぁ……
f(G)を与えられたグラフに対する独立集合の総数とすると、
・一点からなるグラフから始めて頂点を次々と追加し、f(G)を求めていく
・根付き木の部分木から順に、f(G)を求めていく
の2通りが思いつく。

競技時間中は前者かと思っていたけど、正解は後者。

AtCoder解説(※pdf)を見ると「根から遠い順に求めていけば良い」と書いてある。

プログラミング


なるほど、アルゴリズムとしては理解できた。
でもコードにできそうに無い。

深さ優先探索か何かをして、木の構造を入力する……??
各頂点に対して「この頂点の親はコレで、子はコレとコレです」みたいなデータを用意するの??
……?????

と、ワケが分からなくなったので皆の提出したコードを見ることにした。
言語はRuby。
Rubyで書かれた正答のソースコード一覧は以下から見られる。
All submissions - AtCoder Beginner Contest 036 | AtCoder

Rubyは初心者なので、読むのにだいぶ苦労したが、正解のコードは以下の2つの段階からなっている。

(1) 頂点どうしの関係性を配列に入力する
(2) 配列を元に、再帰的にf(x), g(x)を計算する

f,gは以下の通り。解説文から引用。
・f(x):頂点 x を親とする部分木に含まれる頂点をすべて白または黒で塗り,両端が黒で塗られた辺が存在しないようにする方法は何通りか?
・g(x): 頂点 x を親とする部分木に含まれる頂点をすべて白または黒で塗り,両端が黒で塗られた辺が存在しないようにする方法は何通りか?ただし,頂点 x は必ず白で塗らなければならない.


(1) 頂点どうしの関係性を配列に入力する



これは例を用いたほうが分かりやすいだろう。問題に載っていた入力例で考える。

5
2 5
1 5
2 4
3 2


5つの頂点からなるグラフである。

頂点1と繋がっているのは頂点5、頂点2と繋がっているのは頂点3,4,5、……という情報を順に配列に入れて
[[5], [3, 4, 5], [2], [2], [1, 2]]
というデータを作る。
ただし、実装する際はインデックスが0から始まるので、全ての要素から1を引いて
[[4], [2, 3, 4], [1], [1], [0, 1]]
という結果にする必要がある。

このデータの作り方はそんなに難しくない。枝のデータを1行ずつ読み込みながら配列に要素を追加すれば良い。

(2) 配列を元に、再帰的にf(x), g(x)を計算する



問題の解説文では、関数を定義するときはf(x)と書いてあり、xを引数にしていた。
しかし、実際のコードではf(x,p)と書かれているので「xとp」が引数である。
ではpとは何か。皆のコードを見てもしばらく分からずに悩んでいて、やっと分かった。
pは、xの親のノードである。
頂点xと繋がっている頂点の一覧は(1)の段階で作成した。
根ではない頂点を考えると、繋がっている頂点のうち1つは親、残りは子である。
関数の再帰では「頂点xの子それぞれに対して、値を求める」という操作をする。
これを言い換えると「xの隣接点の全てに対して、値を求める。ただし親pに対しては無視する」となる。

こうすると、各頂点に対して「頂点xの親は頂点pです」というデータを(例えば連想配列で)用意する必要はない。関数を呼び出す段階で、pを引数に入れればよい!
yをxの子とすると、f(x,p)を計算するにはf(y,yの親)が必要である。ここでyの親はxなので、関数呼び出しの際にはf(y,x)とすればよい。


アルゴリズムとコードの間のギャップ



解説文のアルゴリズムを読んで「納得した、確かにそのとおりだ」と思った。
しかし、コードを書こうとしても、どうすれば良いのか全然分からなくなってしまった。
つまり、解説文とソースコードとの間にギャップがあり、それを越えられなかったと言える。理論から実践までは案外遠いものである。
解説文とソースコードとのギャップは、まとめると次の2点だろう。

・「根から遠い頂点から順に求めていけばよい」と言っても、末端(グラフ理論では「葉」)を実際に指定する必要はない。根を指定して、子に対して再帰的に関数を呼び出せばよい
・そして「この点の親はどれか」という情報も明示的に保持しなくて良い。関数の引数に親の情報を入れ、子に対して呼び出す際にその点自身をパラメータに入れる

分かれば納得するけど、言われなきゃ気づかないぞ、これ。このギャップをどう埋めていけば良いんだろう。

ソースコード


そして俺が書いたコードがこちらです。
Submission #761133 - AtCoder Beginner Contest 036 | AtCoder
後学のために色々コメント書いといた。変数名もちゃんとしたものにした。時間制限があったらもっと適当な名前にすると思うw

あー。もっとrubyかけるようになろう。
それでは。
  1. 2016/06/11(土) 17:48:42|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0

FC2Ad