アルゴリズムとかオーダーとか

仕事で勉強したことなどをまとめてます

トロポジカルソートの数え上げとDP(1)

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder

が解説を見てもさっぱりわからなかくて数日頭を悩ませているので、理解できたものから少しずつまとめていこうと思います。

 

まず、初っ端につまづいたのが次の一文

頂点集合 S をトポロジカルソートするとき,頂点 v ∈ S が最も右に置かれるた めの必要十分条件を考えてみます.

 さっぱりわかりません。まずなんで「頂点 v ∈ S が最も右に置かれる」こと考えてるんだろ???な状態でした。

 

これについては普通の順列の個数を求めることを考えることで理解できました。

 

4つの要素{A, B, C, D}からなる順列について上記の意味を考えます。

上の説明の通り、{A, B, C, D}について、要素Dが一番右にくる組み合わせの個数を考えると、残りの3つの要素{A, B, C}からなる順列の組み合わせの個数と同じになります。

 

まぁちょっと考えればすぐわかる当たり前のことなのですが、4つの要素からなる順列のうち、3つまでの要素が決定されていたら残りの選択肢は1つしかないですもんね。

 同じように、さらに要素を減らしながら個数を数えていけば順列の全ての組み合わせの個数が求まります。

 

以上から、要素数nの順列 \{a_1, a_2, ... a_n\}に対する組み合わせの個数 S(n)を求める方法を漸化式で表すと以下になります。

{\begin{align} S(n) = S(n-1) \times n \end{align}}

 

要素nの中から1つの要素を取り除いてできる順列の個数を、要素数n回分足しあわせたもの ということですね。要素数が4つであれば

 \begin{align} \{要素数3つの組み合わせの数\} \times 4 = \\ (\{要素数2つの組み合わせの数\} \times 3) \times 4 ... \end{align}

とすればもとまるわけです。これは順列の組み合わせを求める式 n!にも一致します。

 

ということで、順列のこの法則に乗せるために、一番右(最後)に来る要素vについて考える必要があるわけですね。

なるほど〜。

 

今回はここまで。