2024 가지컵

# 풀이
- 한 줄로 연속한 $10$개의 칸에서, 모든 서로 인접한 두 칸에 들어 있는 가지의 색상이 같으면 한 줄에 놓인 모든 가지의 색상이 같습니다.
- 가로와 세로 방향으로 각각 한 줄씩 루프를 돌면서 서로 인접한 두 칸의 가지 색상이 모두 같은 경우를 확인하면 됩니다.
- $10 \times 10$개의 각 칸마다 그 칸을 포함하는 가로줄 혹은 세로줄이 모두 같은 색상인지 확인해도 됩니다.

2024 가지컵 - A - Editorial

# 풀이
- 모든 행과 열의 번호는 $0$부터 시작합니다.

## 케이스 줄이기
- 가운데의 `/` 방향 대각선을 기준으로, 정가운데 대각선과 그 위아래 삼각형 세 부분으로 나눠서 생각합시다.
- 가운데 대각선에선 $n$이 홀수일 때 $\lfloor n/2 \rfloor$행 $\lfloor n/2 \rfloor$열의 칸이 조건에 맞는 유일한 칸이며, $n$이 짝수면 조건에 맞는 칸이 없습니다.
- 대각선 아래쪽 삼각형에서 조건을 만족하는 칸이 있다면, 그 칸을 중심점에 대해 점대칭시킨 대각선 위쪽 삼각형의 칸도 조건을 만족해야 합니다.
- 따라서 위쪽 삼각형만 고려하면 충분합니다.
- 위쪽 삼각형의 $r$행 $c$열에 적힌 값은, 첫 번째 표에선 $nr+c+1$이고 두 번째 표에선 다음과 같습니다.

$$
rc + \frac{1}{2}(c+1)(c+2) + \frac{1}{2}r(r+1)
$$

- 이 두 수가 같다고 하고 식을 정리한 뒤, $w = r+c$라고 정의하면 다음 식을 얻습니다.
$$ 2nr = w(w+1) $$
- 위 식을 만족하면서 $0 \le w \le n-2$이고 $0 \le r \le w$인 $r$, $c$를 모두 찾으면 위쪽 삼각형에서 조건에 맞는 모든 칸을 찾게 됩니다.
- $w=0$인 경우 $r=0$, $c=0$인데 이는 $n$의 값과 무관하게 항상 조건을 만족하므로, 앞으로 $w \ge 1$인 경우만 고려합니다.
- $r = w(w+1)/2n < w(w+1)/2w = (w+1)/2$이므로 $w$의 범위를 맞추면 $r$의 범위는 자동으로 맞습니다.

## 조건에 맞는 칸 찾기
- $2nr = w(w+1)$을 푸는 것은 $1 \times 2$, $2 \times 3$, ..., $(n-2)(n-1)$ 중 $2n$의 배수를 전부 찾아내는 것과 같습니다.
- 이를 활용해 답을 일일이 찾는 풀이는 시간 초과를 받습니다.
- $w$와 $w+1$이 서로소이기 때문에, $2n = ab$이면서 $a \mid w$, $b \mid (w+1)$이고 서로소인 두 수 $a$, $b$를 모두 찾으면 위 식을 풀 수 있습니다.
- $a \mid w$, $b \mid (w+1)$라는 것은 $ax = w$, $by = w+1$인 두 정수 $x$, $y$가 존재한다는 의미입니다.
- 이를 연립하면 $by - ax = 1$을 얻습니다.
- 확장 유클리드 알고리즘을 사용하면 $bs + at = 1$인 어떤 $s$, $t$를 구할 수 있으며, $by - ax = 1$을 만족하는 모든 $x$, $y$는 임의의 정수 $z$에 대해 다음과 같이 표현됩니다.

$$
y = az + s \; ; \quad x = bz - t
$$

- $w = ax = abz - at$이므로 $1 \le abz - at \le n-2$이며, $ab = 2n$임을 활용해 이 부등식을 정리하면 다음 식을 얻습니다.

$$
\left\lceil \frac{at+1}{2n} \right\rceil \le z \le \left\lfloor \frac{at+n-2}{2n} \right\rfloor
$$

- 위 부등식으로부터 모든 $w$와 $r$을 구하여 위쪽 삼각형에서 조건을 만족하는 모든 칸을 구할 수 있습니다.
- $2n$의 빠른 소인수분해를 위해 ${10}^5$ 이하의 모든 소수를 에라토스테네스의 체로 미리 구해둔 다음, 입력되는 모든 $n$에 대해 가능한 모든 $a$, $b$ 쌍을 순회하면서 정답을 찾으면 문제를 해결할 수 있습니다.

2024 가지컵 - B - Editorial

# 풀이

- 시작점에서 경로를 그려나갈 때, 특정한 가지의 위/아래 여부는 확정된 시점에서 바뀌지 않습니다. 
- $S(A, B)$를 경로를 $(A,B)$까지 그려나가며 확정지을 수 있는 서로 다른 조합의 집합이라고 합시다.
- $A, B \ge 1$에 대해 $S(A, B) = S(A-1, B) \cup S(A, B)$ 가 성립하므로, $|S(A,B)| = |S(A-1, B)| + |S(A, B)| - |S(A-1, B) \cap S(A, B)|$임을 알 수 있습니다.

## 관찰
- 중요한 부분은 $(A-1, B)$와 $(A, B-1)$에 모두 가지가 없으면, $S(A-1, B) \cap S(A, B-1)$ = $S(A-1, B-1)$이라는 점을 관찰하는 것입니다.
- $S(A-1, B) \cap S(A, B-1) \supset S(A-1, B-1)$라는 것은 분명합니다. $(A-1, B-1)$까지 그은 경로를 한 칸 더 연장해서 $(A-1, B)$로 그을 수 있으므로 $S(A-1, B-1) \sub S(A-1, B)$이고, $(A-1, B-1)$까지 그은 경로를 한 칸 더 연장해서 $(A, B-1)$로 그을 수 있으므로 $S(A-1, B-1) \sub S(A, B-1)$이기 때문입니다.
- 이제 $S(A-1, B) \cap S(A, B-1) \subset S(A-1, B-1)$을 보이기 위해, $S(A-1, B) \cap S(A, B-1)$에 속해 있는 원소 $X$를 생각합시다. 
- $(A-1, B)$까지 가는 경로 $p$와 $(A, B-1)$까지 가는 경로 $q$가 있어서 $p$와 $q$의 위/아래 영역은 정확히 같은 결과 $X$를 냅니다.
-  이 두 경로 대신 이들을 한 칸씩 연장해서 $(A,B)$에서 만나게 한 $p'$, $q'$을 생각하고, 이 둘을 경계선으로 갖는 영역을 생각해 봅시다. 그러면 이 영역 안에는 가지가 없습니다. ($(A, B)$에 가지가 있을 수도 있지만, 그건 무시해도 좋습니다)
- 즉 $p'$과 $q'$으로 둘러싸인 영역과 그 경계 내의 점만 사용하는 모든 점은 모두 같은 결과를 냅니다. 해당 영역 내에는 항상 $(A-1, B-1)$과 그 점까지 가는 경로가 있으므로, $X$는 $S(A-1, B-1)$에 속합니다.
## 결론
- 위의 논증을 통해, $(A, B-1), (A-1, B), (A, B)$에 가지가 없으면 $|S(A,B)| = |S(A-1, B)| + |S(A, B)| - |S(A-1, B-1)|$임을 알 수 있습니다.
- 다른 경우의 $|S(A,B)|$는 0이 되거나 직전 점에서의 값과 일치하므로 역시 직전 집합의 개수만으로 식을 얻을 수 있습니다.
- 결론적으로 간단한 $O(NM)$ DP 식을 통해 답을 얻을 수 있습니다. 
- 이외에도 가지의 위치들만 고려하여 계산하는 $O(K \log K)$ 풀이 등이 존재합니다.


2024 가지컵 - C - Editorial

# 풀이
- $N = k$인 적당한 $H$를 정해 높이 $1$인 빌딩에서 가지를 발사할 때, 발사한 가지의 최대 충돌 횟수를 $f(k)$라 합시다.
- 높이 $1$인 빌딩을 제외한 모든 빌딩의 높이가 $1$이 될 수 있다면, $f(k) = 1 + 2 + \dots + (k-1) = \frac{k(k-1)}{2}$입니다.
- $N = k$인 적당한 $H$를 정해 높이 $h$인 빌딩에서 가지를 발사할 때, 발사한 가지의 최대 충돌 횟수는 $f(k - h + 1)$입니다.
- 따라서 $B_i$의 합의 상한은 $\sum_{i = 1}^{N} f(i) = \frac{N(N-1)(N+1)}{6}$입니다.
- 이 상한에 도달하는 $H$를 귀납적으로 구성할 수 있습니다.
- 우선 $N = 2$일 때는 답이 $H = [1, 2]$로 유일합니다.
- $N = k$일 때의 각 $H_i$에 $1$을 더합니다.
- $k \equiv 0 \pmod 4$이면 $\frac{k}{2}+1$번째 원소로 $1$을 삽입합니다.
- $k \equiv 1 \pmod 4$이면 $\frac{k-1}{2}+1$번째 원소로 $1$을 삽입합니다.
- $k \equiv 2 \pmod 4$이면 $\frac{k}{2}+1$번째 원소로 $1$을 삽입합니다.
- $k \equiv 3 \pmod 4$이면 $\frac{k-1}{2}+2$번째 원소로 $1$을 삽입합니다.
- 다른 위치에 $1$을 삽입하면 충돌 횟수가 최대가 되지 않습니다.
- 답의 상한에 도달하는 실례가 있으므로 이 배치는 정답이 됩니다.
# 유일성
- $N = k$인 모든 순열에 다음 조작 $A$를 거치는 것으로 $N = k + 1$인 모든 순열을 만들 수 있습니다.
    - 순열의 각 원소에 $1$을 더합니다.
    - $1$을 원하는 위치에 삽입합니다.
- 조작 $A$ 전후로 $B_i$의 합은 최대 $f(k+1)$만큼 증가합니다.
- 어떤 $k$에 대해, $N = k$일 때 최적이 아닌 어떤 배치 $H'$가 조작 $A$를 거치면 $N = k+1$일 때 최적인 배치 $H''$가 된다고 가정합니다.
- $H'$에서 $B_i$의 합은 $\frac{k(k-1)(k+1)}{6}$ 미만이고, $H''$에서 $B_i$의 합은 $\frac{k(k+1)(k+2)}{6}$입니다.
- 조작 $A$ 전후로 $B_i$의 합이 $f(k+1) = \frac{k(k+1)}{2}$보다 많이 증가했으므로, 가정이 틀렸습니다.
- 최적이 아닌 어떤 배치 $H'$가 조작 $A$를 거치더라도 최적인 배치가 될 수 없고, 최적인 배치에서 조작 $A$를 통해 최적인 배치가 되는 방법이 한 가지뿐이므로 정답이 되는 배치는 유일합니다.


2024 가지컵 - D - Editorial

# 풀이
- `R`에 `D`가 1개 이상 있으면 `W` 또는 `L`이 존재하는 경우는 채소를 낼 수 있는 조합이 존재하지 않습니다.
- `R`에 `D`가 존재하지 않을 때 `W`와 `L` 중 존재하지 않는 결과가 있다면 채소를 낼 수 있는 조합이 존재하지 않습니다.

## `D`가 1개 이상 있을 때
- 모든 키위새는 비깁니다.
- $R$에 `W` 또는 `L`이 존재하는 경우 채소를 낼 수 있는 조합이 존재하지 않습니다.
### $V$에 모든 종류의 채소가 나올 때
- 모든 `?`를 아무렇게나 채워 출력하면 됩니다.
### $V$에 두 가지의 채소가 나올 때
- 모든 `?`를 $V$에 나오지 않는 채소로 채워 출력하면 됩니다.
### $V$에 한 가지의 채소가 나올 때
- 모든 `?`를 나온 채소로 채워 출력하면 됩니다.
### $V$가 모두 `?`일 때
- 모든 `?`를 한 종류의 채소로 채우면 됩니다.
## `D`가 없을 때
- 모든 가지는 이기거나 집니다.
- 만약 `W`나 `L`이 없다면 채소를 낼 수 있는 조합이 존재하지 않습니다.
- `W`와 `L`이 둘 다 있으면 이기는 채소와 지는 채소를 구할 수 있습니다.
- $R_i$가 `W`면 $V_i$가 `?` 또는 이기는 채소이고, $R_i$가 `L`이면 $V_i$가 `?` 또는 지는 채소임을 확인하면 됩니다.
- 위 조건이 성립하지 않으면 낼 수 있는 조합이 존재하지 않습니다.
- 위 조건이 성립하면 $R_i$가 `W`일 때 $V'_i$를 이기는 채소로, $R_i$가 $L$일 때 $V'_i$를 지는 채소로 출력하면 됩니다. 


2024 가지컵 - E - Editorial

# 풀이
- $S_{i,j}$가 같고 인접한 두 토양을 간선으로 연결합시다.
- $(i,j)$와 인접한 $(k,l)$에 대해 $S_{i,j} = S_{k,l}$이면 $H_{i,j} = H_{k,l}$이니 한 컴포넌트에서 $H_{i,j}$의 값은 같습니다.
- $(i,j)$와 인접한 $(k,l)$에 대해 $S_{i,j} > S_{k,l}$이면 $H_{i,j} \ge H_{k,l} + 1$입니다.
- 이때, $H_{k,l}$을 미리 구해놓았다면 $H_{i,j}$의 하한을 알 수 있습니다.
- $(i,j)$가 속한 컴포넌트의 하한은 각 칸의 하한의 최대입니다.
- $H$의 원소의 합이 최소이므로, 각 컴포넌트의 $H_{i,j}$는 계산된 하한이여야 합니다.
- 만약 하한이 존재하지 않는다면 $H_{i,j}$는 $0$이어야 합니다.
- $S_{i,j}$가 증가하는 순서대로 $H_{i,j}$를 구합시다.
- 그러면, $S_{k,l}$이 $S_{i,j}$보다 작다면 이미 $H_{k,l}$을 구했으니 $(i,j)$가 속한 컴포넌트의 하한을 구할 수 있습니다. 
- DFS 또는 BFS를 통하여 현재 컴포넌트의 $H_{i,j}$의 하한을 구할 수 있습니다.
- 플러드 필을 이용하여 $(i,j)$가 속한 컴포넌트의 $H$ 값을 하한으로 채울 수 있습니다.
- 이를 모든 $H_{i,j}$에 대하여 반복하면 $\mathcal{O}(NM \log NM)$에 문제를 해결할 수 있습니다.

2024 가지컵 - F - Editorial

# 풀이
- 어떤 세 꼭짓점이 한 직선 위에 있는 다각형 $G$는 $f$를 적용한 후에도 한 직선 위에 있는 세 꼭짓점이 존재합니다.
- 정다각형은 어떤 세 꼭짓점도 한 직선 위에 있지 않으므로, $G$는 정다각형이 될 수 없습니다.
- 어떤 세 꼭짓점도 한 직선 위에 있지 않은 $K$각형은 $f$를 적용한 후에도 $K$각형입니다.
- 정$N$각형은 꼭짓점이 $N$개이므로, $N = K$여야 합니다.
- 삼차원 공간에서 유리수점으로만 이루어진 정다각형은 정삼각형, 정사각형, 정육각형뿐입니다.
- 따라서 어떤 삼각형, 사각형, 육각형이 정다각형이 될 수 있는지 보면 됩니다.
- $\det{A} \ne 0$인 모든 선형변환 $A$는 주어진 $f$의 조건을 만족시킵니다.
- 따라서 다각형을 정다각형으로 만드는 선형변환 $A$가 존재하면 $f$가 존재합니다.

## 정삼각형
- 삼각형 $ABC$의 한 점 $A$를 원점으로 둡니다.
- 벡터 $\overrightarrow{AB}$와 $\overrightarrow{AC}$는 선형독립이므로 $X \begin{bmatrix} \overrightarrow{AB} & \overrightarrow{AC} \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}$를 만족하는 선형변환 $X$가 존재합니다.
- 따라서 임의의 삼각형은 정삼각형으로 변환 가능합니다.
- 주어진 점에서 삼각형을 찾으면 됩니다.
- 서로 다른 세 점을 골라, 세 점이 한 직선 위에 있지 않으면 삼각형이 만들어집니다.
- $\mathcal{O}(N^3)$에 정삼각형을 만들 수 있는지 판단할 수 있습니다.

## 정사각형
- 정사각형의 마주보는 변은 평행하므로 정사각형으로 변환 가능한 사각형 $ABCD$는 $\overline{AB} \parallel \overline{CD}$와 $\overline{BC} \parallel \overline{DA}$를 만족시켜야 합니다.
- 이를 만족시키는 사각형 $ABCD$의 한 점 $A$를 원점으로 둡니다.
- 벡터 $\overrightarrow{AB}$와 $\overrightarrow{AD}$는 선형독립이므로 $X \begin{bmatrix} \overrightarrow{AB} & \overrightarrow{AD} \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix}$를 만족하는 선형변환 $X$가 존재합니다.
- 따라서 $\overline{AB} \parallel \overline{CD}$와 $\overline{BC} \parallel \overline{DA}$인 것은 정사각형으로 변환 가능할 필요충분조건입니다.
- $\overline{AB} \parallel \overline{CD}$와 $\overline{BC} \parallel \overline{DA}$를 만족하는 사각형을 찾아야 합니다.
- 점 $A$가 좌표의 사전순으로 다른 점 $B$보다 앞에 있다면 $A \lt B$라 정의합니다.
- $A \lt B \lt D$이고 한 직선 위에 있지 않은 세 점 $A$, $B$, $D$를 고릅니다.
- $C = B + \overrightarrow{AD}$로 두면 사각형 $ABCD$는 $A < B < D < C$인 유일한 평행사변형입니다.
- $D < C$이므로, 투 포인터를 이용해 $\mathcal{O}(N^3)$ 시간에 정사각형을 만들 수 있는지 판단할 수 있습니다.

## 정육각형
- 정육각형의 마주보는 변은 평행하므로, 정육각형으로 변환 가능한 육각형 $ABCDEF$는 $\overline{AB} \parallel \overline{DE}$, $\overline{BC} \parallel \overline{EF}$, $\overline{CD} \parallel \overline{FA}$를 만족시켜야 합니다.
- 정육각형 $PQRSTU$에서 $P + \overrightarrow{PQ} + \overrightarrow{PU} = P + \frac{1}{2}\overrightarrow{PS}$이므로, $A + \overrightarrow{AB} + \overrightarrow{AF} = A + \frac{1}{2}\overrightarrow{AD}$이어야 합니다.
- 이를 만족시키는 육각형 $ABCDEF$의 한 점 $A$를 원점으로 둡니다.
- 벡터 $\overrightarrow{AB}$와 $\overrightarrow{AF}$는 선형독립이므로 $X \begin{bmatrix} \overrightarrow{AB} & \overrightarrow{AF} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & -1 \\ 1 & 0 \end{bmatrix}$를 만족하는 선형변환 $X$가 존재합니다.
- 따라서 두 조건은 정육각형으로 변환 가능할 필요충분조건입니다.
- 두 조건을 만족시키는 육각형을 찾아야 합니다.
- $A \lt B \lt F$이고 한 직선 위에 있지 않은 세 점 $A$, $B$, $F$를 고릅니다.
- $C = B + \overrightarrow{AB} + \overrightarrow{AF}$, $D = A + 2\overrightarrow{AB} + 2\overrightarrow{AF}$, $E = F + \overrightarrow{AB} + \overrightarrow{AF}$로 둡니다.
- 육각형 $ABCDEF$는 $A < B < F < C < E < D$이면서 정육각형이 될 수 있는 유일한 육각형입니다.
- $F < C < E < D$이므로, 투 포인터를 이용해 $\mathcal{O}(N^3)$ 시간에 정육각형을 만들 수 있는지 판단할 수 있습니다.

# 유리수점으로만 이루어진 정다각형
- 유리수점으로만 이루어진 정다각형의 존재 여부는 정수점으로만 이루어진 정다각형의 존재 여부와 같습니다.
- 정수점으로만 이루어진 정삼각형과 정사각형, 정육각형은 실례가 있습니다.
- 정수점으로만 이루어진 정오각형 $ABCDE$가 존재한다고 가정합니다.
- $A' = A + \overrightarrow{BC}$, $B' = B + \overrightarrow{CD}$, $C' = C + \overrightarrow{DE}$, $D' = D + \overrightarrow{EA}$, $E' = E + \overrightarrow{AB}$로 둡니다.
-  도형 $A'B'C'D'E'$는 정수점으로만 이루어진 정오각형이며 한 변의 길이가 $\lVert\overrightarrow{AD} - 2\overrightarrow{BC}\rVert < \overline{AB}$입니다.
- 따라서 정오각형 $ABCDE$보다 한 변의 길이가 작습니다.
- 정오각형 $ABCDE$는 정수점으로만 이루어졌으므로 한 변의 길이가 무한정 작아질 수 없습니다.
- 이는 가정에 모순이므로 정수점으로만 이루어진 정오각형 $ABCDE$는 존재하지 않습니다.
- $N = 6$일 경우는 위 논리가 성립하지 않는데, $A'B'C'D'E'F'$가 육각형을 이루지 않기 때문입니다.
- $N \ge 7$인 모든 정$N$각형에 대해서는 같은 방법으로 증명이 가능합니다.

2024 가지컵 - G - Editorial

# 풀이
- 문제에서 제시한 그래프는 무방향 트리입니다.
- 정점은 두 가지 상태를 가집니다.
    - 현재 정점을 방문했는지 여부인 방문 상태
    - 현재 정점에서 연결된 간선 개수가 확정되었는지 여부인 확정 상태
- 따라서 트리의 성질과 정점의 상태에 따라 조건 분기로 이동 전략을 세울 수 있습니다.

## 이동 전략
- 확정되지 않은 $u$ 정점에서 `maze` 이동 방법으로 이미 방문한 $v$ 정점을 방문한다면, $u$ 정점은 확정된 정점으로 판단할 수 있습니다.
- 따라서 처음에는 재방문하는 정점이 올 때까지 `maze` 마법을 계속 사용하는 것이 최적의 전략임을 알 수 있습니다.
- 처음 이동 전략을 진행하는 중에 $u$번 정점에서 이미 방문한 $v$번 정점에 방문했다고 했을 때, $u$번 정점은 항상 단말 정점입니다.
- 이 단말 정점을 없다고 취급한다면, `gaji` 마법으로 $v$번 정점으로 이동한 후 $v$번 정점에서 다시 처음 이동 전략을 취할 수 있습니다.
- 위 과정을 재귀적으로 진행하면 DFS 알고리즘임을 알 수 있고 트리의 모든 간선을 찾을 수 있습니다.

## 마법 사용 최대 횟수
- 다음 3개의 과정은 불가능한 상황입니다.
    - $u$번 정점(방문 X, 확정 O or X)에서 $v$번 정점(방문 O or X, 확정 O or X)으로 이동
    - $u$번 정점(방문 O, 확정 O or X)에서 $v$번 정점(방문 X, 확정 O)으로 이동
    - $u$번 정점(방문 O, 확정 O)에서 $v$번 정점(방문 X, 확정 X)으로 이동
- 다음 과정은 DFS 알고리즘으로 인해 실행되지 않습니다.
    - $u$번 정점(방문 O, 확정 O)에서 $v$번 정점(방문 O, 확정 X)으로 이동
- 따라서 DFS 알고리즘으로 간선을 찾을 경우, 각 간선당 아래 최대 4개의 과정을 진행합니다.
    - $u$번 정점(방문 O, 확정 X)에서 $v$번 정점(방문 X, 확정 X)으로 `maze` 마법으로 이동.
    - $u$번 정점(방문 O, 확정 X)에서 $v$번 정점(방문 O, 확정 X)으로 `maze` 마법으로 이동.
    - $u$번 정점(방문 O, 확정 X)에서 $v$번 정점(방문 O, 확정 O)으로 `gaji` 마법으로 이동.
    - $u$번 정점(방문 O, 확정 O)에서 $v$번 정점(방문 O, 확정 O)으로 `gaji` 마법으로 이동.
- 최대 $4 \times (N-1)$번 마법을 사용하므로 $4N$번 안에 트리의 모든 간선을 찾을 수 있습니다.