S Recolorable BFUW

この問題では生成AIの利用を認めます。

頂点に色が塗られた無向グラフ上を自律的に移動するロボットがいます。 ロボットはグラフの全体構造を知らず、現在いる頂点の色と隣接する頂点の色のみをローカルに観測して次の行動を決定します。

本問題の目的は、与えられた \(10\) 個の無向グラフ \(G_1, G_2, \ldots, G_{10}\) のそれぞれについて、ロボットが「すべての頂点を訪問し、開始頂点に戻って停止する」ための行動ルールを設計することです。 グラフごとに異なるルールを使用できます。 得点計算はScoringセクションを参照してください。

ロボットの仕様と操作

各頂点には色が塗られており、初期状態ではすべての頂点の色は \(1\) です。 ロボットは内部状態を持たず、頂点番号、移動履歴、開始頂点、訪問済みかどうかを直接知ることはできません。 隣接頂点の色は多重集合として観測し、同じ色の隣接頂点同士は区別できません。 同じグラフでは、開始頂点によらず同じルールを使用します。

毎ステップ、ロボットは現在の頂点で以下の操作をこの順序で実行します。

1. 現在の頂点を指定した色に再彩色（Recolor）する。
2. 指定した色の隣接頂点へ移動（Move）する、その場に留まる、または停止（Stop）する。

ルールの記述フォーマット

行動ルールは以下のような \(1\) 行 \(1\) ルールのCSV形式（\(4\) 列）で記述します。 ルールは上から順に評価されるfirst-match方式であり、最初に条件を満たした \(1\) 行のみが適用されます。 空行および各行の # 以降はコメントとして無視されます。 色番号には \(1\) 以上 \(8\) 以下の整数を使用し、波括弧内のカンマは列の区切りに数えません。

CUR, NEI_PRED, REPAINT, MOVE

各列の仕様を以下に示します。 CUR と NEI_PRED の両方が真のとき、そのルールがマッチします。 条件は再彩色の前に判定します。

CUR（現在の頂点の色条件）

• *：任意の色（常に一致）。
• c：色 \(c\) と一致。
• {A_1,A_2,...,A_k} または A_1|A_2|...|A_k：指定した色のいずれか（OR指定）。

NEI_PRED（隣接頂点の色条件）

• *：任意（常に一致）。
• ex(c)：色 \(c\) の隣接頂点が \(1\) つ以上存在する。
• all(c)：すべての隣接頂点が色 \(c\) である。
• {1,2,2}：隣接頂点の色の多重集合が厳密に一致する（未指定の色が混ざると不一致）。
• {1,2+} / {1,2*}：+ は \(1\) 個以上、* は \(0\) 個以上の繰り返しを意味する。
• ! または not：条件の否定（NOT）。例：!ex(1), not ex(1)。
• &：論理積（AND）。例：ex(2)&ex(3)。
• |：論理和（OR）。例：ex(1)|ex(2)。

論理演算子の優先順位はNOT、AND、ORの順です。 否定は ex と all に使用できます。 述語全体を囲む括弧（例：(ex(1)|ex(2))&ex(3)）は使えません。 多重集合条件と論理演算は併用できます（例：{1,2}&ex(3)|all(4)）。

REPAINT（現在の頂点の塗り替え先）

• SAME：色を変更しない。
• 数値：指定した色に塗り替える。

MOVE（次の行動）

• 数値：その色の隣接頂点へ移動する。候補が複数ある場合は非決定的に分岐する。該当する隣接頂点が存在しない場合は NoTargetNeighbor エラーとなり不正解。
• STAY：移動せず現在の頂点に留まる。再彩色は反映され、次のステップへ進む。
• STOP：停止する。ただし、全頂点訪問と開始頂点への帰還を満たしていない場合は不正解。

行動ルールの適用例

あるステップにおいて、ロボットが現在いる頂点 \(v\) の色が \(1\) であり、隣接する頂点の色がそれぞれ \(1,2,2\) であったとします。 以下のルールが設定されているとします。

1, all(1), 2, 1
1, ex(2), 3, 2
*, *, SAME, STOP

ロボットは上から順にルールを評価します。

• 1行目 1, all(1), 2, 1：現在の色は \(1\) ですが、隣接頂点の色がすべて \(1\) ではないためスキップします。
• 2行目 1, ex(2), 3, 2：現在の色が \(1\) で、かつ隣接頂点に色 \(2\) が存在するため、条件に一致します。

条件に一致した \(2\) 行目が適用され、以下の操作が実行されます。

• 再彩色：頂点 \(v\) の色を \(3\) に塗り替えます。
• 移動：色 \(2\) の隣接頂点へ移動します。この例では色 \(2\) の隣接頂点が \(2\) つ存在するため、ジャッジは両方の分岐を検証します。

探索の成功条件と非決定性

ジャッジは、与えられたグラフのすべての頂点を開始頂点として個別にシミュレーションを行います。 移動先の候補が複数存在する場合、ジャッジはすべての分岐を検証します。 以下の条件を、すべての開始頂点およびすべての分岐で満たした場合のみ、そのグラフに対する解は「正しい」と判定されます。

1. すべての頂点を少なくとも \(1\) 回訪問する。
2. 最後に開始頂点に戻る。
3. 開始頂点で停止（STOP）する。

開始頂点は最初から訪問済みとし、停止時の各頂点の色は問いません。 移動先の選ばれ方に制約はなく、各候補がいつか必ず選ばれるという保証もありません。 \(1\) つの分岐でも失敗する場合や、停止しない場合は不正解です。 一致するルールがない場合も失敗とします。

制限

• 出力サイズ：\(1\) テストあたり \(1048576\) バイト以下。
• ルール数：\(1000\) 行以下（空行とコメントを除く）。
• 手数：各実行について、移動と STAY の合計が \(19999\) 回以下。STOP は手数に数えない。
• 検証状態数：各開始頂点から到達可能な状態が \(250000\) 個以下。

検証状態は、現在位置、全頂点の色、訪問済み頂点の集合の組です。 開始頂点ごとに、全分岐で到達する異なる状態を数え、初期状態と停止直前の状態も含めます。 上限を超えた場合は不正解です。

対象グラフの構造

各グラフ \(G_T\) は以下の辺リストで定義されます。 頂点番号は \(1\) から頂点数までです。

\(G_{1}\)（\(8\) 頂点、\(8\) 辺）

\(\{1,2\}\), \(\{1,8\}\), \(\{2,3\}\), \(\{3,4\}\), \(\{4,5\}\), \(\{5,6\}\), \(\{6,7\}\), \(\{7,8\}\)。

\(G_{2}\)（\(6\) 頂点、\(6\) 辺）

\(\{1,3\}\), \(\{1,4\}\), \(\{1,5\}\), \(\{1,6\}\), \(\{2,3\}\), \(\{2,4\}\)。

\(G_{3}\)（\(6\) 頂点、\(6\) 辺）

\(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{2,3\}\), \(\{2,5\}\), \(\{5,6\}\)。

\(G_{4}\)（\(6\) 頂点、\(7\) 辺）

\(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{2,3\}\), \(\{4,5\}\), \(\{4,6\}\), \(\{5,6\}\)。

\(G_{5}\)（\(8\) 頂点、\(12\) 辺）

\(\{1,2\}\), \(\{1,4\}\), \(\{1,5\}\), \(\{2,3\}\), \(\{2,8\}\), \(\{3,4\}\), \(\{3,7\}\), \(\{4,6\}\), \(\{5,6\}\), \(\{5,8\}\), \(\{6,7\}\), \(\{7,8\}\)。

\(G_{6}\)（\(6\) 頂点、\(12\) 辺）

\(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{1,5\}\), \(\{2,3\}\), \(\{2,4\}\), \(\{2,6\}\), \(\{3,5\}\), \(\{3,6\}\), \(\{4,5\}\), \(\{4,6\}\), \(\{5,6\}\)。

\(G_{7}\)（\(9\) 頂点、\(13\) 辺）

\(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{1,5\}\), \(\{2,3\}\), \(\{2,6\}\), \(\{2,7\}\), \(\{3,8\}\), \(\{4,6\}\), \(\{4,9\}\), \(\{6,9\}\), \(\{7,8\}\), \(\{7,9\}\)。

\(G_{8}\)（\(7\) 頂点、\(10\) 辺）

\(\{1,2\}\), \(\{1,3\}\), \(\{2,3\}\), \(\{2,4\}\), \(\{3,4\}\), \(\{4,5\}\), \(\{4,6\}\), \(\{5,6\}\), \(\{5,7\}\), \(\{6,7\}\)。

\(G_{9}\)（\(6\) 頂点、\(9\) 辺）

\(\{1,2\}\), \(\{1,3\}\), \(\{2,3\}\), \(\{2,4\}\), \(\{2,5\}\), \(\{3,5\}\), \(\{3,6\}\), \(\{4,5\}\), \(\{5,6\}\)。

\(G_{10}\)（\(12\) 頂点、\(21\) 辺）

\(\{1,2\}\), \(\{1,3\}\), \(\{1,4\}\), \(\{1,5\}\), \(\{2,3\}\), \(\{2,4\}\), \(\{2,5\}\), \(\{2,7\}\), \(\{2,8\}\), \(\{3,5\}\), \(\{4,7\}\), \(\{5,7\}\), \(\{5,9\}\), \(\{6,7\}\), \(\{6,10\}\), \(\{7,8\}\), \(\{7,9\}\), \(\{8,9\}\), \(\{10,11\}\), \(\{10,12\}\), \(\{11,12\}\)。

ツール

ビジュアライザを以下のURLで公開しています。

https://littlegirl0820.github.io/recolorable-bfuw/

ビジュアライザでは、サンプルとして一般グラフ用 \(8\) 色アルゴリズムを読み込めます。 これは以下の論文で提案されている「\(7\) 色アルゴリズム（Algorithm 5）」を本問題の記述形式に書き起こしたものです。 出典論文では初期色を使用色数に含めませんが、本問題では初期色も \(1\) 色としてカウントするため、\(8\) 色として扱います。

• サンプルアルゴリズム出典論文：https://arxiv.org/abs/2301.13860
• 本問題のモデル定義のベース論文：https://arxiv.org/abs/2505.02789

ビジュアライザでは、ルールの構文チェック、ステップ実行、全開始頂点と全分岐の検証、採点、提出用コードの生成が行えます。 「最小番号」や手動選択による実行はデバッグ用です。 提出前には「このケースを検証」または「全ケースを採点」で確認してください。