HACK TO THE FUTURE 2026 （AtCoder Heuristic Contest 056）

A - Grid Turing Robot

Time Limit: 2 sec / Memory Limit: 1024 MiB

ストーリー

「チューリングマシン」は計算理論で用いられる仮想的な計算機であり、一次元のテープ上で、遷移規則にしたがって内部状態（マシンに搭載されたメモリの値）とヘッド位置の文字を書き換えながらヘッドを左右に動かして計算を行うものである。

F社は、その仕組みを模したロボットを開発している。このロボットは、二次元のグリッド状の盤面上で、遷移規則にしたがって内部状態と現在位置の色を書き換えながら、上下左右に移動することができる。目的地を指定された順に訪問するよう、このロボットの遷移規則を設計してほしい。開発コストは使用する色数と状態数の和に比例するため、できるだけ小さい和で実現することが望ましい。

問題文

N\times N マスの盤面がある。左上のマスの座標を (0, 0) とし、下方向に i、右方向に j 進んだ位置の座標を (i, j) とする。 N\times N マスの外周は壁で囲まれており、また、隣接するマスの間にも壁が存在する場合がある。

各マスには色を塗ることができる。使用する色の総数を C とし、各色は整数 0,1,\ldots,C-1 で表す。初期状態の盤面の色は自由に設定してよい。

ロボットは、内部状態 を表す変数を1つ持つ。この内部状態は整数 0,1,\ldots,Q-1 のいずれかの値をとる。取りうる状態の総数 Q は自由に設定してよい。内部状態の初期値は 0 である。

ロボットは現在位置の色 c と内部状態 q に基づいて、次の行動を決定し、以下の3つの操作を同時に行う。

現在位置の色を A(c, q) に塗り替える（現在と同じ色に塗り替えてもよい）。
内部状態を S(c, q) に更新する（現在と同じ内部状態に更新してもよい）。
D(c, q) の方向に移動する（上・下・左・右・移動しない）。移動先との間に壁がある場合、ロボットは移動できずその場に留まる。

ここで、A, S, D はそれぞれ 遷移規則 を表す関数である。遷移規則は動作開始前に設計し、動作中に変更することはできない。また、ロボットの行動は現在位置そのものには依存せず、現在位置の色と内部状態のみによって決定される。

ロボットの動作例

上図の例ではまず、3\times 3 の盤面が青色に塗られた状態で位置 (0, 0) から動作を開始し、以下の3つの遷移規則に従って動作する。

A(青,0)=緑, S(青,0)=0, D(青,0)=右

A(緑,0)=青, S(緑,0)=1, D(緑,0)=左

A(緑,1)=緑, S(緑,1)=1, D(緑,1)=下

最初の3ステップでは遷移規則 1 が繰り返し適用され、緑色に塗り替えつつ右へ進む。3ステップ目では壁にぶつかるため、移動できずその場にとどまる。 4ステップ目は現在位置が緑色のため、遷移規則 2 が適用され、青色に塗り替えながら左に移動し、内部状態が 1 へと切り替わる。最後に5ステップ目では、現在位置が緑色かつ内部状態が 1 のため、遷移規則 3 が適用され、下に移動する。

K 箇所の目的地の列 (x_0,y_0),(x_1,y_1),\ldots,(x_{K-1},y_{K-1}) と、ステップ数の上限 T が与えられる。ロボットは (x_0,y_0) のマスからスタートし、T ステップ以内に、指定された順にすべての目的地を訪れることを目指す。

ここで、目的地が (x_i,y_i) のとき、まだ順番が来ていない (x_j,y_j)（j>i）のマスを先に訪れても、訪問したことにはならない。実際に (x_j,y_j) が次の目的地になった時点で、その目的地に改めて到達しなければならない。

すべての目的地を順に訪問できるように、盤面の初期色の配置とロボットの遷移規則を設計せよ。

得点

使用する色数を C、状態数を Q、ステップ数の上限 T 以内に訪問できた目的地の数を V とする。このとき、以下の絶対スコアが得られる。

V=K の場合、C+Q
V<K の場合、2N^4 + (K-V)\times N^2

絶対スコアは小さければ小さいほど良い。

各テストケース毎に、\mathrm{round}(10^9\times \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) の相対評価スコアが得られ、その和が提出の得点となる。

最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。システムテストは CE 以外の結果を得た一番最後の提出に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。

テストケース数

暫定テスト: 50個
システムテスト: 2000個、コンテスト終了後に seeds.txt (sha256=c7a6f9526da67d83d1f8fed006e1b8f5edc8e4134444cf954e400a4dcd8bd130) を公開

相対評価システムについて

暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。

順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。

実行時間について

実行時間には多少のブレが生じます。また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。

入力

入力は以下の形式で標準入力から与えられる。

N K T
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
x_0 y_0
\vdots
x_{K-1} y_{K-1}

盤面の大きさ N は 10\leq N\leq 20 を満たす。
目的地の個数 K は N\leq K\leq N^2 を満たす。
すべての目的地を順に訪れる最小移動回数を X とすると、ステップ数の上限 T は X\leq T\leq 2X を満たす。
v_{i,0} \cdots v_{i,N-2} は長さ N-1 の 01 からなる文字列であり、j 文字目 v_{i,j} はマス (i, j) とマス (i, j+1) の間に壁がある（1）かない（0）かを表す。
h_{i,0} \cdots h_{i,N-1} は長さ N の 01 からなる文字列であり、j 文字目 h_{i,j} はマス (i, j) とマス (i+1, j) の間に壁がある（1）かない（0）かを表す。
全てのマスは互いに到達可能であることが保証されている。
(x_k, y_k) は k 番目の目的地の座標を表し、0\leq x_k,y_k\leq N-1 を満たす。すべての目的地は相異なる。

出力

以下の形式で標準出力に出力せよ。

C Q M
s_{0,0} \cdots s_{0,N-1}
\vdots
s_{N-1,0} \cdots s_{N-1,N-1}
c_0 q_0 A(c_0,q_0) S(c_0,q_0) D(c_0,q_0)
\vdots
c_{M-1} q_{M-1} A(c_{M-1},q_{M-1}) S(c_{M-1},q_{M-1}) D(c_{M-1},q_{M-1})

C は使用する色数であり、1 \le C \le N^4 を満たす必要がある。
Q は使用する内部状態数であり、1 \le Q \le N^4 を満たす必要がある。
M は出力する遷移規則の行数であり、0 \le M \le T を満たす必要がある。
s_{i,j} は初期状態におけるマス (i,j) の色であり、0 \le s_{i,j} \le C-1 を満たす必要がある。
各行 c_i q_i A(c_i,q_i) S(c_i,q_i) D(c_i,q_i) は、現在位置の色が c_i、内部状態が q_i のときに適用する遷移規則を表す。
- 0\leq c_i\leq C-1、0\leq q_i\leq Q-1 を満たす必要があり、同じ (c_i,q_i) の組は高々一度しか出現してはならない。
- 塗り替える色 A(c_i,q_i) は 0 \le A(c_i,q_i) \le C-1 を満たす必要がある。
- 新しい内部状態 S(c_i,q_i) は 0 \le S(c_i,q_i) \le Q-1 を満たす必要がある。
- 移動方向 D(c_i,q_i) は以下の5文字のいずれかで表す。
  - 上：U
  - 下：D
  - 左：L
  - 右：R
  - 移動しない：S

C\times Q は非常に大きくなり得るため、すべての組 (c,q) に対する遷移規則を出力する必要はない。シミュレーション中に実際に遭遇する可能性のある組に対する遷移規則のみを出力すればよい。最大で T ステップであるため、高々 T 行の遷移規則を出力すれば十分である。ただし、実行中に遭遇した (c,q) に対する遷移規則が出力中に存在しない場合、その時点でロボットの行動は打ち切られる。

例を見る

入力生成方法

L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L, U) とする。

盤面の生成

マスの角にあたる点を「頂点」と呼ぶことにする。

N=\mathrm{rand}(10,20) により盤面サイズを決定する。壁の面数を W=\mathrm{rand}(0,N-1) により決定し、マス間に壁がない状態から開始して、以下を W 回繰り返す。

頂点のうち、既存の壁に接していないものから一様ランダムに1つを選び、その頂点から上下左右のいずれかの方向を選んで、他の壁に接するまで壁を伸ばす。

目的地の生成

K=\mathrm{rand}(N,N^2) により目的地の個数を決定する。 N^2 個のマスを一様ランダムな順に並び替え、その最初の K 個を目的地の列として選択する。

`T` の生成

すべての目的地を順に訪れる最小移動回数 X を計算し、T=\mathrm{rand}(X,2X) によりステップ数の上限 T を決定する。

サンプルプログラム(Python)

# 入力
N, K, T = map(int, input().split())
v = [input().strip() for _ in range(N)]
h = [input().strip() for _ in range(N - 1)]
targets = [tuple(map(int, input().split())) for _ in range(K)]

# 移動可能か判定する関数
DIJ = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
def can_move(i, j, d):
    if d == 'U':
        if i == 0: return False
        return h[i - 1][j] == '0'
    elif d == 'D':
        if i == N - 1: return False
        return h[i][j] == '0'
    elif d == 'L':
        if j == 0: return False
        return v[i][j - 1] == '0'
    elif d == 'R':
        if j == N - 1: return False
        return v[i][j] == '0'
    return False

# --- 戦略 ---
# 内部状態は常に0とする。
# 各マスに異なる初期色を塗り、色の塗り替えは行わず、色で現在位置を表現する。
# 目的地1までのマンハッタン距離が短くなる方向に動し、そのような方向が無いなら停止。
C = N * N
Q = 1
s = [[0] * N for _ in range(N)]
for i in range(N):
     for j in range(N):
          s[i][j] = i * N + j
rules = []
i, j = targets[0] # 現在位置
gi, gj = targets[1] # 最初の目的地
for t in range(T):
    d = 'S'
    if i > gi and can_move(i, j, 'U'):
        d = 'U'
    elif i < gi and can_move(i, j, 'D'):
        d = 'D'
    elif j > gj and can_move(i, j, 'L'):
        d = 'L'
    elif j < gj and can_move(i, j, 'R'):
        d = 'R'
    if d == 'S':
        break
    rules.append((s[i][j], 0, s[i][j], 0, d))
    di, dj = DIJ[d]
    i, j = i + di, j + dj

# 出力
print(C, Q, len(rules))
for r in range(N):
    print(' '.join(map(str, s[r])))
for c, q, A, S, D in rules:
    print(c, q, A, S, D)

ツール(入力ジェネレータ・ビジュアライザ)

Web版: ローカル版より高性能でアニメーション表示が可能です。
ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

入力例 1

出力例 1

これは、問題文中のロボットの動作例に対応する入出力である。説明用のものであり、入力の制約は満たしていない。

Story

A Turing machine is a theoretical computing machine used in computational theory. It performs computations by following transition rules, changing its internal state (the value stored in the machine's memory) and the symbol at the head position on a one-dimensional tape, while moving the head left or right.

F Corporation is developing a robot modeled after this mechanism. This robot operates on a two-dimensional grid board and can move up, down, left, or right while following transition rules to update its internal state and the color at its current position.

Your task is to design the robot’s transition rules so that it visits a given sequence of destinations in order. Since the development cost is proportional to the sum of the number of colors and states used, it is desirable to minimize this sum as much as possible.

Problem Statement

There is a board consisting of N \times N cells. The top-left cell has coordinates (0, 0), and a cell i rows down and j columns to the right has coordinates (i, j). The outer edge of the N \times N grid is surrounded by walls, and there may also be walls between adjacent cells.

Each cell can be painted with a color. Let C be the total number of colors used, where each color is represented by an integer 0, 1, \ldots, C-1. You may freely set the initial colors of the board.

The robot has one variable representing its internal state. This internal state can take any value from 0 to Q-1, where Q is the total number of possible states, which you may choose freely. The initial internal state is 0.

Based on the current color c of the cell and the internal state q, the robot determines its next action and simultaneously performs the following three operations:

Repaints the current cell with color A(c, q) (it may repaint with the same color).
Updates its internal state to S(c, q) (it may update to the same state).
Moves in the direction D(c, q) (up, down, left, right, or stays in place). If there is a wall between the current cell and the destination, the robot cannot move and stays in place.

Here, A, S, and D are functions that define the transition rules. These transition rules must be designed before the robot starts operating and cannot be changed during operation. Also, the robot's actions do not depend on its current position, only on the current cell's color and the internal state.

Example of Robot Operation

In the example above, the robot starts on a 3 \times 3 board initially painted blue, at position (0, 0), and operates according to the following three transition rules:

A(\text{blue}, 0) = \text{green}, S(\text{blue}, 0) = 0, D(\text{blue}, 0) = \text{right}

A(\text{green}, 0) = \text{blue}, S(\text{green}, 0) = 1, D(\text{green}, 0) = \text{left}

A(\text{green}, 1) = \text{green}, S(\text{green}, 1) = 1, D(\text{green}, 1) = \text{down}

In the first three steps, transition rule 1 is repeatedly applied, repainting the cell green and moving right. At the third step, the robot hits a wall and cannot move, so it stays in place. In the fourth step, since the current cell is green, transition rule 2 is applied, repainting it blue, moving left, and changing the internal state to 1. Finally, in the fifth step, since the current cell is green and the internal state is 1, transition rule 3 is applied, and the robot moves down.

A sequence of K destination cells (x_0, y_0), (x_1, y_1), \ldots, (x_{K-1}, y_{K-1}) and an upper limit T on the number of steps are given. The robot starts from the cell (x_0, y_0) and aims to visit all destinations in the specified order within T steps.

If the robot visits a destination (x_j, y_j) before it is its turn (i.e., before reaching all prior destinations (x_i, y_i) for i < j), that visit does not count. The robot must reach (x_j, y_j) again once it becomes the current destination.

Design the initial color configuration of the board and the robot’s transition rules so that all destinations are visited in order.

Scoring

Let C be the number of colors used, Q be the number of states used, and V be the number of destinations successfully visited in order within the step limit T. Then, the absolute score is calculated as follows:

If V = K: C + Q
If V < K: 2N^4 + (K - V) \times N^2

The lower the absolute score, the better.

For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.

The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases.

The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.

Number of test cases

Provisional test: 50
System test: 2000. We will publish seeds.txt (sha256=c7a6f9526da67d83d1f8fed006e1b8f5edc8e4134444cf954e400a4dcd8bd130) after the contest is over.

About relative evaluation system

In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.

The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

Input

Input is given from Standard Input in the following format.

N K T
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
x_0 y_0
\vdots
x_{K-1} y_{K-1}

N is the size of the board and satisfies 10 \leq N \leq 20.
K is the number of destinations and satisfies N \leq K \leq N^2.
Let X be the minimum number of moves needed to visit all destinations in order. The step limit T satisfies X \leq T \leq 2X.
Each v_{i,0} \cdots v_{i,N-2} is a binary string of length N-1. The j-th character v_{i,j} indicates whether there is a wall (1) or not (0) between cell (i, j) and cell (i, j+1).
Each h_{i,0} \cdots h_{i,N-1} is a binary string of length N. The j-th character h_{i,j} indicates whether there is a wall (1) or not (0) between cell (i, j) and cell (i+1, j).
It is guaranteed that all cells are mutually reachable.
(x_k, y_k) represents the coordinates of the k-th destination and satisfies 0 \leq x_k, y_k \leq N-1. All destinations are distinct.

Output

Output to Standard Output in the following format.

C Q M
s_{0,0} \cdots s_{0,N-1}
\vdots
s_{N-1,0} \cdots s_{N-1,N-1}
c_0 q_0 A(c_0,q_0) S(c_0,q_0) D(c_0,q_0)
\vdots
c_{M-1} q_{M-1} A(c_{M-1},q_{M-1}) S(c_{M-1},q_{M-1}) D(c_{M-1},q_{M-1})

C is the number of colors used, and must satisfy 1 \le C \le N^4.
Q is the number of internal states used, and must satisfy 1 \le Q \le N^4.
M is the number of transition rules output, and must satisfy 0 \le M \le T.
s_{i,j} is the initial color of cell (i, j), and must satisfy 0 \le s_{i,j} \le C - 1.
Each line c_i q_i A(c_i,q_i) S(c_i,q_i) D(c_i,q_i) represents a transition rule applied when the current color is c_i and internal state is q_i:
- 0 \le c_i \le C - 1, 0 \le q_i \le Q - 1
- The same pair (c_i, q_i) must not appear more than once.
- Repaint color A(c_i,q_i) must satisfy 0 \le A(c_i,q_i) \le C - 1
- New internal state S(c_i,q_i) must satisfy 0 \le S(c_i,q_i) \le Q - 1
- Movement direction D(c_i,q_i) must be one of the following five characters:
  - Up: U
  - Down: D
  - Left: L
  - Right: R
  - Stay in place: S

Since C \times Q can be very large, it is not necessary to output transition rules for all (c, q) pairs. It is sufficient to output rules only for pairs that may actually occur during the simulation. As there are at most T steps, at most T transition rules are sufficient.

However, if the robot encounters a (c, q) pair during execution for which no transition rule has been output, its operation is terminated at that point.

Show example

Input Generation

Let \mathrm{rand}(L, U) be a function that generates a uniformly random integer between L and U, inclusive.

Board Generation

We refer to the corner points of the cells as "vertices."

First, determine the board size with N = \mathrm{rand}(10, 20). Then determine the number of wall segments W = \mathrm{rand}(0, N - 1). Start with a board where no internal walls exist between adjacent cells, and repeat the following process W times:

Randomly choose one vertex that is not adjacent to any existing wall. Then choose one of the four directions (up, down, left, right) and extend a wall from that vertex in the chosen direction until it touches another wall.

Destination Generation

Determine the number of destinations with K = \mathrm{rand}(N, N^2). Shuffle the N^2 cells uniformly at random, and select the first K cells from this shuffled list as the destination sequence.

Generating `T`

Calculate the minimum number of moves X required to visit all destinations in order. Then determine the step limit with T = \mathrm{rand}(X, 2X).

Sample Solution (Python)

# Input
N, K, T = map(int, input().split())
v = [input().strip() for _ in range(N)]
h = [input().strip() for _ in range(N - 1)]
targets = [tuple(map(int, input().split())) for _ in range(K)]

# Function to check if movement is possible
DIJ = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
def can_move(i, j, d):
    if d == 'U':
        if i == 0: return False
        return h[i - 1][j] == '0'
    elif d == 'D':
        if i == N - 1: return False
        return h[i][j] == '0'
    elif d == 'L':
        if j == 0: return False
        return v[i][j - 1] == '0'
    elif d == 'R':
        if j == N - 1: return False
        return v[i][j] == '0'
    return False

# --- Strategy ---
# The internal state is always fixed to 0.
# Each cell is assigned a unique initial color; the color is never changed.
# The color thus represents the robot’s current position.
# The robot moves in a direction that decreases the Manhattan distance to target[1].
# If no such direction exists, it stops.
C = N * N
Q = 1
s = [[0] * N for _ in range(N)]
for i in range(N):
     for j in range(N):
          s[i][j] = i * N + j
rules = []
i, j = targets[0] # current position
gi, gj = targets[1] # first destination
for t in range(T):
    d = 'S'
    if i > gi and can_move(i, j, 'U'):
        d = 'U'
    elif i < gi and can_move(i, j, 'D'):
        d = 'D'
    elif j > gj and can_move(i, j, 'L'):
        d = 'L'
    elif j < gj and can_move(i, j, 'R'):
        d = 'R'
    if d == 'S':
        break
    rules.append((s[i][j], 0, s[i][j], 0, d))
    di, dj = DIJ[d]
    i, j = i + di, j + dj

# Output
print(C, Q, len(rules))
for r in range(N):
    print(' '.join(map(str, s[r])))
for c, q, A, S, D in rules:
    print(c, q, A, S, D)

Tools (Input generator and visualizer)

Web version: This is more powerful than the local version providing animations.
Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.

Sample Input 1

Sample Output 1

This input and output correspond to the example of robot operation given in the problem statement.
They are for illustrative purposes and do not satisfy the input constraints.

A-Final - Grid Turing Robot (System Test)

Time Limit: 0 msec / Memory Limit: 1024 MiB