各接点は出枝、入枝をそれぞれd本ずつもっているグラフのこと。このグラフの事をd正則有向グフラと呼ぶ。グラフは以下のコンポーネントで成り立つ。与えられたノードからスタートし、宝石を全て取得するように巡回し始めのノードに戻ってくるルートの最短距離を求める問題。与えられたDAGをトポロジカルソートしてできる列の通り数を数え上げる問題。普通にトポロジカルソートすると1つの列しか作成されない。DAGとは、有向グラフ且つ閉路のないグラフのことである。これは、ある操作の手順を表す時に用いられたりする。DAGはトポロジカルソートをすることができる。最小全域木とは、グラフの全域の中で辺の重みの総和が最小のもの木のこと。与えられたグラフの全てのノードを含む木を作成する際に、辺の重みが最小になるように作ったものになる。滞在する必要のある頂点は1つと考える。滞在する頂点を頂点iとすると、頂点0から最短で頂点iに到達し、できるだけ長く頂点iに滞在し、最短で頂点0に戻る事を考える。全ての数字と数字の間に対して、「+」を入れる場合と入れない場合で全列挙。全探索では計算量がO(2n)となり間に合わない。よって動的計画法を用いて解く。部分問題を解き、その計算結果を保存し再利用することで全体の問題が解ける。問題の入力値から、上司と部下の関係をグラフを起こす。すると、今回の問題では部下に対する上司の人数は必ず1人なので木構造になる。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。