問題 D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder 与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると１つの列しか作成されない。 また、全列挙(全てのノードの順列をだし、全ての有効辺を満…

有向非巡回グラフ(DAG)とは DAGとは、有向グラフ且つ閉路のないグラフのことである。これは、ある操作の手順を表す時に用いられたりする。DAGはトポロジカルソートをすることができる。 トポロジカルソートとは トポロジカルソートとは、グラフの有向辺の情…

最小全域木とは 最小全域木とは、グラフの全域の中で辺の重みの総和が最小のもの木のこと。つまり、与えられたグラフの全てのノードを含む木を作成する際に、辺の重みが最小になるように作ったものになる。この木を作成するためにプリムのアルゴリズムを用い…

最長共通部分列とは 最長共通部分列(Common Longest Subsequence)とは、２つの与えられてた列X = {x1, x2, …, xm}とY = {y1, y2, …, yn}の最長の共通部分列のことである。 例えばX = {a, b, c, d, f}, Y = {a, f, b, d, a}の最長共通部分列は{a, b, d}となる…