WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。普通にdfsで探索すると計算量がやばい。下図のような構成となっているグラフで、赤い頂点から探索を進めた日にゃあスタート頂点1つにつき計算量がO(M^2)になる。dfsで探索しても計算量はいける。}};Editorialhttps://apps.topcoder.com/wiki/display/tc/SRM+682この問題はいくつかのアプローチがある。1つに、「a->b->c->d」というような4つの異なる頂点のパスを見つけ出す方法を考えればよいと、問題を簡単にしてしまう方法がある。このようなパスを見つけることができたら、あとはそこに繋がる頂点iを見つける必要があるだけである。4つの長さのパスを全て列挙したとして、aに接続したiを探すことになる。c,そしてdとは異なる最初のiであればよく、aと隣接した頂点を走査すれば、高々5回試せばよい。要する計算量は長さ4のシンプルパスの数に5を掛けたものとなる。c->d」のような3つの辺で構成される。c->d」といった隣接した頂点のペアは高々O(M^2)である。それぞれにおいて、「b->c」といった中間の辺で繋がっているかを確認する。これは頂点が他の頂点と隣接しているかのマトリクスを予め計算しておけばO(1)となる。「a->b->c->d」が繋がっていることを確認できたら、最後に全ての頂点が異なることを確認する。この方法では、長さ4のシンプルパスを見つけるためにO(M^2)の計算量を要する。上記の通り、高々5回の計算で5つ目の頂点が見つかるため、全体の計算量もO(M^2)である。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。