J - Grid Construction 解説
by 
noya2
To state the conclusion first, the necessary and sufficient condition for \((H, W)\) to be constructible is as follows:
\[ (H, W) = (2,2), (3,3), (5,5), (6n+9, 6m+9), (6n+11, 6m+11)\ (n, m=0,1,\dots) \]
Let us first confirm that construction is possible for these \((H, W)\).
For \((2,2), (3,3), (5,5)\), construction can be achieved as follows.
<^
v>
<<^
v.^
v>>
<<<<^
v.v.^
v>.<^
v.^.^
v>>>>
Moreover, by filling the outer 3 cells as follows, the problem is reduced to a smaller grid with \(H, W\) decreased by 6.
^>>>>>>>>>>>>>>>>
^.v.v.v.v.v.v.v.v
^>.^.^.^.^.^.^.<v
^.< >.v
^>. .<v
^.< >.v
^>. .<v
^.< >.v
^>.v.v.v.v.v.v.<v
^.^.^.^.^.^.^.^.v
<<<<<<<<<<<<<<<<v
This reduces the remaining cases to those where \((H, W) = (9, 6m+9), (11, 6m+11)\ (m=0,1,\dots)\). For example, it suffices to construct a repeating unit of length \(6\). One solution for \((H, W) = (9, 39), (11, 41)\) can be constructed as follows.
^>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
^.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v
^>.<v>.^.<v>.^.<v>.^.<v>.^.<v>.^.<v>.<v
^.^.v.<<^.v.<<^.v.<<^.v.<<^.v.<<^.v.^.v
^>>>.<v.^>.<v.^>.<v.^>.<v.^>.<v.^>.<<<v
^.v.^.v>>.^.v>>.^.v>>.^.v>>.^.v>>.^.v.v
^>.<^>.v.<^>.v.<^>.v.<^>.v.<^>.v.<^>.<v
^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.v
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<v
^>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
^.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v
^>.^.<v>.^.<v>.^.<v>.^.<v>.^.<v>.^.^.^.<v
^.<^>.v.<^>.v.<^>.v.<^>.v.<^>.v.<^>>>>>.v
^>.^.<v>.^.<v>.^.<v>.^.<v>.^.<v>.^.v.v.<v
^.<^>.v.<^>.v.<^>.v.<^>.v.<^>.v.<^>.<v>.v
^>.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.v.<v
^.<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<v>.v
^>.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.<v
^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.v
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<v
By constructing the endpoints appropriately and placing repeating units in between, we can obtain a solution.
Finally, we show that construction is impossible for \((H, W)\) values other than these.
Proof
Without loss of generality, assume \(H \le W\).
Clearly, \(H = 1\) cannot be constructed. Now let \(H \ge 2\).
First, let’s consider drawing the outer part of the grid. In other words, we consider drawing all segments represented by \((0, y) - (0, y+1), (H, y) - (H, y+1), (x, 0) - (x+1, 0), (x, W) - (x+1, W)\ (x=0,1,\dots H-1, y=0,1,\dots ,W-1)\). Essentially, there is only one way to arrange the segments, aside from rotation. By considering methods to simultaneously draw corner segments \((0, 0) - (0, 1), (0, 0) - (1, 0)\), we can see that the arrangement of the outer “U”-shaped configurations is uniquely determined.
This proves all cases for \(H=2\). The aforementioned method is effective when \(W=2\), and in this case, all segments can be drawn. On the other hand, if \(W \ge 3\), the process will result in overlapping segments, making it invalid.
For \(H \ge 3\), the method is effective. Furthermore, in the case \(H=W=3\), all segments can be drawn. However, in the case \(H=3, W \ge 4\), there are segments represented by \((1, y) - (2, y)\ (y=2, 3, \dots , W-2)\) that remain uncovered, and all of these segments are aligned in the same direction, making construction impossible.
Now assume \(H \ge 4\). Suppose we draw the outer part of the grid. Next, we consider drawing the inner part, represented by segments \((1, y) - (2, y), (H-2, y) - (H-1, y), (x, 1) - (x, 2), (x, W-2) - (x, W-1)\ (y=2, 3, \dots , W-2)\). There is only one way to do this. By considering methods to draw corner segments such as \((1, 2) - (2, 2), (2, 1) - (2, 2)\), we can see that the arrangement of the inner “U”-shapes is also uniquely determined. However, this method is only valid when both \(H\) and \(W\) are odd; otherwise, overlapping segments will occur.
This shows that \(H=4\) is impossible. As for \(H=5\), only \(W=5\) is possible; otherwise, as in the case \(H=3, W \ge 4\), segments aligned in the same direction will remain, making construction impossible.
Finally, by observing the number of segments needed to construct the grid, we find it to be \(H(W+1) + (H+1)W = 2HW + H + W\). Since this must be a multiple of 3, the only possible values for \((H \bmod 3, W \bmod 3)\) are \((0, 0)\) and \((2, 2)\).
To summarize our observations, the only possibilities for \((H \bmod 6, W \bmod 6)\) are \((3, 3)\) and \((5, 5)\). This exhausts all cases.
投稿日時:
最終更新: