コンテンツにスキップ

DOJ Beginner Contest 6 E - Building a Binary Grid

サイト
DOJ
コンテスト
DOJ Beginner Contest 6
問題
E - Building a Binary Grid

長さ NN の 01 文字列が QQ 個与えられます。N×NN \times N の 01 のグリッドを 1 つ作り、どの文字列も、グリッド上の長さ NN の経路(上下左右に隣り合う相異なるマスの列)に沿って読めるようにする問題です。グリッドと、各文字列に対応する経路を 1 つずつ出力します。

2≤N≤1002 \le N \le 100 で、NQNQ の総和は 10610^6 以下です。

ii 行目(0-indexed)をすべて i mod 2i \bmod 2 にします。つまり、00 だけの行と 11 だけの行が交互に並びます。さらに、右下の角だけを 11 にします。

0000
1111
0000
1111

(N=4N = 4 の例。NN が偶数なら最下行はもともと 11 です。)

このグリッドでは、角以外のマスについて次のことがいえます。

  • 右か左に動くと、同じ行なので値は変わりません。
  • 上か下に動くと、行が変わるので値が反転します。

左上 (0,0)(0, 0) から始めます。ここは 00 です。次の文字が今のマスと同じ値なら右に、違う値なら下に動きます。

右か下にしか動かないので、同じマスを 2 回通ることはありません。N−1N - 1 回動いたあとも、行と列の番号の和は N−1N - 1 なので、グリッドからはみ出しません。また、右下の角(番号の和が 2N−2>N−12N - 2 > N - 1)には届かないので、角だけ値を変えたことの影響も受けません。

右下の角 (N−1,N−1)(N - 1, N - 1) から始めます。ここは 11 です。次の文字に合わせて、左か上に動きます。

角から左のマスと上のマスは、行が違うので値が異なり、どちらかは次の文字と一致します。そこから先は、0 で始まる場合と同じように「同じ値なら左、違う値なら上」と動けば、どの文字列も読めます。左か上にしか動かないので、角に戻ることもありません。

1 つの文字列の経路は O(N)O(N) で求まるので、全体で O(NQ)O(NQ) です。

Python
for _ in range(int(input())):
N, Q = map(int, input().split())
grid = []
for i in range(N):
grid.append([i % 2] * N)
grid[-1][-1] = 1
for i in range(N):
print(*grid[i], sep="")
for _ in range(Q):
S = input()
if S[0] == "0":
i, j = 0, 0
ans = [i + 1, j + 1]
for k in range(1, N):
if grid[i][j + 1] == int(S[k]):
j += 1
ans.append(i + 1)
ans.append(j + 1)
else:
i += 1
ans.append(i + 1)
ans.append(j + 1)
else:
i, j = N - 1, N - 1
ans = [i + 1, j + 1]
for k in range(1, N):
if grid[i][j - 1] == int(S[k]):
j -= 1
ans.append(i + 1)
ans.append(j + 1)
else:
i -= 1
ans.append(i + 1)
ans.append(j + 1)
print(*ans)

隣のマス(右または左)の値が次の文字と一致すれば横に、一致しなければ縦に動いています。縦に動いた先は、横のマスと値が逆なので、必ず次の文字と一致します。