問題一覧 > 通常問題

No.3741 Used to be Polyominal Constructive

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 5
作問者 : 👑 kencho / テスター : uruzunyaa
お気に入りにしたユーザー ProblemId : 13820 / 自分の提出
問題文最終更新日: 2026-11-02 04:29:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
グリッド構築24題 (順位表) の他の問題:

Story

kencho came up with the following problem.

"You are given $3$ polyominoes, each fitting in an $N \times N$ grid. Output one way to translate each polyomino so that every $2$ of the polyominoes do not overlap and are adjacent by sharing an edge."



This problem looked interesting at first glance, but it turned out that speeding up a nearly brute-force solution with SIMD made it faster than the intended solution (if you have time, try to think of an $O(N^2 \log N)$ solution).

So kencho changed the format of the problem and decided to have you create a test case that defeats "incorrect solutions that randomly make polyominoes adjacent to each other and search for a consistent combination".

Incidentally, although the word polyominal has a few uses in papers and elsewhere, it is hardly ever used, and it seems that using polyomino as is to modify a noun is the common practice.

Problem Statement

Consider an $N \times N$ grid where each cell contains # or .. Regarding the cells of a grid $G$ that contain # as unit squares, we call the set of those squares the figure represented by $G$.

A figure is called a polyomino if it is non-empty and it is possible to move from any unit square to any other unit square by following unit squares that share an edge.

Find an integer $N$ and $3$ grids $(G_1, G_2, G_3)$ of size $N \times N$ satisfying all of the following conditions. Let $P_i$ be the figure represented by $G_i$.

  • $N$ is an integer between $1$ and $666$, inclusive.
  • For $i = 1, 2, 3$, $P_i$ is a polyomino.
  • The number of ways to make $P_1$ and $P_2$ adjacent by translation is at least $10^5$.
  • The number of ways to make $P_2$ and $P_3$ adjacent by translation is at least $10^5$.
  • The number of ways to make $P_3$ and $P_1$ adjacent by translation is at least $10^5$.
  • The number of ways to simultaneously make $P_1$ and $P_2$, $P_2$ and $P_3$, and $P_3$ and $P_1$ adjacent by translation is at least $1$ and at most $10$.
What the number of ways to make them adjacent means

In this problem, we consider translating polyominoes by integer vectors, without rotating or reflecting them.

Translation takes place on an infinitely extending square lattice, and the figure after translation does not need to fit within the original $N \times N$ grid.

Two polyominoes are said to be adjacent if both of the following conditions hold.

  • The unit squares of the 2 polyominoes do not overlap.
  • There exist a unit square of one polyomino and a unit square of the other polyomino that share an edge (merely sharing a vertex does not count as adjacent).

The number of ways to make $P_i$ and $P_j$ adjacent is the number of translation vectors such that, when the position of $P_i$ is fixed and $P_j$ is translated by an integer vector, the 2 polyominoes are adjacent. Even if they share multiple edges, the same translation vector counts as $1$ way.

The number of ways to simultaneously make $P_1$ and $P_2$, $P_2$ and $P_3$, and $P_3$ and $P_1$ adjacent is the number of ordered pairs $(v_2, v_3)$ such that, when the position of $P_1$ is fixed and $P_2, P_3$ are translated by integer vectors $v_2, v_3$ respectively, all 3 pairs are adjacent.

Therefore, an arrangement obtained merely by translating all the polyominoes by the same amount is not counted as a different way.

Input

This problem is output-only. No input is given.

Output

Output the integer $N$ and the grids $G_1, G_2, G_3$ in the following format.

$N$
$G_{1, 1, 1} G_{1, 1, 2} \ldots G_{1, 1, N}$
$G_{1, 2, 1} G_{1, 2, 2} \ldots G_{1, 2, N}$
$\vdots$
$G_{1, N, 1} G_{1, N, 2} \ldots G_{1, N, N}$
$G_{2, 1, 1} G_{2, 1, 2} \ldots G_{2, 1, N}$
$G_{2, 2, 1} G_{2, 2, 2} \ldots G_{2, 2, N}$
$\vdots$
$G_{2, N, 1} G_{2, N, 2} \ldots G_{2, N, N}$
$G_{3, 1, 1} G_{3, 1, 2} \ldots G_{3, 1, N}$
$G_{3, 2, 1} G_{3, 2, 2} \ldots G_{3, 2, N}$
$\vdots$
$G_{3, N, 1} G_{3, N, 2} \ldots G_{3, N, N}$

$G_{i,j,k}$ denotes the character written in the cell at the $j$-th row from the top and the $k$-th column from the left of grid $G_i$.

Print a newline at the end.

Visualizer

A web version of the visualizer for output results is available here.

During the contest, sharing visualization results and mentioning solutions or considerations are prohibited. Please be careful.

In principle, we do not accept questions about the specifications of the visualizer. Please use it only as an auxiliary tool.

Sample

Output
2
#.
##
.#
.#
##
##

Note that this sample output only illustrates the output format, and it will be judged as WA if submitted.

For $P_1, P_2, P_3$ represented by this output, the respective numbers of ways are as follows.

  • The number of ways to make $P_1$ and $P_2$ adjacent by translation is $9$.


  • The number of ways to make $P_2$ and $P_3$ adjacent by translation is $10$.


  • The number of ways to make $P_3$ and $P_1$ adjacent by translation is $11$.


  • The number of ways to simultaneously make $P_1$ and $P_2$, $P_2$ and $P_3$, and $P_3$ and $P_1$ adjacent by translation is $17$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。