問題一覧 > 通常問題

No.3337 Divide and Conquer

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 6
作問者 : 👑 kencho / テスター : cn_449 👑 みうね
お気に入りにしたユーザー ProblemId : 12740 / 自分の提出
問題文最終更新日: 2025-11-08 01:59:36
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
yukicoder contest 487 (順位表) の他の問題:

Problem Statement

You are a minister of a certain kingdom. The kingdom has the shape of an $N \times N$ ($N$ is a multiple of $3$) square grid graph, where each of the $N^2$ vertices corresponds to $1$ city and each of the $2N(N-1)$ edges corresponds to $1$ road.
More precisely, each city is represented by a pair of integers $(i,\ j)$ ($i,\ j$ are integers between $1$ and $N$, inclusive), and the cities directly connected by a road to $(i,\ j)$ are the at most $4$ cities $(i - 1,\ j), (i + 1,\ j), (i,\ j - 1), (i,\ j + 1)$.
There is no way to travel between cities other than using these roads.

One day, the king ordered you to devise a policy to improve public order in the country. This kingdom is inhabited by $3$ races, humans, elves, and dwarves, and conflicts between the races never ceased.
You consider an arrangement of cities that allows $1$ race to unite to be a risk, so you decided to limit the inhabitants of each of the $N^2$ cities to $1$ race, and then to make the number of cities reachable without passing through cities inhabited by other races as small as possible.
Also, to prepare for emergencies, you decided to ensure that whenever any $2$ races cooperate, they do not need to pass through cities inhabited by the remaining $1$ race.

Now, let $M_{min}$ be the minimum integer $M$ for which there exists an assignment of races to cities satisfying all of the following conditions. Find one example of such an assignment under $M = M_{min}$.

  • The number of cities assigned to each race is the same.
  • From any city $c$, the number of cities that can be reached by passing only through cities assigned the same race as the one assigned to $c$ is at most $M$, including $c$ itself.
  • Let $a, b$ be any $2$ cities. If the race $x$ assigned to $a$ and the race $y$ assigned to $b$ are different, it is possible to travel from $a$ to $b$ by passing only through cities assigned $x$ or $y$.
Note that, under the constraints of this problem, it can be shown that an assignment satisfying the conditions always exists for sufficiently large $M$.

Constraints

  • All inputs are integers.
  • $3 \leq N \leq 2025$
  • $N$ is a multiple of $3$.

Input

The input is given from standard input in the following format.

$N$

Output

Output the answer in the following format.

$S_1$
$S_2$
$\vdots$
$S_N$

$S_i$ is a string of length $N$, and the $j$-th character of $S_i$ must be H if the race assigned to city $(i,\ j)$ is human, E if it is elf, and D if it is dwarf.

Print a newline at the end.

Sample

Sample 1
Input
3
Output
HED
HDD
EEH

The figure below shows the assignment corresponding to the sample output. Blue vertices represent cities assigned to humans, red vertices represent cities assigned to elves, and green vertices represent cities assigned to dwarves.
This assignment satisfies the conditions of the problem when $M=3$, and no assignment satisfying the conditions of the problem exists when $M \leq 2$, so this is a correct answer.

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