DOJ Beginner Contest 6 E - Building a Binary Grid
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 6
- 問題
- E - Building a Binary Grid
長さ の 01 文字列が 個与えられます。 の 01 のグリッドを 1 つ作り、どの文字列も、グリッド上の長さ の経路(上下左右に隣り合う相異なるマスの列)に沿って読めるようにする問題です。グリッドと、各文字列に対応する経路を 1 つずつ出力します。
で、 の総和は 以下です。
グリッドの作り方
Section titled “グリッドの作り方”行目(0-indexed)をすべて にします。つまり、 だけの行と だけの行が交互に並びます。さらに、右下の角だけを にします。
0000111100001111( の例。 が偶数なら最下行はもともと です。)
このグリッドでは、角以外のマスについて次のことがいえます。
- 右か左に動くと、同じ行なので値は変わりません。
- 上か下に動くと、行が変わるので値が反転します。
0 で始まる文字列
Section titled “0 で始まる文字列”左上 から始めます。ここは です。次の文字が今のマスと同じ値なら右に、違う値なら下に動きます。
右か下にしか動かないので、同じマスを 2 回通ることはありません。 回動いたあとも、行と列の番号の和は なので、グリッドからはみ出しません。また、右下の角(番号の和が )には届かないので、角だけ値を変えたことの影響も受けません。
1 で始まる文字列
Section titled “1 で始まる文字列”右下の角 から始めます。ここは です。次の文字に合わせて、左か上に動きます。
角から左のマスと上のマスは、行が違うので値が異なり、どちらかは次の文字と一致します。そこから先は、0 で始まる場合と同じように「同じ値なら左、違う値なら上」と動けば、どの文字列も読めます。左か上にしか動かないので、角に戻ることもありません。
1 つの文字列の経路は で求まるので、全体で です。
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)隣のマス(右または左)の値が次の文字と一致すれば横に、一致しなければ縦に動いています。縦に動いた先は、横のマスと値が逆なので、必ず次の文字と一致します。