KOI 2023 고등부 1차 풀이 및 후기 ★

KOI는 Korean Olympiad in Informatics의 약자로, 한국 정보 올림피아드를 말합니다.

이 대회는 1차 대회와 2차 대회로 이루어져 있고, 1차 대회는 이산 수학을 바탕으로 하는 수학 문제들로 이루어진 1교시와 알고리즘 문제들로 이루어진 2교시로 나누어 진행됩니다. 자세한 정보는 koi.or.kr에서 확인하실 수 있습니다.

 

koi.or.kr에 2교시 문제들의 풀이는 공개되어 있지만 1교시 문제들의 풀이는 제공하지 않아서 풀이를 작성했습니다.

• 팀원 찾기: 엄밀한 증명 고민 중...
  

1교시 풀이

문제의 지문은 링크에서 확인하실 수 있습니다. 또한, biko.kr에서 문제를 채점받을 수 있습니다.

다음은 각 문제에 대해 개인적으로 부여한 난이도와 실제 배점입니다.

1. 그래프의 지름	2. 길 찾기	3. 키 순서	4. 위치 찾기	5. 식의 성질
중 / 5점	하 / 5점	하 / 5점	중 / 5점	하 / 5점
6. KOI 문자열	7. 받아올림	8. 트리 위의 모임	9. 리그전	10. 쪽지 시험
상 / 9점	중 / 9점	상 / 9점	중 / 9점	하 / 10점
11. 보물 상자	12. 약수 게임	13. 원판 배치하기	14. 2층	15. 합이 0
상 / 14점	상 / 14점	하 / 8점	하 / 11점	하 / 11점
16. Max-plus tree	17. 벌집 채우기	18. 팀원 찾기	19. ABBC	20. 교집합과 격자판
중 / 13점	상 / 15점	상 / 15점	중 / 15점	상 / 15점

 

그래프의 지름(5점)

정점이 $10$개이고 지름이 $1$이 되려면 모든 정점쌍을 직접 연결하는 간선이 존재해야 합니다. 따라서 완전그래프를 구성하게 됩니다.

$f(10,1)=\binom{10}2=45$.

 

• 지름이 무한대가 아니라면 무조건 연결 그래프 형태를 갖는다는 것을 알 수 있습니다.
• 연결 그래프가 되려면 간선이 최소한 $N-1$개 존재해야 합니다.

정점이 $10$개이고 지름이 $2$인 무향 단순 연결 그래프를 다음과 같이 간선 $9$개로 구성할 수 있습니다.

따라서 $f(10,2)=9$.

 

정점이 $10$개이고 지름이 $3$인 무향 단순 연결 그래프를 다음과 같이 간선 $N-1$개로 구성할 수 있습니다.

따라서 $f(10,3)=9$.

 

$f(10,1)+f(10,2)+f(10,3)=63$.

 

길 찾기(5점)

$4\times 7$ 직사각형을 최단 경로로 지난 뒤, 수직으로 $5$만큼 이동하고, 나머지 $5\times 5$ 직사각형을 최단 경로로 지나도록 하면 됩니다.

따라서 답은 $\binom {5+5}5 \times \binom {4+7} 4 = 83160.$

 

키 순서(5점)

X가 Y보다 크면 X에서 Y로 가는 방향 간선이 존재하도록 그래프를 만들어봅시다.

• 우선 C가 줄의 맨 앞에 위치합니다.
• A, B, E는 B - A - E 또는 B - E - A 순서를 갖게 됩니다.
• D는 C 뒤의 어느 자리에든 올 수 있습니다.

따라서 D의 위치 $4$가지에 A, B, E의 순서 관계 $2$가지를 곱하면 $8$가지임을 알 수 있습니다.

 

위치 찾기(5점)

$1+2+\cdots +14=105$이므로 한 주기가 돌아갈 때마다 $T=14$에 걸리는 사람의 번호는 $④→③→②→①→⑤→\cdots$가 됩니다.
$2023$ 전까지 $\lfloor 2023/105 \rfloor=19$번의 주기가 돌기 때문에, 마지막 $T=14$에 걸리는 사람의 번호는 $(4-18)\operatorname{mod}\,5=1$번이 됩니다.
따라서 $2023\, \operatorname{mod}\,105=28$번 문제를 푸는 사람의 번호에 $1$을 더하면 $2023$번 문제를 푸는 사람의 번호가 됩니다.

$1+2+\cdots+6=21<28\le 1+2+\cdots+7=28$이므로 $7\, \operatorname{mod}\,5 + 1 = 3$.
따라서 $2023$번 문제를 풀기 위해서는 ③번 자리에 위치해야 합니다.

 

식의 성질(5점)

논리식에 대한 개념을 묻는 문제입니다.

 

$X\to Y = \neg X \vee Y$임을 이용합시다.

$P=(A\wedge B)\to C = \neg (A\wedge B)\vee C$.

$$\begin{aligned}Q&=(\neg C\to \neg A) \vee (\neg C\to \neg B) \\ &= (A\to C) \vee (B\to C) \\ &=  (\neg A\vee C) \vee (\neg B\vee C)\\ &= \neg A\vee \neg B\vee C \\ &= \neg(A\wedge B)\vee C.\end{aligned}$$

 

따라서 "P와 Q는 동일하다" 선지가 답이 됩니다.

 

KOI 문자열(9점)

일단 문제를 보고 케이스를 잘 나눠 풀어야겠다는 생각을 해볼 수 있습니다.

길이가 $\ell$인 KOI 문자열이 아닌 문자열의 개수($s(\ell)$이라고 합시다.)를 생각해 보도록 하죠. 그럼 다음과 같이 세 가지 경우로 나눌 수 있습니다.

• 문자열이 K로 시작하는 경우($k(\ell)$이라고 합시다.)
  
  • 우선 뒤쪽 $\ell-1$개의 자리에서 적당히 K를 분배합니다. (K가 $0$개여도 됩니다.)
  • 남는 자리에 순서대로 I...IO...O를 끼워넣습니다. (O나 I가 $0$개여도 됩니다.)
  • 이렇게 완성되는 형태의 문자열들만이 오직 모든 K로 시작하는 KOI 문자열이 아닌 문자열입니다.
• 문자열이 O로 시작하는 경우
  • 길이가 $\ell-1$인 KOI 문자열이 아닌 문자열을 뒤에 이어 붙이면 됩니다.
• 문자열이 I로 시작하는 경우
  • 길이가 $\ell-1$인 KOI 문자열이 아닌 문자열을 뒤에 이어 붙이면 됩니다.

그렇다면 처음 등장하는 K를 기준으로 앞쪽에 O와 I를 아무렇게나 배치한 뒤, 뒤쪽에 앞에 적은 대로 배치하면 됩니다.

따라서 $s(\ell)=2^\ell + \sum_{i=0}^{\ell-1}2^i \times k(\ell-i)$라는 관계식을 이끌어낼 수 있고, 이걸로 $s(12)$를 구하면 됩니다.

 

이제 $k(\ell)$만 잘 구할 수 있으면 됩니다. 정의에 따라 $k(\ell)=\sum_{i=0}^{\ell-1} \binom{\ell-1}i \cdot (i+1)$임은 알 수 있습니다.

이 식을 잘 조작하면 $k(\ell)=(\ell+1)\cdot 2^{\ell-2}$가 됩니다. (혹은 다른 방식으로 카운팅해서 이 식을 구할 수도 있습니다.)

 

그러면 $s(\ell)=2^\ell + \sum_{i=0}^{\ell-1} 2^i \times (\ell-i+1)\cdot 2^{\ell-i-2}=2^\ell + 2^{\ell-2} \cdot \sum_{i=0}^{\ell-1} (\ell-i+1)$이 됩니다.

 

따라서 $s(12)= 2^{10}(4+2+3+\cdots+13)=2^{10}(3+13\cdot 14 / 2)=2^{10}\times 94$이어서 $n=11$, $m=47$이므로 $n+m=58$입니다.

 

받아올림(9점)

일의 자리만 보면서 연속한 숫자들의 받아올림 여부를 관찰해 봅시다.

• $0+1$은 받아올림이 일어나지 않습니다.
• $1+2$도 받아올림이 일어나지 않습니다.
• $2+3$도 받아올림이 일어나지 않습니다.
• $3+4$도 받아올림이 일어나지 않습니다.
• $4+5$도 받아올림이 일어나지 않습니다.
• $5+6$은 받아올림이 일어납니다.
• $6+7$은 받아올림이 일어납니다.
• $7+8$은 받아올림이 일어납니다.
• $8+9$은 받아올림이 일어납니다.
• $9+0$은 받아올림이 일어나지 않습니다.

그렇다면, 일의 자리 덧셈이 $0+1$ ~ $4+5$인 경우와 $9+0$인 경우로 나눠서 생각해 봅시다.

 

① 일의 자리 덧셈이 $9+0$

연속한 두 수이기 때문에, 일의 자리를 제외한 부분이 받아올림으로 인해 $1$만큼 차이가 날 것입니다.

그렇다면, 원래 범위를 $10$으로 나눈 상태에서 받아올림이 일어나지 않는 쌍의 개수를 세어주면 똑같을 것입니다.

 

② 일의 자리 덧셈이 $0+1$ ~ $4+5$

연속한 두 수이기 때문에, 일의 자리를 제외한 부분이 완전히 동일합니다.

따라서 일의 자리를 제외한 부분에 $0$ ~ $4$를 배정하면 됩니다.

 

$c(n):=i<n$인 음이 아닌 정수 $i$에 대해, $i+(i+1)$이 받아올림이 일어나지 않는 모든 $i$의 개수.

답은 $c(2000)-c(1000)$가 됩니다.

 

$c(2000)=c(200)+2\times 5^3=c(20)+2\times 5^2+2\times 5^3=2+2\times 5^1+2\times 5^2+2\times 5^3=2\times \frac {5^4-1} {5-1} = 312$.

$c(1000)=c(100)+5^3=c(10)+5^2+5^3=1+5+5^2+5^3=\frac {5^4-1} {5-1}=156$.

 

따라서 답은 $312-156=156$입니다.

 

참고로, 적당히 케이스를 나누면서 실수 없이 세어서 풀 수도 있습니다. 대회 중에는 전 이렇게 풀었습니다.

 

트리 위의 모임(9점)

각 간선마다 몇 번 세어지는지 확인을 해주면 됩니다.

간선을 기준으로 나누어지는 양쪽 컴포넌트 각각에서 세 정점을 뽑는다면, 간선을 사용하지 않을 것입니다.

그렇지 않다면 항상 간선을 사용하게 됩니다.

 

따라서 각 간선을 기준으로 양쪽 컴포넌트의 크기를 각각 $A$, $B$라고 하면 $\binom {A+B}3-\binom A3-\binom B3$을 반복적으로 더해주면 됩니다.

 

그러면 $\binom {12}3 \times 11 - \binom 13 \times 6 - \binom 23 \times 3 - \binom 33\times 1 - \binom 63 \times 2 - \binom 93 \times 1 -\binom {10}3\times 3 - \binom {11}3\times 6 = 2420-1-40-84-360-990=945$이므로 $\sum f(a,b,c)=945$입니다.

 

리그전(9점)

보통 이런 유형은 표를 그려서 분석하는 것이 좋습니다.

표를 그리기에 앞서 알아낼 수 있는 사실들을 정리해 봅시다.

각 팀 X의 승리 횟수, 무승부 횟수, 패배 횟수를 각각 W_X, M_X, L_X라고 합시다.

 

일단 주어진 조건을 표현하면,

• W_D $>$ W_C
• L_B $>$ L_C
• L_A $=$ L_D $=$ 0, W_A $=$ W_D, M_A $=$ M_D

입니다.

 

이걸 조금 정리해 보면,

• W_A $=$ W_D $>$ W_C
• L_B $>$ L_C
• M_A $=$ M_D $=$ 3 $-$ W_A $=$ 3 $-$ W_D
  

입니다.

 

생각을 해보면, 변수의 종류가 많고 각 변수가 가질 수 있는 값도 여러 가지일 뿐 만 아니라, 그 순서까지 결정하게 된다면 고려할 경우의 수가 매우 많을 것입니다. 따라서, 문제의 'A와 C의 경기 결과'라는 말에 집중해 봅시다.

 

그러면 A와 C의 결과 세 가지를 고정하고, 각 경우에 대해서 실례가 적어도 하나 존재하는지 판단하면 된다는 것을 알 수 있습니다!

 

일단 표에서 채울 수 있는 칸들을 채워봅시다.

• A와 D 모두 진 적이 없으므로, 무승부가 나야 합니다.

① A가 C에게 짐

L_A $=$ 0라는 조건이 있었죠? 모순되므로 불가능합니다.

 

② A가 C와 무승부

• W_A $=$ 0이면 W_A $>$ W_C여서 W_C로 가능한 값이 없으므로 A가 한 번은 이겨야 합니다.
• 따라서 A는 B를 이깁니다.

• A와 D를 제외하고는 M_X에 대한 제약이 없습니다.
• 따라서 남는 자리에는 M 위주로 채워줍니다.
• 동시에, L_B $>$ L_C 조건이 있으니 B쪽에 L을 몰아줍시다.

모든 조건을 만족하는 실례가 존재합니다.

따라서 A는 C와 비길 수 있습니다.

 

③ A가 C를 이김

• L_B $>$ L_C 조건이 있으니 B쪽에 L을 몰아줍시다.

모든 조건을 만족하는 실례가 존재합니다.

따라서 A는 C를 이길 수 있습니다.

 

최종적으로 "A가 이기거나 비겼다" 선지가 답이 됩니다.

 

쪽지 시험(10점)

교란수와 동일한 방식으로 포함배제 식을 세워 계산하면 됩니다. 교란수를 포함배제로 계산하는 것은 잘 알려져 있으므로 조금만 검색해 봐도 좋은 학습 자료를 찾을 수 있을 것입니다. 따라서 자세한 설명은 생략합니다.

 

$7!-\binom 4 1 \cdot 6!+\binom 4 2 \cdot 5!-\binom 4 3 \cdot 4!+\binom 4 4 \cdot 3!=2790.$

 

보물 상자(14점)

각 상자 $i$에 대해 보물이 있을 확률을 $P_i$, 꺼내는 비용을 $C_i$라고 합시다. 또, 상자의 순열은 $\{\pi_i\}$로 표현합시다.

 

그럼 순열 $\{\pi_i\}$에 대해서, 보물을 찾기 위해 필요한 총비용의 기댓값은 $\displaystyle \sum _{i=1}^{5} \left ( P_{\pi_i}\times \sum_{j=1}^{i} C_{\pi_j} \right )$가 됩니다.

 

보통 기댓값 문제에는 DP가 잘 먹힙니다. 그래서 우선, 식에서 재귀적인 구조를 찾아보려고 노력합니다. 하지만 잘 나타나지 않습니다.

 

식에서 $\pi_i$와 $\pi_{i+1}$을 교환했을 때 총비용의 기댓값이 어떻게 변화하는지 관찰해 봅시다.

• 교환 전: $\displaystyle \cdots+P_{\pi_i} \times (\sum_{j=1}^{i-1} C_{\pi_j}+C_{\pi_i}) + P_{\pi_{i+1}} \times (\sum_{j=1}^{i-1} C_{\pi_j}+C_{\pi_i}+C_{\pi_{i+1}})+\cdots$
• 교환 후: $\displaystyle \cdots+P_{\pi_{i+1}} \times (\sum_{j=1}^{i-1} C_{\pi_j}+C_{\pi_{i+1}}) + P_{\pi_{i}} \times (\sum_{j=1}^{i-1} C_{\pi_j}+C_{\pi_i}+C_{\pi_{i+1}})+\cdots$

교환 후에 기댓값은 $P_{\pi_{i}}\times C_{\pi_{i+1}} - P_{\pi_{i+1}}\times C_{\pi_{i}}$만큼 증가합니다. 이 변화량은 음수일 수도, 양수일 수도 있습니다. 그렇다면 변화량이 음수인, $P_{\pi_{i}}\times C_{\pi_{i+1}} - P_{\pi_{i+1}}\times C_{\pi_{i}} < 0$일 경우에만 교환하는 것이 이득이 됩니다.

 

그런데 이 부등식을 다시 정리하면, $\displaystyle \frac {P_{\pi_i}} {C_{\pi_i}} < \frac {P_{\pi_{i+1}}} {C_{\pi_{i+1}}}$가 됩니다. 이 말인즉슨 $\displaystyle \frac {P_{\pi_i}} {C_{\pi_i}}$에 대한 내림차순으로 $\{\pi_i\}$를 설정하여 기댓값을 구하면 최적이 된다는 뜻입니다. (일종의 그리디 알고리즘이라고 보면 될 것 같습니다.)

 

따라서 C - B - E - D - A 순으로 보물 상자의 확인해 보면 되겠습니다. 계산이 살짝 길기 때문에 계산 과정은 생략합니다. 답, $X$는 $2475$입니다.

 

약수 게임(14점)

사고력 마지막 문제입니다.

게임의 상태 그래프를 그려보며 작은 $n$들에 대해 게임의 승부를 관찰해 봅시다. 이기는 수들의 집합을 $W$, 지는 수들의 집합을 $L$라고 합시다.

 

게임의 상태 그래프를 그리는 규칙은 단순합니다.

• 정점 $n$에서 $1<d<n$인 $n$의 모든 약수 $d$에 대해 정점 $n-d$로 가는 간선을 잇습니다.
• 정점 $x$에 대해서,
  • 나가는 간선에 위치한 모든 정점 $y$가 $W$의 원소라면 $x\in L$이고,
  • 그렇지 않다면 $x\in W$입니다.

초록색은 𝑊, 빨간색은 𝐿입니다. 정점 1은 빼먹었네요.

그래프를 그렸으니, 이제 $W$, $L$의 원소들을 소인수 분해시킨 상태를 관찰해 봅시다.

• $W=\left \{ 2^2,\ 2\times 3,\ 2\times 5,\ 2^2\times 3,\ 2\times 7,\ 2^4,\ 2\times 3^2,\ 2^2\times 5\right \}$
• $L=\left \{1,\ 2,\ 3,\ 5,\ 2^3,\ 3^2,\ 7,\ 11,\ 13,\ 3\times 5,\ 17,\ 19\right \}$

이렇게 적어두면... $W$의 원소들은 전부 짝수라는 것을 알 수 있습니다. 그 외에는 바로 보이는 무언가가 없어서 스프라그-그런디 정리를 이용하는 방향으로 생각을 해볼 수 있습니다. 하지만 별다른 무언가는 없었습니다.

 

그래서 $W$와 $L$의 원소들을 다시 잘 살펴봅니다. $2^\alpha$꼴의 수들은 $\alpha$가 홀수면 $L$, 짝수면 $W$가 되는 것 같습니다. $1$은 예외적이고요. 이 경우들을 제외하면 홀수면 $L$, 짝수면 $W$이 되는 것 같습니다. 사실 설득력 있는 규칙 같지는 않은데, 정점 $15$개를 넘어서 정점 $20$~$25$개까지 그래프를 그려보게 되면 생각보다 규칙이 다 들어맞는다는 걸 확인할 수 있습니다!

 

claim

정리하면, 다음 규칙이 성립합니다.

• $x$: 홀수 → $x\in L$
• $x$: 짝수
  • $x$: $2^{2k-1}$꼴임 → $x\in L$
  • $x$: $2^{2k-1}$꼴이 아님 → $x\in W$

---

proof

강한 수학적 귀납법을 이용합니다.

우선, $n=1$인 기저 상황에서 규칙은 성립합니다.

$n=k$인 상황에서, $n<k$에 대해 규칙이 성립한다고 가정합시다. 이때, $n$의 형태에 따라 케이스를 분류해 봅시다.

 

Case 1. $n$: 홀수

• $n$의 약수 $d$ ($1<d<n$)는 홀수입니다. 따라서 $n-d$는 짝수입니다.
• $n$과 $d$는 모두 $d$의 배수입니다. 따라서 $n-d$도 $d$의 배수입니다.
• $n-d$는 짝수이고, 1보다 큰 홀수인 $d$의 배수입니다.
• 따라서 $n-d$는 $2$ 이외의 소인수를 갖는 짝수여서 $n-d\in W$입니다.

$n$에서 나가는 간선에 위치한 모든 정점은 $W$의 원소이므로 $n\in L$입니다.

 

Case 2. $n$: 짝수

 

Case 2-1. $n$: $2^\alpha$꼴임

• $2^\beta$ ($0<\beta<\alpha$)꼴만을 약수로 갖습니다.
• 그럼 $n-d=2^\beta \times (2^{\alpha - \beta}-1)$입니다.
• 일단, $\alpha-\beta>1$일 경우, 홀수를 약수로 갖는 짝수가 되어 $n-d\in W$가 됩니다.
• 그런데 $\alpha-\beta=1$일 경우에는 $n-d=2^\beta$가 됩니다.
• 따라서 $\alpha-1=\beta$가 홀수일 경우 $n-d\in L$가 존재합니다.

$\alpha$가 짝수일 경우, $n$에서 나가는 간선에 위치한 정점 중 $L$의 원소가 존재하므로 $n\in W$입니다.

$\alpha$가 홀수일 경우, $n$ 에서 나가는 간선에 위치한 모든 정점은 $W$의 원소이므로 $n\in L$입니다.

 

Case 2-2. $n$: $2^\alpha \times m$꼴임 ($m$: 홀수, $\alpha>0$)

• $n$은 $m$을 약수로 갖습니다.
• 따라서 $n-d=(2^\alpha-1)\times m$가 존재합니다.
• $2^\alpha-1$과 $m$은 모두 홀수이므로, $n-d\in L$입니다.

$n$에서 나가는 간선에 위치한 정점 중 $L$의 원소가 존재하므로 $n\in W$입니다.

 

$n=k$인 모든 케이스에서 여전히 규칙을 만족함을 확인했습니다. $\square$

---

규칙에 따라, $1$ 이상 $1\, 000$ 이하의 모든 자연수 $n$ 중 A가 이기도록 하는 $n$의 개수는 (짝수의 개수)-($2^{2k-1}$꼴의 개수)가 됩니다.

$2^{2k-1}$꼴은 $2,8,32,128,512$가 전부이므로, 답은 $1\,000/2-5=495$입니다.

 

원판 배치하기(8점)

첫번째 비버챌린지 문제입니다.

세 번째 점이 양 옆의 점과의 거리가 제일 멀기 때문에 가장 큰 빨간색 원을 배치합니다. (이게 항상 최적이라는 보장은 없지만, 눈으로 봤을 때 가장 큰 원을 다른 곳에 배치하면 답이 없습니다.)

 

이를 기준으로 남는 반지름들이 하나씩 특정되므로, 남는 원을 배치하면 됩니다.

 

 

2층(11점)

순열에 사이클이 있다는 성질을 이용합니다.

직접 적어보면, 다음 두 가지 사이클만이 존재한다는 것을 알 수 있습니다.

• $15\to 7\to 6\to 13\to 12\to 14\to 3\to 2\to 9\to 8\to 15\to 7\to \cdots$
• $10\to 1\to 5\to 11\to 4\to 10\to 1\to \cdots$

따라서 크기가 작은 두 번째 사이클 속 수들을 전부 선택해 주면 됩니다.

꼭 사이클의 방향을 따라서만 교환이 일어나야 하냐? 한다면 답은, 그렇습니다.

어떤 열을 두 번 이상 교환하는 것은 손해입니다. 따라서 하나의 열을 교환했다면, 그대로 끝까지 유지하게 됩니다. 이때 겹치는 수가 존재하는 열이 있다면 그 열은 이 열이 끝까지 동일한 상태를 유지하니까 역시 무조건 교환해야 하겠죠?

따라서 사이클 속 열들은 무조건 전부 한 번씩 교환을 해주어야 합니다.

 

합이 0(11점)

연속구간합이 0이라는 뜻은 누적합 배열에서 구간의 시작 이전 지점과 마지막 지점의 값이 같은 것과 동치입니다.

따라서, 누적합 배열에서 최빈값에 맞춰 수열을 분할하면 됩니다.

 

누적합 배열을 직접 적어보면,

$7\;2\;4\;0\;1\;7\;4\;0\;4\;1\;2\;7\;4\;1$이 되어서, 최빈값인 $4$에 맞추어 수열을 분할하면 됩니다.

 

 

Max-plus tree(13점)

max 정점은 서브트리 중 가장 큰 값을 가지는 서브트리를 제외하고 전부 무시합니다.

따라서 더 큰 값을 만들 수 있는 서브트리에 몰아주는 것이 최적입니다.

 

덧셈 항이 더 많은 서브트리를 남겨두고, 반대쪽은 현재 쓸 수 있는 수들 중 작은 값들부터 배치하기를 반복하면 됩니다.

편의상 팔각형을 별모양으로 대신했습니다.

 

다음 그림은 초기의 상태입니다.

빨간색으로 지운 부분들에 작은 값들을 몰아서 배치한 뒤, 무시하고 다음으로 넘어갑시다.

 

무시하고 나면 남는 정점들은 다음과 같습니다. 이때 max 정점의 자식이 하나뿐이라면 그대로 그 자식이 max 정점의 값이 될 것입니다.

 

정리하고 나니 후보가 눈에 띄게 줄었습니다. 빨간색으로 지운 부분은 반대쪽 서브트리보다 나을 게 없죠? 마찬가지로 작은 값들을 배치하고 무시한 뒤 다음으로 넘어갑시다.

그리고 plus 정점 밑에도 전부 plus 정점들과 리프 정점들 뿐이면 하나로 합쳐줄 수 있겠죠?

 

합쳐주고 나니 세 수의 합과 두 수의 합이 남네요. 두 수의 합 쪽을 빨간색으로 지워줬습니다.

이제 max 정점 자리에 세 수의 합이 그대로 올라갈 것이고, 그러고 나면 plus 정점과 리프 정점들만이 남습니다.

여기에 임의의 순서로 남은 수들인 $11$~$16$을 배치합니다. 그럼 루트 정점의 값은 $11+12+\cdots+16=81$이 됩니다.

 

벌집 채우기(13점)

저는 아래 영상과 같이 점진적으로 $x$를 줄여서 $x=m=9$를 달성했습니다.

 

정해의 경우에는 다음과 같이 구성되었습니다.

이 외에도 다양한 구성 방법이 존재할 수 있습니다.

 

아무튼, $m=9$임을 증명해 봅시다. $x\le 8$을 달성할 수 없다는 뜻이기도 하여, 이를 증명하면 충분합니다.

다양한 규칙을 관찰할 수 있습니다.

• 어떻게 전이되든 테두리만 닫혀 있으면 결과적으로 안쪽은 다 채워진다. 왜냐하면 테두리의 안쪽은 둔각이 존재해서 항상 세 면과 인접한 칸이 존재하기 때문이다.
• 테두리를 중점적으로 보면 안쪽으로 움푹 파인 형태가 세 면과 인접한 상태인데 이들이 점차 감소한다.
• 칸들이 모두 전이에 잘 이용된다면 각 칸을 지나는 전체 정육각형과 평행한 직선들을 테두리로 하는 가장 큰 육각형으로 전이가 끝난다.

모두 괜찮은 아이디어 같긴 하지만, 증명에 도달하기에는 부족해 보입니다. 하지만 공통적으로 '테두리'랑 관련이 있는 것을 알 수 있습니다. 테두리에 집중해서 다음과 같은 관찰도 할 수 있습니다.

• 세 면과 인접한 상태의 칸이 칠해질 때 테두리가 오목한 모양에서 볼록한 모양으로 바뀌지만, 그 둘레의 길이는 일정하다.

왜 그럴까요? 세 면과 인접한 칸이 칠해져 있지 않을 때 인접한 세 면이 둘레에 포함됩니다. 그리고 이 칸을 칠하게 된다면 칸과 인접하지 않은 세 면이 칠해지게 됩니다. 따라서 둘레의 길이가 일정합니다. 반면 네 면 이상과 인접한 칸이 있었다면 칠해진 후 둘레의 길이가 오히려 감소하고, 두 면 이하와 인접한 칸이 있었다면 칠해지지 않아서 둘레의 길이가 그대로입니다.

 

둘레의 길이의 합이 클수록 가능한 최대 넓이도 커지는 것은 당연합니다. 그렇다면, 전이 과정에서 네 면 이상과 인접한 칸이 없도록 효율적으로 전이된다면 초기 상태의 둘레의 길이의 합과 동일한 육각형이 최종 형태가 될 것입니다.

 

위에서 보인 답들은 $x=9$를 달성했습니다. 처음 $x=9$일 때, 색칠된 칸의 개수는 $9$, 인접한 면의 수는 각각 $6$이므로 $6\times 9=54$가 둘레의 길이의 총합입니다. 그리고 전체 정육각형의 둘레도 $54$입니다. 따라서 $m\le 8$일 때 절대로 모든 칸을 칠할 수 없습니다.

 

팀원 찾기(15점)

$2N$명의 사람들이 원탁에 둘러앉아 있다. 이 사람들이 두 명씩 짝을 지어 $N$개의 팀을 이루었다.
하나의 팀에 속한 두 사람이 원탁에서 인접한 자리에 앉도록 하고 싶다. 이를 위해, 다음 동작을 반복할 수 있다.

• 인접한 두 자리에 앉은 사람들이 일어나 서로 자리를 바꾼다.

여러분은 이 동작을 최소한으로 수행해 목표를 달성해야 한다.
아래 그림에서 숫자가 적힌 원은 사람을 나타내고, 원 안의 숫자는 그 사람이 속한 팀의 번호를 나타낸다. 인접한 두 사람 사이를 클릭해 두 사람의 자리를 바꿀 수 있다.
 
채점 방식
총 다섯 개의 문제가 주어진다. 각 문제를 해결하면 20%의 점수를 받을 수 있다.
 
주의사항
점수를 얻기 위해서는 반드시 제출 버튼을 눌러 제출해야 한다. 제출 버튼을 누르면 헌재 상태가 저장된다.
 

풀이

모든 팀에 대해서 자리를 바꿀 때마다 자리를 바꾸는 두 팀원이 모두 짧은 호의 방향으로 가까워지게 해야 합니다. 한 팀원의 두 팀원이 만나기 직전에 이것이 불가능한 경우가 발생하는데 이는 아래 그림의 사례 (C)로서, 안에 위치한 팀원 쌍을 $2$번의 이동으로 빼내면 됩니다.

증명은... 까다로워 보입니다.

 

ABBC(15점)

차수의 반절을 진입 차수, 나머지 반절을 진출 차수로 갖도록 방향을 결정하면 됩니다. 차수가 홀수라면 $1$ 차이가 나게끔 맞춰주면 됩니다.

일반적인 그래프에 대한 증명은 까다롭지만, 저는 하여튼 대회 중에 주어진 예제들은 모두 모든 정점에 대해서 이를 만족시킬 수 있다는 믿음을 가지고 모든 문제를 풀어서 맞혔습니다.

이제 일반적인 그래프에 대해서 저렇게 만족시킬 수 있는지 증명을 해봐야겠죠?

 

우선 세 번째 그래프처럼 트리 그래프의 경우를 생각해 봅시다.

모든 정점에 대해 진입/진출 차수 차이가 최대 $1$이 되도록 방향이 설정된 두 트리를 생각해 봅시다. 그리고 두 트리를 연결하는 방향이 정해지지 않은 간선이 하나 있다고 생각해 봅시다. 필요에 따라 각 트리 속 간선들을 전부 뒤집거나 내버려 두거나 하여 이 간선에 방향을 결정한 뒤에도 모든 정점에 대해 진입/진출 차수 차이가 최대 $1$이 되도록 방향을 설정할 수 있습니다.

 

그럼 이제 일반적인 그래프의 경우를 생각해 봅시다.

방향이 정해지지 않은 일반적인 그래프에서 사이클을 하나씩 골라서 한 방향으로 간선들의 방향을 정해준 뒤, 이 간선들을 방향이 정해지지 않은 고려 대상에서 제외하기를 반복합시다.

그렇다면, 각 정점의 진입/진출 차수의 차이는 그대로 유지^[1]되면서 방향이 정해지지 않은 간선들은 점차 줄어^[2]듭니다. [2]에 따라 사이클에 방향을 정해주는 과정은 유한하고, 언젠가는 방향이 정해지지 않은 간선들이 포레스트를 형성하게 됩니다. 또한 [1]에 따라 포레스트의 모든 정점에 대해 진입/진출 차수 차이는 $0$이 됩니다. 마지막으로, 포레스트의 각 트리들에 위에서 언급한 트리 그래프에서의 규칙을 통해 간선의 방향을 결정하면 모든 정점에 대해 진입/진출 차수 차이가 최대 $1$이 되도록 완성할 수 있습니다.

 

따라서 일반적인 그래프에서 최적으로 방향을 설정할 수 있습니다.

 

교집합과 격자판(15점)

문제 지문에 설명되지 않은 정보가 하나 있습니다.

만들어야 하는 상태와 일치하는 칸은 O, 일치하지 않은 칸은 X가 표시됩니다.

수도쿠와 비슷한 순도 100%의 퍼즐 문제입니다. 개인적으로는 마지막 문제인 만큼, 조금 더 어렵고 수학적인 문제였으면 좋지 않았을까.. 싶습니다.

 

관찰 1. $1$, $2$, $3$, $4$라는 원소 자체는 대칭적이다

문제의 정답을 상상해 봅시다. 거기서 $1$과 $2$의 포함 여부만 반대고, 나머지는 동일한 쌍들을 교환해 봅시다. 그래도 여전히 정답일 것입니다.

 

관찰 2. 색칠된 칸의 개수와 해당 행/열의 집합의 크기가 대응된다

그리고 당연히, 행/열의 위치를 바꾸어도 변함은 없습니다.

 

시행 1. 색칠된 칸이 8개인 열들을 $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$로 설정한다

순서가 상관없어서 그냥 1-2-3-4로 한 것뿐입니다.

 

시행 2. 색칠된 칸이 8개인 행들을 시행 1에서 설정한 열들 중 색칠된 칸으로 교차하는 열에 대응되는 집합으로 설정한다

색칠된 칸이 8개인 열은 색칠된 칸이 8개인 행 4개 중 자신과 같은 집합에 대응되는 행 하나에 대해서만 색칠된 칸으로 교차하고, 나머지에 대해서는 색칠되지 않은 칸으로 교차하기 때문입니다.

시행 1, 시행 2 이후의 모습입니다. 교차하는 칸들에 표시가 되어 있습니다.

관찰 3. 열의 크기가 1인 집합들이 행에 집합의 원소 포함 여부를 나타냅니다

시행 2 이후 교차 지점들을 관찰하면 떠올릴 수 있습니다.

열의 $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$와 교차하는 지점들에 원소의 포함 여부가 체크됩니다.

 

시행 3. 열의 크기가 1인 집합들에 맞게 모든 행들의 위치를 결정합니다

시행 3 이후의 모습입니다.

시행 4. 시행 3과 비슷하게 행의 크기 1인 집합들을 기준으로 모든 열의 위치를 결정하여 정답을 완성합니다

시행 4까지 끝낸 후 정답을 만든 모습입니다.

 

후기

1교시

예년 기출들을 풀어본 결과, 비버챌린지가 그다지 어렵지 않고 배점은 상대적으로 꽤나 높아서 비버챌린지를 중점적으로 푸는 전략을 택했다.
결과적으로 전략은 성공적이었다.
108점을 받았다. 1번과 2번을 바보같이 실수해서 10점을 날려먹은 게 좀 아쉽지만, 이 점을 제외하고는 굉장히 만족스럽게 풀었다.

 

2교시

15:52:00에 시험이 시작되었고, 우선 빠르게 템플릿을 작성했다.
 
1번 대피소

앞쪽을 읽다가 '맨해튼 거리 - 체비쇼프 거리 변환을 써야 하나? 이거 공부할까 고민을 했는데 왜 넘겼지?' 하다가 '1번에 그런 게 나올 리 없구나' 하고 마저 읽은 다음에 차분하게 삼중 for문을 짰다. 예제가 안 나오길래 k에 맞춰서 단일, 이중, 삼중 for문으로 나눠 적었다.
제출해서 16:02:15에 100점을 받았다.

2번 주유소

일단 서론이 트리에 대한 설명이길래 기분이 좋았다. 골드~플래 중위에 있는 트리 DP들에 스스로 강점이 있다고 생각했기 때문이다.
가장 큰 깊이와 k를 비교하여 트리 DP를 짜면 되겠다 싶어서 코드를 짜려다가, 생각해 보니 양쪽과 연결되는 경우를 빼먹어서 다시 생각을 했다. 가장 큰 깊이 두 개의 합과 관련지으면 되겠다 싶었다.
그대로 짜서 16:21:31에 100점을 받았다.

3번 블록 쌓기

제목을 보고 2022년 koi 1차 1교시 기출문제가 떠올랐다. 딱히 관련은 없었다.
여러 가지 관찰을 시도했지만, 괜찮은 방법이 떠오르지 않은 채 30분가량 지났던 것 같다. 그래도 좀 긁어야겠다 싶어서 17:07:54에 7점을 받았다. 그 뒤로 여러 관찰을 해봤지만 좀처럼 가닥이 잡히지 않은 채 끝났다.

총점 108+207=315점을 득점했고, 은상을 받았다. 전체 부문은 은상 중상위권, 일반고 부분은 은상 상위권 정도인데, 1교시에서 실수한 문제들과 2교시에서 긁지 못한 점수를 놓치지 않았더라면 금상도 가능했을 것 같아서 조금 아쉽다.

 

총평

예년보다 어려웠다는 평이 많은 것 같습니다.

1교시의 난이도는 약간 상승했습니다. (작년에 워낙 난이도 상승이 컸죠)

 

사고력의 난이도는 작년보다 조금 상승했습니다. 2번, 3번, 10번을 제외하고는 전형적이지만 시간이 오래 걸리는 유형과 애초에 새로운 유형들로 꽉 차있었습니다. 작년에 꽤 쉽게 풀 수 있는 문제들이 그래도 몇 개는 있었던 것과 대조적입니다.

비버챌린지의 경우에는 앞쪽 13~16번은 전형적이었고, 17~20은 상대적으로 신선했습니다. 하지만 부분 문제를 예년보다 잘게 쪼개 놓아서, 오히려 비버챌린지에서 일정 점수를 받는 난이도는 작년보다 낮아졌다고 느껴집니다. (예를 들어 2022 기출의 17~19번은 부분 문제가 없어서 문제를 통으로 풀어낼 아이디어 없이는 접근할 수 없었습니다) 또한, 정확한 증명이 없이도 답을 맞힐 수 있어서 더 풀 만 했던 것 같네요.
물론, 대회가 끝나고 증명과 함께 문제를 풀어보려는 입장에서는 2022년 기출 대비 난이도가 많이 상승했습니다.

 

개인적으로 높은 점수를 받기 위해서는 비버챌린지에 전략적으로 시간 분배를 하는 것이 제일 중요했다고 생각합니다.

2교시는 난이도가 많이 상승했습니다.

 

1번은 작년보다 살짝 쉬워졌지만, 대충 비슷한 것 같습니다. 브론즈 1 정도가 적당할 것 같네요.

 

2번에서 많은 학생들이 애를 먹었습니다. 백준 기준으로 플래티넘을 받을 것이 확실해 보여요. 하지만 이 유형이 익숙한지에 따라 개인차는 존재하는 것 같습니다.

 

3번도 작년보다 어려워진 것 같습니다. 이 문제의 독특한 점은 서브태스크의 제약 조건이 ioi 문제처럼 섬세하게 구성되었다는 점입니다. 하지만 점수 배분이 세세하더라도 득점하기는 매우 어려웠습니다. 작년의 '보급' 문제의 1, 2번 부분 문제는 어느 정도 긁을만했을 뿐 아니라 얻을 수 있는 점수가 꽤 컸던 것과는 대조적입니다. 아직 전체 문제에 대한 풀이는 모르지만, '보급'보다 어려울 것이라고 예상합니다.

 

마무리

1학년 때에는 당연히 1차를 통과할 줄 알았지만 무상으로 떨어졌고, 2학년 때에는 1학년 때보다 백분위가 더 떨어졌습니다. 당시 코드포스 블루여서 꽤 자신이 있었는데도요... 그래서인지 이번 수상이 매우 값지고 감사하게 느껴집니다!

 

좋은 문제들을 제공한 KOI 대회 측에 감사드립니다!