問題
3文字の文字列がn個与えられる。これらの文字列を連続部分文字列として含むような文字列を構成せよという問題。解法
以前紹介したしりとりの問題と同じような感じでやってDFSする。しかし文字の種類が62種類あり、グラフのノード数はその二乗あるので上手くDFSしなきゃいけない。
登録:
コメントの投稿 (Atom)
講義資料をNotionで書いてみた
プログラミング応用という名前の講義を受け持っており, そこで組合せ最適化のベーシックな話題とそのPythonでの実装を教えているのですが, 資料をNotionで書いてみました. 講義資料をNotionで公開しているのでアルゴリズムの基礎とかNP困難性とかを勉強したい人はどう...
-
0. 概要 本記事では ランダムグラフ理論の動機と応用 ランダムグラフ理論のさわり ランダムグラフの面白い定理 について書きます. 1. ランダムグラフ理論の動機と応用 ランダムグラフ理論の主な動機としては 「とある性質Pを満たすグラフ... -
0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つで... -
1. 全点対最短経路問題の計算量の外観 グラフ $G$ が与えられたときに 全点対最短経路 ( APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと...
0 件のコメント:
コメントを投稿