最長しりとり

talk

唐突に、ポケモンの名前でしりとりしたら、どれだけ長く続くだろうと思いつきました。ルールは、

  • 最後の１文字が頭文字と全く同じである場合にのみ続けられる
    • 長音や「ん」は終わり。
    • 拗音や促音も（使ってもいいルールもあるが）めんどうなのでなし。
  • 一度使った名前は二度と使ってはいけない

というもの。この問題はつなげていい名前と名前の間に距離1の有向路があるとしたグラフの最長路を求める問題になるので、当然NP困難になってしまいます。
で、Javaで全探索を書いてみたところ、
151匹（赤・緑・青・ピカチュウ）では一瞬で答えの22匹

ニョロモ→モンジャラ→ラッタ→タマタマ→マダツボミ→ミニリュウ→ウツボット→トサキント→トランセル→ルージュラ→ラフレシア→アーボック→クサイハナ→ナゾノクサ→サンド→ドガース→スリープ→プテラ→ラプラス→ストライク→クラブ→ブーバー

が出ましたが、251匹（金、銀、パール）では、五時間半走らせて40匹

エンテイ→イーブイ→イシツブテ→テッポウオ→オニスズメ→メガニウム→ムウマ→マグマラシ→シャワーズ→ズバット→トランセル→ルージュラ→ラッタ→タマタマ→マダツボミ→ミルタンク→クロバット→トゲチック→クサイハナ→ナゾノクサ→サンド→ドードリオ→オドシシ→シードラ→ラフレシア→アリアドス→スリープ→プテラ→ラプラス→ストライク→クヌギダマ→マリルリ→リングマ→マグマッグ→グランブル→ルギア→アズマオウ→ウツボット→トサキント→トゲピー

という結果でした（ただし同数解は他にあるかもしれない）。というかベイリーフは図鑑で二匹目なので全部探索するのはかなり無理。ググってみると整数計画法を使う方法があるらしいです（が、面倒なのでやらない）。
ちなみになんでこんなこと思いついたのかというと、ポケモンっていま全部で何匹いるのかなと思ってWikipediaを引いてみたからです。