超簡単な自己紹介と記事作成の動機
はじめまして、一般社団法人 日本しりとり協会 公式ガイド「オシリトールはかせ」です。
エンジニア養成期間「42 Tokyo」へ2025年4月に入学し、日本しりとり協会と並行しながら42の課題に取り組んでいます。
先月11月に出展した「ゲームマーケット2025秋」と「産業交流展2025」、そして実施計画中の「全日本しりとり選手権大会」準備のため、現在はFreeze（休学）中ですが、本日は42 Tokyo Advent Calendar 2025に参加すべく、実験的に取り組んだプログラム・企画について共有します。が、
まだまだアルゴリズムもコーディングも改善の余地が大いにあるのではないかと思われる、「こんなのやってみました」レベルです。
それでも記事にすることで得るものがある、また少しでもテーマを面白がってもらえれば幸いと考え、公開する次第でございます。
「東京メトロ24時間券で回る最多駅名しりとり」導出プログラム
タイトルの通り、東京メトロ24時間券で回る最多駅名しりとりを導出するプログラムを作成しました。AIには大いに助けてもらっています。
ただし正確な所要時間を反映させることは現状できておらず、しりとりを繋ぐ2駅の名前と標準的な所要時間を与えます。
1行ごとに発駅,着駅,標準所要時間を「青山一丁目,明治神宮前,6分」といった具合で書いたテキストデータです。
よって、一般的な乗換案内サービスを用いた人間による駅ごとの発着時刻検証が最終的には必要です。（やれやれだぜ）
そして現在の結論は、「制限のない東京メトロ駅名最多しりとりは40駅だが、駅構内を走らず歩いて24時間券を使う限りは39駅が限界」というものです。
〜東京メトロ24時間券で回る駅名最多しりとり〜
広尾->大手町->地下鉄赤塚->神楽坂->葛西->飯田橋->志茂->門前仲町->浦安->水天宮前->江戸川橋->白金台->池袋->六本木一丁目->目黒->六本木->行徳->九段下->辰巳->茗荷谷->日本橋->新橋->白金高輪->和光市->新大塚->茅場町->上野広小路->神保町->上野->乃木坂->霞ケ関->北綾瀬->千駄木->銀座一丁目->明治神宮前->恵比寿->住吉->新木場->原木中山(終着)
……ここから町屋に辿り着けないのではないかとみられます。（土日祝ダイヤで広尾5:05発・原木中山23:54着）
プログラムの内容紹介
42で取り組んでいること、また動作が高速であることから、C言語にしています。
「再帰探索（DFS）」や「単純な総当たり」では計算量が爆発してしまうため、主に3点の工夫を取り入れました。
1. History Archive法：
通常の探索プログラムでは、経路を記憶するために、各ノードに「これまでの駅リスト（配列やリスト）」を持たせがちです。しかし、経路長が100を超え、候補数が数百万になると、配列のコピーだけでメモリとCPU時間を食いつぶしてしまいます。このプログラムでは、経路の「実体」をノードに持たせていません。
各ステップごとの生存ノードを history_archive[step] という巨大な配列にすべて保存し、各ノードは 「前のステップの配列のどこに親がいたか（parent_index）」 という整数値だけを持っています。
・メモリ効率：配列コピーが不要。ノードサイズが一定（軽量）。
・復元：最後にゴールが決まったら、parent_index を芋づる式に遡る（バックトラック）だけで、素早く復元できます。
これは、巨大な探索空間を扱う将棋やチェスのAIでも使われるTransposition Tableや局面管理に近い発想を、しりとり探索に応用しています。
2. ビット演算による「超高速集合管理」
「しりとりでは 同じ駅を再利用しない（通ることは複数回許容する）」という、しりとり（ハミルトンパス的）制約のチェックは、ハッシュセットやリスト探索だと時間がかかること、また東京メトロの駅数を踏まえ、固定長ビットセットを採用しています。
・current_bits & mask の論理演算一発で判定。
・「AルートとBルート、通ってきた駅の集合は同じか？」という判定が、memcmp（64bit整数4回の比較）で完了。
これらにより、後述する「重複除去」のオーバーヘッドを削減しています。
3. 「駅ごとの生存競争」を取り入れた階層型ビームサーチ
・完全重複排除：「現在地」と「訪問済み駅の集合」が完全に一致するルート同士なら、時間が短い方だけを1つ残す。
以上の3点です。
それでは、こちらにコード全体を提示します。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>
#include <stdint.h>
// --- パラメータ設定 ---
#define INPUT_FILE "tokyo-metro_shiritori-2stations-times.txt"
#define TIME_LIMIT 1140 // 制限時間[分]
#define MAX_STATIONS 256 // 駅数上限
#define MAX_NAME_LEN 64 // 駅名文字数上限
#define MAX_HISTORY_DEPTH 200 // 履歴保存配列のサイズ
// 探索幅の設定
// MAX_PER_STATION: 1つの駅あたりに保持する最大経路数
// MAX_BEAM_TOTAL: 1ステップ（深さ）あたりに保持する全経路数の上限
// 値を減らすと高速化を図れるが駅数が減ったり同駅数でも所要時間が伸びたりする
#define MAX_PER_STATION 100000
#define MAX_BEAM_TOTAL 50000000
// --- データ構造 ---
// 訪問済み駅を管理するビットセット (256ビット = 32バイト)
typedef struct {
uint64_t bits[4];
} BitSet;
typedef struct {
int to_id;
int time;
} Edge;
typedef struct {
char name[MAX_NAME_LEN];
Edge edges[16];
int edge_count;
} Station;
// 探索ノード
typedef struct {
BitSet visited; // 32 bytes: 訪問履歴
int current_id; // 4 bytes: 現在地ID
int total_time; // 4 bytes: 経過時間
int parent_index; // 4 bytes: 親ノード（history_archive）のインデックス
} Node;
// --- グローバル変数 ---
Station stations[MAX_STATIONS];
int station_count = 0;
// 次のステップの候補を展開するための巨大バッファ
Node *beam_next = NULL;
// 履歴保存用（バックトラックによる経路復元に使用）
Node *history_archive[MAX_HISTORY_DEPTH];
int history_counts[MAX_HISTORY_DEPTH];
// --- 関数プロトタイプ ---
int get_station_id(const char *name);
void add_edge(int from_id, int to_id, int time);
int compare_nodes_strict(const void *a, const void *b);
void set_bit(BitSet *bs, int n);
bool get_bit(const BitSet *bs, int n);
void *safe_malloc(size_t size);
// --- メイン処理 ---
int main() {
clock_t start_clock = clock();
int exit_status = 0;
int *path_ids = NULL;
int max_depth_reached = 0;
// 配列ポインタを初期化（クリーンアップ時の安全のため）
memset(history_archive, 0, sizeof(history_archive));
// 1. データ読み込み
FILE *fp = fopen(INPUT_FILE, "r");
if (!fp) {
printf("エラー: ファイル %s が見つかりません。\n", INPUT_FILE);
exit_status = 1;
goto cleanup;
}
char line[256];
while (fgets(line, sizeof(line), fp)) {
line[strcspn(line, "\r\n")] = 0;
if (strlen(line) == 0) continue;
char *start_name = strtok(line, ",");
char *end_name = strtok(NULL, ",");
char *time_str = strtok(NULL, ",");
if (!start_name || !end_name || !time_str) continue;
if (strstr(start_name, "出発駅")) continue;
int time_val = atoi(time_str);
if (time_val == 0 && time_str[0] != '0') continue;
int u = get_station_id(start_name);
int v = get_station_id(end_name);
if (u == -1 || v == -1) {
printf("エラー: 駅数が上限(%d)を超えました。\n", MAX_STATIONS);
fclose(fp);
exit_status = 1;
goto cleanup;
}
add_edge(u, v, time_val);
}
fclose(fp);
printf("データ読込完了: %d駅\n", station_count);
// 2. 作業用メモリ確保
size_t next_mem_size = sizeof(Node) * MAX_BEAM_TOTAL * 5;
printf("メモリ確保中... (Work buffer: ~%.1f GB)\n",
(double)next_mem_size / (1024.0 * 1024.0 * 1024.0));
beam_next = (Node *)safe_malloc(next_mem_size);
if (!beam_next) {
printf("【致命的エラー】メモリ確保に失敗しました。\n");
exit_status = 1;
goto cleanup;
}
printf("探索開始 (PerStation: %d, MaxTotal: %d)\n", MAX_PER_STATION, MAX_BEAM_TOTAL);
printf("--------------------------------------------------\n");
// 3. 初期状態（Step 0）の作成
Node *start_nodes = (Node *)safe_malloc(sizeof(Node) * station_count);
if (!start_nodes) {
exit_status = 1;
goto cleanup;
}
for (int i = 0; i < station_count; i++) {
Node *n = &start_nodes[i];
n->current_id = i;
n->total_time = 0;
n->parent_index = -1;
memset(&n->visited, 0, sizeof(BitSet));
set_bit(&n->visited, i);
}
history_archive[0] = start_nodes;
history_counts[0] = station_count;
// 4. ループ探索 (Step 0 -> Step 1 -> ...)
for (int step = 0; step < MAX_HISTORY_DEPTH - 1; step++) {
Node *source = history_archive[step];
int source_cnt = history_counts[step];
int next_cnt = 0;
// --- A. 展開フェーズ ---
for (int i = 0; i < source_cnt; i++) {
Node *p = &source[i];
Station *s = &stations[p->current_id];
for (int k = 0; k < s->edge_count; k++) {
int neighbor = s->edges[k].to_id;
int cost = s->edges[k].time;
// 訪問済みチェック
if (get_bit(&p->visited, neighbor)) continue;
// 時間制限チェック
if (p->total_time + cost > TIME_LIMIT) continue;
// バッファ上限チェック
if (next_cnt >= MAX_BEAM_TOTAL * 5) break;
// 新しいノードの生成
Node *child = &beam_next[next_cnt++];
child->current_id = neighbor;
child->total_time = p->total_time + cost;
child->parent_index = i;
child->visited = p->visited;
set_bit(&child->visited, neighbor);
}
}
if (next_cnt == 0) {
printf("\nこれ以上進めません (Depth %d で終了)\n", step + 1);
max_depth_reached = step;
break;
}
// --- B. 選抜フェーズ (Sort & Prune) ---
qsort(beam_next, next_cnt, sizeof(Node), compare_nodes_strict);
int survived_cnt = 0;
int current_st = -1;
int count_per_st = 0;
Node *last_kept = NULL;
for (int i = 0; i < next_cnt; i++) {
Node *curr = &beam_next[i];
if (curr->current_id != current_st) {
current_st = curr->current_id;
count_per_st = 0;
last_kept = NULL;
}
// 1. 完全重複排除
if (last_kept != NULL) {
if (memcmp(&last_kept->visited, &curr->visited, sizeof(BitSet)) == 0) {
continue;
}
}
// 2. 駅ごとの生存数制限
if (count_per_st >= MAX_PER_STATION) {
continue;
}
// 3. 全体上限チェック
if (survived_cnt >= MAX_BEAM_TOTAL) {
break;
}
if (i != survived_cnt) {
beam_next[survived_cnt] = *curr;
}
last_kept = &beam_next[survived_cnt];
survived_cnt++;
count_per_st++;
}
// --- C. 履歴の確定保存 ---
history_archive[step + 1] = (Node *)safe_malloc(sizeof(Node) * survived_cnt);
if (!history_archive[step + 1]) {
printf("メモリ確保失敗。ここで終了します。\n");
max_depth_reached = step;
exit_status = 1;
goto cleanup;
}
memcpy(history_archive[step + 1], beam_next, sizeof(Node) * survived_cnt);
history_counts[step + 1] = survived_cnt;
max_depth_reached = step + 1;
// 進捗表示
if ((step + 1) % 2 == 0 || (step + 1) > 35) {
printf("Step %2d: 候補数 %8d -> %8d (生存率 %.1f%%)\n",
step + 1, next_cnt, survived_cnt, (double)survived_cnt/next_cnt*100.0);
}
}
// 5. 結果集計とバックトラック
printf("--------------------------------------------------\n");
printf("【最終結果集計中...】\n");
Node *finals = history_archive[max_depth_reached];
int f_cnt = history_counts[max_depth_reached];
int best_idx = -1;
int min_time = 999999;
for (int i = 0; i < f_cnt; i++) {
if (finals[i].total_time < min_time) {
min_time = finals[i].total_time;
best_idx = i;
}
}
printf("最大訪問駅数: %d 駅 (初期駅含む)\n", max_depth_reached + 1);
printf("所要時間合計: %d 分\n", min_time);
if (best_idx == -1) {
printf("有効な経路が見つかりませんでした。\n");
goto cleanup;
}
path_ids = (int *)safe_malloc(sizeof(int) * (max_depth_reached + 1));
if (!path_ids) {
exit_status = 1;
goto cleanup;
}
int curr_idx = best_idx;
// 親インデックスを辿って経路復元
for (int d = max_depth_reached; d >= 0; d--) {
Node *n = &history_archive[d][curr_idx];
path_ids[d] = n->current_id;
curr_idx = n->parent_index;
}
printf("\n(ルート出力)\n");
for (int i = 0; i <= max_depth_reached; i++) {
printf("%s%s", stations[path_ids[i]].name, (i < max_depth_reached) ? "->" : "");
}
printf("\n\n詳細:\n");
int t_sum = 0;
for (int i = 0; i <= max_depth_reached; i++) {
int id = path_ids[i];
int cost = 0;
if (i > 0) {
Station *s = &stations[path_ids[i-1]];
for(int k=0; k<s->edge_count; k++){
if(s->edges[k].to_id == id) {
cost = s->edges[k].time;
break;
}
}
}
t_sum += cost;
printf("%2d. %s (区間%d分, 計%d分)\n", i+1, stations[id].name, cost, t_sum);
}
double elapsed = (double)(clock() - start_clock) / CLOCKS_PER_SEC;
printf("\n実行時間: %.2f秒\n", elapsed);
// 終了処理（クリーンアップ）
cleanup:
if (beam_next) free(beam_next);
if (path_ids) free(path_ids);
for (int i = 0; i < MAX_HISTORY_DEPTH; i++) {
if (history_archive[i]) free(history_archive[i]);
}
return exit_status;
}
// --- 実装詳細 ---
int get_station_id(const char *name) {
for (int i = 0; i < station_count; i++) {
if (strcmp(stations[i].name, name) == 0) return i;
}
if (station_count >= MAX_STATIONS) {
return -1; // 上限エラー
}
strcpy(stations[station_count].name, name);
stations[station_count].edge_count = 0;
return station_count++;
}
void add_edge(int from_id, int to_id, int time) {
Station *s = &stations[from_id];
if (s->edge_count < 16) {
s->edges[s->edge_count].to_id = to_id;
s->edges[s->edge_count].time = time;
s->edge_count++;
} else {
printf("警告: 駅 %s の接続数が上限を超えています。\n", s->name);
}
}
int compare_nodes_strict(const void *a, const void *b) {
const Node *na = (const Node *)a;
const Node *nb = (const Node *)b;
if (na->current_id != nb->current_id)
return na->current_id - nb->current_id;
int cmp = memcmp(&na->visited, &nb->visited, sizeof(BitSet));
if (cmp != 0) return cmp;
return na->total_time - nb->total_time;
}
void set_bit(BitSet *bs, int n) {
bs->bits[n / 64] |= (1ULL << (n % 64));
}
bool get_bit(const BitSet *bs, int n) {
return (bs->bits[n / 64] & (1ULL << (n % 64))) != 0;
}
void *safe_malloc(size_t size) {
void *ptr = malloc(size);
if (!ptr && size > 0) {
printf("【警告】メモリ確保失敗 (%zu bytes)。\n", size);
}
return ptr;
}
最後に……
先日テストプレイとして約20駅、しりとりせずに効率よく回ってみましたが、
ちょ〜疲れる！！！！
ので、ありがたくも実践してくださる方は、ぜひ体力と精神力にお気をつけください。
乗車も乗換も、通常の長旅と違う疲れを誘うので、青春１８キッパーさんなども油断なさいませぬよう。
それでは、また別のネタでお目にかかれれば幸いです。
お読みくださりありがとうございました！
PR
先月開催の「ゲームマーケット2025秋」に出品した『ゴリラしりとり』が昨日、名だたるゲームデザイナーさんたちによる配信で話題にあがりました。一度話題が終わろうとしているところで蒸し返されるくらいに！笑
面白そうな作品が数多く紹介されている配信なので、ゴリラしりとりの部分に限らずお楽しみくださいな。1:08:50ごろから、約7分間も！笑
— しりとり協会（一般社団法人日本しりとり協会） (@Shiritori_SRTR) December 7, 2025
コンポーネントお買い上げ→ご紹介いただいた秋山乃佑（ダイスケ）@daisuke_ak_gameさん、説明していただいた米光一成さん@yonemitsuはじめ、みなさま盛り上がってくださり嬉しい限りです。ありがとうございました！！#ゲムマ2025秋 #ゲームマーケット2025秋 https://t.co/GvtUaFuOoT
また、ゴリラしりとりの説明書をHTML/CSSコードとしてAI生成した話はnoteの記事にしました。
まだ少ない事例だと思うので、ご参考になれば嬉しいです！ゲームマーケット2025秋で出品した『ゴリラしりとり』について、マニュアルをAI生成した話をnoteで記事にしました。https://t.co/3GXxzP0Eyl
— しりとり協会（一般社団法人日本しりとり協会） (@Shiritori_SRTR) December 5, 2025
直接生成できるAIは限られ「A4両面印刷でA5版4ページになるウェブサイト」としてHTML/CSSのコードをAIに生成してもらう話です。#ゲームマーケット #ゲムマ