import sys def solve_shiritori(word_list): """ 与えられた単語リストから、最も長く続くしりとりのパターンを探します。 【高速化のポイント】 1. 自己ループ（始点と終点が同じ単語）の集約: "A...A" のような単語は、その文字を通る際にまとめて使用できるため、 個別の探索を行わず、そのノードに到達した時点で一括して連結します。 2. 多重辺（同じ始点・終点を持つ単語群）の枝刈り: "A...B" という単語が複数ある場合、どれを使ってもグラフ上の移動先は同じ "B" です。 したがって、その中から1つだけを選んで探索を進めることで、 重複した探索（順序の入れ替え等）を省略し、計算量を劇的に削減します。 """ # グラフ構築 # edges[start][end] = [word1, word2, ...] edges = {} # self_loops[char] = [word1, word2, ...] self_loops = {} # 探索開始地点の候補となる文字セット start_chars = set() for w in word_list: if not w: continue start = w[0] end = w[-1] start_chars.add(start) if start == end: if start not in self_loops: self_loops[start] = [] self_loops[start].append(w) else: if start not in edges: edges[start] = {} if end not in edges[start]: edges[start][end] = [] edges[start][end].append(w) longest_chain = [] def dfs(current_node, current_chain): nonlocal longest_chain # 1. 自己ループ単語を回収 # このノードにある自己ループ単語を全てチェーンに追加します。 # これらは順序不同でまとめてしまって問題ありません。 popped_loops = [] if current_node in self_loops and self_loops[current_node]: popped_loops = list(self_loops[current_node]) self_loops[current_node].clear() # 使用済みにする（再帰中は使えないように） current_chain.extend(popped_loops) # 暫定最長の更新チェック if len(current_chain) > len(longest_chain): longest_chain = list(current_chain) # 進捗表示と被らないように改行を入れてから表示 print(f"\n暫定最長 ({len(longest_chain)}語): {' -> '.join(longest_chain)}") # 2. 次のノードへ遷移 if current_node in edges: # 遷移可能な次の文字（end_char）のリスト next_nodes = list(edges[current_node].keys()) for next_node in next_nodes: word_list_for_edge = edges[current_node][next_node] if word_list_for_edge: # 【重要】枝刈り # start->end への単語が複数あっても、グラフ構造上の遷移先は同じなので、 # 1つの単語だけを選んで探索すれば十分です。 # これにより探索空間を劇的に削減します。 w = word_list_for_edge.pop() current_chain.append(w) # 「ん」で終わる場合はそこで終了 if next_node == 'ん' or next_node == 'ン': if len(current_chain) > len(longest_chain): longest_chain = list(current_chain) print(f"\n暫定最長 ({len(longest_chain)}語): {' -> '.join(longest_chain)}") else: dfs(next_node, current_chain) # バックトラック（状態を戻す） current_chain.pop() word_list_for_edge.append(w) # 3. 自己ループ単語を戻す（バックトラック） if popped_loops: # 追加した分を削除 del current_chain[-len(popped_loops):] self_loops[current_node].extend(popped_loops) # 全ての文字を始点として探索 sorted_start_chars = sorted(list(start_chars)) total_chars = len(sorted_start_chars) for i, start_char in enumerate(sorted_start_chars): sys.stderr.write(f"\r進捗: {i + 1}/{total_chars} 文字目 ({start_char}) を探索中...") sys.stderr.flush() # 始点として探索開始 dfs(start_char, []) sys.stderr.write("\n") return longest_chain if __name__ == "__main__": # テスト用データ # words = [ # "りんご", "ごりら", "らっぱ", "ぱんだ", # "だちょう", "うし", "しか", "かめ", # "めだか", "からす", "すずめ", "めじろ", # "ろっぱ", "ぱいなっぷる", "るびー" # ] # print(f"入力リスト: {words}") # result = solve_shiritori(words) # print(f"\n最長しりとり ({len(result)}語):") # print(" -> ".join(result)) names = [ "アイスランド", "アイルランド", "アゼルバイジャン", "アフガニスタン", "アメリカ", "アラブ首長国連邦／シュチョウコクレンポウ", "アルジェリア", "アルゼンチン", "アルバニア", "アルメニア", "アンゴラ", "アンティグア・バーブーダ", "アンドラ", "イエメン", "イスラエル", "イタリア", "イラク", "イラン", "インド", "インドネシア", "ウガンダ", "ウクライナ", "ウズベキスタン", "ウルグアイ", "エクアドル", "エジプト", "エストニア", "エスワティニ", "エチオピア", "エリトリア", "エルサルバドル", "オーストラリア", "オーストリア", "オマーン", "オランダ", "ガーナ", "カーボヴェルデ", "ガイアナ", "カザフスタン", "カタール", "カナダ", "ガボン", "カメルーン", "ガンビア", "カンボジア", "キタマケドニア／北マケドニア", "ギニアビサウ", "ギニア", "キプロス", "キューバ", "ギリシャ", "キリバス", "キルギス", "グアテマラ", "クウェート", "クック諸島／ショトウ", "グレート・ブリテン及び北部アイルランド連合王国／オウコク", "グレナダ", "クロアチア", "ケニア", "コートジボワール", "コスタリカ", "コモロ", "コロンビア", "コンゴ", "コンゴ民主共和国／キョウワコク", "サウジアラビア", "サモア", "サントメ・プリンシペ", "ザンビア", "サンマリノ", "シエラレオネ", "ジブチ", "ジャマイカ", "ジョージア", "シリア", "シンガポール", "ジンバブエ", "スイス", "スウェーデン", "スーダン", "スペイン", "スリナム", "スリランカ", "スロバキア", "スロベニア", "セーシェル", "セキドウ／赤道ギニア", "セネガル", "セルビア", "セントクリストファー・ネーヴィス", "セントビンセントおよびグレナディーン諸島／ショトウ", "セントルシア", "ソマリア", "ソロモン", "タイ", "ダイカン／大韓民国／ミンコク", "タジキスタン", "タンザニア", "チェコ", "チャド", "チュウオウ／中央アフリカ", "チュウカ／中華人民共和国／キョウワコク", "チュニジア", "チリ", "ツバル", "デンマーク", "ドイツ", "トーゴ", "ドミニカ", "トリニダード・トバゴ", "トルクメニスタン", "トルコ", "トンガ", "ナイジェリア", "ナウル", "ナミビア", "ニウエ", "ニカラグア", "ニジェール", "日本", "ニュージーランド", "ネパール", "ノルウェー", "バーレーン", "ハイチ", "パキスタン", "バチカン", "パナマ", "バヌアツ", "バハマ", "パプアニューギニア", "パラオ", "パラグアイ", "バルバドス", "ハンガリー", "バングラデシュ", "ヒガシ／東ティモール", "フィジー", "フィリピン", "フィンランド", "ブータン", "ブラジル", "フランス", "ブルガリア", "ブルキナファソ", "ブルネイ・ダルサラーム", "ブルンジ", "ベトナム", "ベナン", "ベネズエラ", "ベラルーシ", "ベリーズ", "ペルー", "ベルギー", "ポーランド", "ボスニア・ヘルツェゴビナ", "ボツワナ", "ボリビア", "ポルトガル", "ホンジュラス", "マーシャル諸島／ショトウ", "マダガスカル", "マラウイ", "マリ", "マルタ", "マレーシア", "ミクロネシア", "ミナミ／南アフリカ", "ミナミ／南スーダン", "ミャンマー", "メキシコ", "モーリシャス", "モーリタニア", "モザンビーク", "モナコ", "モルディブ", "モルドバ", "モロッコ", "モンゴル", "モンテネグロ", "ヨルダン", "ラオス", "ラトビア", "リトアニア", "リビア", "リヒテンシュタイン", "リベリア", "ルーマニア", "ルクセンブルク", "ルワンダ", "レソト", "レバノン", "ロシア", ] result = solve_shiritori(names) print(f"\n最長しりとり ({len(result)}国):") print(" -> ".join(result))