K - 5D Polyomino
問題文
いくつかの $K$ 次元単位超立方体を $(K-1)$ 次元の面でつなげてできる、連結な図形の形をしたパズルのピースのことを $K$ 次元ポリオミノ と呼びます。
各辺が $2$ マスの $K$ 次元のグリッドと、$3$ 個の $K$ 次元ポリオミノがあります。グリッドは $K$ 次元空間内の領域 $[0,2]^K$ を $2^K$ 個のマスに分割したものです。座標 $(x_1, x_2, \ldots, x_K)$ ($x_l \in \lbrace 1, 2 \rbrace$) のマスは、領域 $[x_1 - 1, x_1] \times [x_2 - 1, x_2] \times \cdots \times [x_K - 1, x_K]$ を占めます。2 つのマスが $(K-1)$ 次元の面で接するのは、座標がちょうど 1 成分だけ異なるときです。
$i$ 番目の $K$ 次元ポリオミノは $N_i$ 個のマスからなり、何も置かれていないグリッドに置いたときに座標 $(x_{i,j,1}, x_{i,j,2}, \ldots, x_{i,j,K})$ ($1 \leq j \leq N_i$) のマスを占めます。
あなたは次の条件を全て満たすように、$3$ 個の $K$ 次元ポリオミノ全てをグリッドに敷き詰めることにしました。
- グリッドの全てのマスは $K$ 次元ポリオミノで覆われている。
- $K$ 次元ポリオミノ同士がマスを共有するように置くことはできない。
- $K$ 次元ポリオミノの回転は自由に行うことができるが、平行移動したり裏返したりすることはできない。
ここで回転とは、次の条件をすべて満たす $K \times K$ 行列 $Q$ を用いて $f(p) = O + Q(p - O)$ と表される変換 $f$ のことです。ただし、$O = (1, 1, \ldots, 1)$ はグリッドの中心にある点です。
- $Q$ のすべての要素は $-1$, $0$, $1$ のいずれかである。
- $Q$ のどの行にもどの列にも、$0$ でない要素がちょうど $1$ つずつある。
- $Q$ の行列式は $1$ である。
$f$ は $K$ 次元空間内の点に対する変換です。座標 $(x_1, x_2, \ldots, x_K)$ のマスは、その中心 $(x_1 - \frac{1}{2}, x_2 - \frac{1}{2}, \ldots, x_K - \frac{1}{2})$ を $f$ で移した点を中心とするマスに移ります。回転は $K$ 次元ポリオミノごとに独立に選べます。
条件を満たすようにグリッドに $K$ 次元ポリオミノを敷き詰めることは可能ですか？
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- $1 \leq T \leq 5$
- $3 \leq K \leq 5$
- $N_i \geq 1$
- $N_1 + N_2 + N_3 = 2^K$
- $x_{i,j,l} \in \lbrace 1, 2 \rbrace$
- 各 $i$ について、$(x_{i,j,1}, \ldots, x_{i,j,K})$ ($1 \leq j \leq N_i$) は相異なる
- 与えられる $K$ 次元ポリオミノは連結である。つまり、$K$ 次元ポリオミノを構成するマス同士は、$(K-1)$ 次元の面で接するマスのみを辿って互いに行き来できる
- 入力は全て整数
部分点
- $K = 3$ を満たすデータセットに正解した場合は $50$ 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case} _ 1$
$\mathrm{case} _ 2$
$\vdots$
$\mathrm{case} _ T$
各テストケースは以下の形式で与えられる。
$K$
$N_1$
$x_{1,1,1}$ $x_{1,1,2}$ $\ldots$ $x_{1,1,K}$
$\vdots$
$x_{1,N_1,1}$ $x_{1,N_1,2}$ $\ldots$ $x_{1,N_1,K}$
$N_2$
$x_{2,1,1}$ $x_{2,1,2}$ $\ldots$ $x_{2,1,K}$
$\vdots$
$x_{2,N_2,1}$ $x_{2,N_2,2}$ $\ldots$ $x_{2,N_2,K}$
$N_3$
$x_{3,1,1}$ $x_{3,1,2}$ $\ldots$ $x_{3,1,K}$
$\vdots$
$x_{3,N_3,1}$ $x_{3,N_3,2}$ $\ldots$ $x_{3,N_3,K}$
出力
$T$ 行出力せよ。$t$ 行目には、$t$ 番目のテストケースで条件を満たすように $K$ 次元ポリオミノを敷き詰められる場合は Yes を、そうでない場合は No を出力せよ。
2
3
4
1 1 1
1 2 1
2 1 1
2 2 1
2
1 1 2
2 1 2
2
1 1 1
1 2 1
3
2
1 1 1
2 1 1
2
1 1 1
2 1 1
4
1 1 1
1 1 2
1 2 1
2 1 1
Yes
No
1 つ目のテストケースでは、1 つ目と 2 つ目の $3$ 次元ポリオミノをそのまま置き、3 つ目の $3$ 次元ポリオミノを回転させて座標 $(1, 2, 2), (2, 2, 2)$ のマスを占めるように置くと、条件を満たすように敷き詰められます。
2 つ目のテストケースでは、3 つ目の $3$ 次元ポリオミノをどのように置いても、残りの $4$ マスは $1$ つのマスから $3$ 方向に $1$ マスずつ伸びた形になります。この形を $2$ マスからなる $3$ 次元ポリオミノ $2$ 個で覆うことはできないため、条件を満たすように敷き詰めることはできません。
$K = 3$ のとき、回転は立方体をその中心の周りで回す $24$ 通りの方法に対応します。
この入力例は部分点の制約を満たします。
1
4
7
1 1 1 1
1 1 1 2
1 2 1 1
1 2 1 2
2 1 2 1
2 2 1 1
2 2 2 1
5
1 1 2 1
1 1 2 2
1 2 2 1
1 2 2 2
2 1 2 2
4
1 1 1 1
1 1 1 2
1 2 1 2
1 2 2 2
No
1 つ目と 2 つ目の $4$ 次元ポリオミノをそのまま置くと、残りのマスは座標 $(2, 1, 1, 1), (2, 1, 1, 2), (2, 2, 1, 2), (2, 2, 2, 2)$ の $4$ マスです。3 つ目の $4$ 次元ポリオミノを裏返すことができれば、ちょうどこの $4$ マスに収まります。
しかし裏返すことはできず、回転だけではどのように置いても条件を満たすように敷き詰められないため、No を出力してください。
2
3
3
1 1 1
1 1 2
1 2 1
2
2 1 1
2 2 1
3
1 1 2
2 1 2
2 2 2
4
5
1 1 1 1
1 2 1 1
2 1 1 1
2 1 1 2
2 2 1 1
4
1 2 1 1
2 1 2 1
2 2 1 1
2 2 2 1
7
1 1 2 2
1 2 1 2
1 2 2 1
1 2 2 2
2 1 2 2
2 2 1 2
2 2 2 2
Yes
Yes
テストケースごとに $K$ が異なることがあります。