题解 · 743

题解

주어진 $E_i$ 를 각각 처리할 필요는 없다. 하나의 배치에서 $1$ 부터 $N^2$ 까지의 모든 정수를 에너지로 만들면 모든 입력을 해결할 수 있다. 실제로 $N \ge 5$ 이면 이러한 배치가 항상 존재하므로 답은 항상 YES이다.

노선은 오른쪽으로 $N-1$ 번, 아래쪽으로 $N-1$ 번 이동한다. 각 행에서 오른쪽으로 이동한 횟수를 $x_i$ 라고 하면

x_i \ge 0, \qquad \sum_{i=1}^{N} x_i=N-1

이다. 반대로 이 조건을 만족하는 모든 정수열 $(x_1,\cdots,x_N)$ 은 하나의 노선을 나타낸다. 첫째 행에서 오른쪽으로 $x_1$ 번 이동하고, 아래로 한 번 이동한 다음 둘째 행에서 오른쪽으로 번 이동하는 식이다.

따라서 같은 행의 수와 가로 선로의 부호를 통일하면, 노선의 에너지를 각 행에서 선택한 가로 이동 횟수의 합으로 표현할 수 있다.

1. 역의 수와 가로 선로 배치

다음과 같이 정수를 배치한다. 출발역에 적을 수 $c$ 는 나중에 정한다.

첫째 행과 둘째 행의 가로 선로는 모두 -, 나머지 행의 가로 선로는 모두 +로 정한다.

오른쪽으로 한 번 이동할 때 에너지에 더해지는 값은 행에 따라

-1,-2,2,3,\cdots,N-1

중 하나가 된다. 이 값들의 집합을

W=\{-2,-1,2,3,\cdots,N-1\}

이라고 하자.

각 행에서 다음 행으로 내려가는 세로 선로는 열과 무관하게 같은 부호를 사용한다. 모든 노선은 각 행 경계를 정확히 한 번 지나므로, 출발역과 모든 세로 이동이 만드는 에너지의 합 $B$ 는 노선과 무관하다. 이를 $B=2N-1$ 로 만들 것이다.

그러면 노선의 에너지는 $2N-1$ 에 $W$ 의 원소 $N-1$ 개를 더한 값이 된다. 같은 원소를 여러 번 선택해도 된다. 선택한 원소들의 순서를 해당 행의 순서로 정렬하면 실제 노선으로 만들 수 있으므로, 이동 순서에 따른 추가 제약은 없다.

2. 모든 에너지를 만들 수 있다는 증명

$kW$ 를 $W$ 의 원소 $k$ 개를 중복을 허용하여 더해서 만들 수 있는 정수의 집합이라고 하자. 다음을 보이면 충분하다.

kW=[-2k,(N-1)k] \qquad (k \ge 3).

여기서 구간은 양 끝점을 포함한 모든 정수를 뜻한다.

먼저 $k=3$ 을 생각하자. 세 원소 중 양수의 개수에 따라 만들 수 있는 합은 다음과 같다.

음수는 연속된 두 정수 $-2,-1$ 이고, 양수도 $2$ 부터 $N-1$ 까지 연속되어 있으므로 각 구간 안의 모든 정수를 만들 수 있다. $N \ge 5$ 이면 위 구간들이 빈틈없이 이어져

3W=[-6,3N-3]

을 얻는다.

이제 $kW=[-2k,(N-1)k]$ 라고 가정하자. 여기에 $-2$ 또는 $N-1$ 을 하나 더하면 각각

[-2k-2,(N-1)k-2],

[-2k+N-1,(N-1)(k+1)]

의 모든 정수를 만들 수 있다. 두 구간 사이에는 빈틈이 없다. 실제로 둘째 구간의 시작점에서 첫째 구간의 끝점을 뺀 값은

N+1-k(N+1)=(1-k)(N+1) \le 0

이다. 따라서 $(k+1)W=[-2(k+1),(N-1)(k+1)]$ 이다.

$N \ge 5$ 이므로 $N-1 \ge 3$ 이다. 따라서 전체 노선의 에너지는 다음 구간의 모든 정수를 포함한다.

[2N-1-2(N-1),\;2N-1+(N-1)^2]=[1,N^2].

즉, 모든 $E_i$ 를 동시에 만족한다.

3. 세로 이동의 합을 맞추기

남은 것은 세로 선로의 부호와 출발역의 수 $c$ 를 정하여 $B=2N-1$ 로 만드는 것이다.

아래쪽으로 이동할 때 도착하는 행의 수는 순서대로

2,2,3,4,\cdots,N-1

이다. 이 수들에 부호를 붙인 합을 $S$ 라고 하면 $B=c+S$ 이다.

$G=2N-3$ 으로 놓고 $S=0$ 에서 시작한다. 위 수들을 역순인

N-1,N-2,\cdots,2,2

로 처리한다. 현재 수를 $w$ 라고 할 때 다음과 같이 정한다.

마지막으로

c=2N-1-S

로 정하면 $B=2N-1$ 이 된다.

이제 $c$ 가 허용 범위 안에 있음을 보이자. $d=G-S$ 라고 하면 위 과정은

d \leftarrow \begin{cases}d-w & d>0,\\ d+w & d \le 0\end{cases}

이다. 처음에는 $d=2N-3$ 이고, $N-1$ 과 $N-2$ 를 처리하면 차례로 $d=N-2$ , 이 된다.

이후 $w=N-3,N-4,\cdots,2$ 를 처리한다. 처리 직전에 $|d| \le w+1$ 이면 처리 직후에는 이다. 따라서 이 과정을 마치면 이다.

마지막으로 남은 $2$ 를 처리하면 $d$ 는 $-1,0,1,2$ 중 하나가 된다. 따라서

c=2N-1-S=d+2 \in \{1,2,3,4\}.

$N \ge 5$ 이므로 출발역의 수도 항상 $1$ 이상 $N$ 이하이다. 나머지 역의 수 역시 모두 허용 범위를 만족한다.

Solution Written by GPT6