2024년 1월 PS 일지

수학이 더 많다.

문제 뒤의 (O)는 풀이 없이 풀었다는 뜻이고, (X)는 풀지 못하고 풀이만 확인했다는 뜻이다.

ps문제의 경우 (△)는 풀이를 까고 업솔빙했다는 뜻이다.

 

1. IMO Shortlists

수올 공부를 안 한지 3년은 된 것 같은데, 정말 오랜만에 다시 시작했다. 대수, 기하, 정수는 기초만 알아서 손도 못 대겠고, 그나마 조합 분야가 풀리는 것 같다. (이마저도 어려운건 못 풀겠다)

 

1.1. 2001 IMO Shortlist C3 (O)

Define a $k$-clique to be a set of $k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

풀이

임의의 $C_3$을 하나 잡고 $C=\{a, b, c\}$라 하자. 
우선 $C$와의 교집합이 $\{a\}$인 $C_3$이 없는 경우, 그래프의 모든 $C_3$는 $b$나 $c$를 포함한다. 따라서 $\{b, c\}$가 답이 된다. $\{b\}, \{c\}$인 경우도 마찬가지이다.

그렇지 않은 경우를 가정하자 : $C$와의 교집합이 $\{a\}, \{b\}, \{c\}$인 $C_3$이 각각 존재한다.

$C$와의 교집합이 $\{b\}$인  $C_3$을 $\{b, p, q\}$, $\{c\}$인 $C_3$을 $\{c, r, s\}$라 하자. 
이 두 사이클은 교집합이 있어야 한다. 일반성을 잃지 않고 $s=q$라 하자.

$C$와의 교집합이 $\{a\}$인 $C_3$을 $\{a, x, y\}$라 하자. $\{b, c, q\}$는 크기 3의 사이클이므로 $\{a, x, y\}$와 겹치는 원소가 있어야 한다. $q \ne a$이므로 $q$는 $x$ 또는 $y$이다. 일반성을 잃지 않고 $x$라 하자. 

이렇게 하면 $\{a, b, c, q(=x)\}$는 $K_4$이다. 조건에 의해 이 클리크 임의의 $C_3$은 최소 두개의 교집합을 갖는다.

주어진 그래프에 $K_5$가 없으므로, $a, b, c, q$와 모두 인접한 정점은 있을 수 없다. 따라서 $\{ a, b, x\}$ 형태의 $C_3$와 $\{ c, q, x \}$ 형태의 $C_3$이 동시에 존재할 수 없으므로, $(a, b)$나 $(c, q)$를 제거하면 모든 $C_3$을 제거할 수 있다.

다른 친구와 함께 풀었었는데, 그 친구의 풀이가 정해이고 나의 풀이는 정해와 다른 풀이인 것 같다. 개인적으로는 내 풀이가 더 마음에 든다.

1.2. 2004 IMO Shortlist C3 (O)

(Australia) The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer $n \ge 4$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from a complete graph on $n$ vertices (where each pair of vertices are joined by an edge).

 

풀이

관찰 1. 답은 $N$ 이하이다.
$N$개의 간선만을 남기는 해가 있음을 보인다.

$N=4$일때 : 아무 연산을 두 번 시행하면 총 $4$개의 간선만을 남길 수 있다.

$N=k$일때 $k$개만의 간선을 남길 수 있었다 가정하자.
$N=k+1$의 경우, $V(G)=\{ v_1, v_2, \cdots v_{k+1} (=u)\}$이라 하자. 각 $i (2 < i \le k)$에 대하여 순차적으로 사이클 $\{u, v_1, v_2, v_i\}$를 골라 간선 $(u, v_i)$를 제거한다. 이후 $\{u, v_2, v_1, v_3\}$를 골라 $(u, v_2)$를 제거한다. 이렇게 하면 $u$는 리프가 되고, 남은 $\{v_1, \cdots v_k\}$ 정점들에 대하여 $k$개의 간선만을 남길 수 있었으므로 총 $k+1$개의 간선이 남는다.

수학적 귀납법에 의하여 위 관찰이 성립한다.

관찰 2. 답은 $N-1$ 이상이다.

고른 사이클이 $\{a, b, c, d\}$, 간선 $(a, b)$가 제거되었을 때 $a$가 속한 컴포넌트와 $b$가 속한 컴포넌트는 같다. 따라서 주어진 연산은 그래프의 연결성을 변화시키지 않는다. 초기 그래프는 완전그래프이므로, 몇 회의 연산이 시행된 이후의 그래프도 연결이다. 따라서 $|E(G)| \ge |V(G)|-1$, 답은 $N-1$ 이상이다.

따라서 답은 $N-1$ 또는 $N$이다. 답이 $N-1$일 필요충분조건은 몇 회의 연산을 시행하여 완전그래프를 트리로 만들 수 있다는 것이다. 이는 어떤 트리가 존재하여, 그 트리의 길이 3인 경로의 양 끝점을 간선으로 잇는 것을 반복하여 완전그래프로 만들 수 있다는 것과 동치이다.

그러한 트리가 존재한다고 가정하자. 트리는 bipartite graph이므로 2-coloring이 존재한다. 이 트리에 간선들이 추가될 때, 추가되는 간선의 양 끝점은 2-coloring에서의 색이 다르다. 따라서, 트리에서 위 방법에 따라 간선을 추가한 이후의 그래프도 bipartite graph이다. 그러나, $N \le 4$이면 $K_n$은 bipartite graph가 아니므로 모순이다.

따라서 답은 $N$이다.

위 문제와 같은 C3인데 난이도 차이가 좀 있는 것 같다. 이 문제가 더 쉬웠다.

1.3. 2005 IMO Shortlist C1 (O)

(Australia) A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for each initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off.

 

풀이

관찰 1. 한 방에 램프 쌍이 존재하면 그 방은 나중에 고려해도 된다.

우선 그 방을 제외한 후 켤 램프를 정한다. 이때 남은 방에 램프 쌍이 두 개 존재한다면 한 쌍은 켜고, 다른 한 쌍은 끄면 된다. 램프 쌍이 하나인 경우, 방에는 세 램프가 있으므로 정해진 램프가 하나 있고, 그 램프와 반대로 램프 쌍을 정하면 된다.

따라서 램프 쌍은 반드시 다른 방에 있다고 가정해도 좋다.

다음과 같이 그래프를 만든다.
* 정점 집합은 각각의 방이다.
* 스위치를 공유하는 램프가 방 $a$와 $b$에 있다면, $a$와 $b$를 잇는 간선이 존재한다.

이렇게 하면 그래프에 0과 1의 숫자를 배정하여 각 정점과 연결된 간선 중 0과 1인 간선이 모두 있도록 하는 문제로 환원할 수 있다.

0이나 1을 임의로 배정했을 때, 조건을 만족하지 않는 정점 $v$가 있다고 하자. $v$에서 시작하는 alternating path를 찾고 반전시키는 것을 반복하면 다른 정점의 상태를 유지하면서 $v$가 조건을 충족하도록 할 수 있다.

찾아보니까 이 문제를 weak 2-coloring이라고도 하는 것 같은데 잘 모르겠다.

https://en.wikipedia.org/wiki/Weak_coloring

Weak coloring - Wikipedia

1.4. 2020 IMO Shortlist C1 (O)

Let $n$ be a positive intger. Find the number of permutations $a_1, a_2, \cdots , a_n$ of the sequence $1, 2, \cdots, n$ satisfying $a_1 \le 2a_2 \le 3a_3 \le \cdots \le na_n$ 
(United Kingdom)

 

풀이

관찰 : $i-1 \le a_i$이다.
$a_i=x$, $x<i-1$이라 하자. $(i-1)a_{i-1} \le ia_i=ix, a_{i-1} \le \frac{ix}{i-1}<x+1$이다. $a_{i-1} \ne x$이므로 $a_{i-1} \le x-1$이다. 따라서 모든 $j\le i$에 대해 $a_j<j$, 모순이다.

비슷하게 $a_i \le i+1$도 보일 수 있다.

$n=k$일때 순열의 가짓수를 $A_k$라 하자. $a_n=n$인 경우와 $a_n=n-1$인 경우가 있고, $a_n=n-1$인 경우 $a_{n-1}=n$이다. 따라서 각각의 경우 $A_{n-1}$, $A_{n-2}$개의 순열이 있다.

따라서 $A_k=A_{k-1}+A_{k-2}$이다.

푼 문제중 제일 쉽게 풀렸다.

1.5. 2001 IMO Shortlist C4 (X)

A set of three nonnegative integers $\{x,y,z\}$ with $x < y < z$ is called historic if $\{z - y,y - x\} = \{1776,2001\}$. Show that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets.

 

뭔가 어려웠었는데 힌트를 보니까 바로 풀렸다.

 

풀이

$a=1776, b=2001$이라 하자.

다음과 같은 그리디 알고리즘을 생각하자.

집합 $A$에 없는 최소의 자연수(0을 포함하여)를 $x$라 하자.

 

• $x$를 $A$에 추가한다.
• $x+a+b$를 $A$에 추가한다.
• $x+a$가 $A$에 없다면 $x+a$를, 아니라면 $x+b$를 추가한다.

위 그리디 알고리즘을 통해 얻어지는 $A$가 문제 조건을 만족한다는 것을 보이자. 모든 수가 한번씩은 추가된다는 것이 자명하므로, 한 수가 두 번 추가되는 일이 없다는 것을 보이면 된다. 위 과정을 반복할 때 추가되는 세 수 중 가장 작은 수들을 순서대로 $x_1, x_2, \cdots$이라 하자. 아래 두 사실을 보이면 된다.

 

1. $x$가 추가될 때, $x+a+b$는 $A$에 없다.

$x+a+b$가 $x_k$와 함께 추가되었다 하자. $x_k, x_k +a, x_k +b, x_k +a+b$ 중 하나는 $x+a+b$일 것이다. 따라서 $x_k \le x$이다. $x_k > x$이면 $x_k$가 추가되었을 시점에 $x$는 $A$에 없으므로, $x_k$가 자신이 추가되었을 시점에서 $A$에 없는 가장 작은 자연수라는 사실에 모순이다. $x_k=x$이면 $x$가 추가될 때 $A$에 이미 $x$가 있으므로 모순이다.

 

2. $x$가 추가될 때, $x+a$가 집합 $A$에 있었다면 $x+b$는 집합 $A$에 없다.

$x+a, x+b$가 모두 $A$에 있다고 하고 귀류법을 사용한다.

어떠한 $k$가 존재하여 $x+b=x_k$, $x+b=x_k+a$, $x+b=x_k+b$, $x+b=x_k+a+b$ 중 하나이다.

 

$x+b=x_k+a+b$라 가정하자. $x_k=x-a$, $x_k$가 추가될 때 $x_k+a=x$가 $A$에 없으므로, $x_k$와 함께 $x$도 $A$에 추가되었어야 한다. 따라서 모순이다.

 

$x+b \le x_k+b$라 가정하자. $x \le x_k$이므로 모순이다.

 

2. PS

할게 많아서 많이 못 했다.

2.1. 과일 게임 (O)

https://www.acmicpc.net/problem/31284

31284번: 과일 게임

 

풀이

일단 하나의 쿼리에 대해 문제를 해결하는 방법을 생각해 보자. 다음과 같은 관찰을 할 수 있다.

 

자연수 $a, b, c$에 대하여 $b, c>a$일때,

1. 배열에 $[b, a, a, \cdots, a, c]$ ($a$가 $2k$개) 형태의 부분배열이 있다면, $[b, a+1, a+1, \cdots, a+1, c]$ ($a+1$이 $k$개) 형태로 바꿀 수 있다.

2. 배열에 $[b, a, a, \cdots, a, c]$ ($a$가 $2k+1$개) 형태의 부분배열이 있다면, $[b, a+1, a+1, \cdots, a+1, \infty, a+1, a+1, \cdots, a+1, c]$ ($a+1$이 각각 $k$개) 형태로 바꿀 수 있다.

 

물론 $\infty$은 답을 셀 때 세지 않는다고 하자.

 

위 연산을 계속 반복하면 배열을 바이토닉하게 바꿀 수 있고, $\infty$가 아닌 수는 $1$ 이상 $O(A + \log N)$ 이하이므로 배열에 등장하는 같은 수 구간들을 다 묶으면 배열의 길이는 $O(A + \log N)$이다.

 

위 과정을 그대로 세그먼트 트리에 담으면 만점을 받을 수 있다. 세그먼트 트리에서의 노드를 합치는 과정은 바이토닉한 수열 두 개를 합치고 위 연산을 반복 실행하는 것인데, 연산은 두 수열이 합쳐지는 부분에서만 실행하면 된다. 따라서 $O(A \log N)$ 시간에 두 노드를 합칠 수 있다. 따라서 전체 시간 복잡도는 $O((N+Q)(A + \log N))$이다.

 

여담으로 std::deque를 쓰면 좀 느리고 덱을 직접 구현해서 쓰거나, std::vector를 써야 빠르다.

2.2. 경찰과 도둑 (O)

https://www.acmicpc.net/problem/31285

31285번: 경찰과 도둑

 

풀이

일단 경찰이 루트에 있는 쿼리만 들어온다고 하자. 우선 도둑의 경우, 최적의 이동 경로는 루트(경찰이 있는 곳) 방향으로 올라간 후, 경찰을 피해 가장 깊은 리프로 도망치는 것이다. 경찰과 도둑의 속도에 따라 두 가지 경우가 있다.

 

1. 경찰이 도둑보다 빠른 경우

도둑이 충분히 많이 위로 올라가지 않는 경우, 올라간 정점에서 반대 방향으로 도망쳤을 때 내려갈 길이가 충분하지 않을 수 있다. 이 경우, 도둑은 리프에 도착한 후 잡힌다.

그러나 반대로 너무 올라간 경우, 리프에 도착하지 못 하였는데도 경찰에게 잡힐 수 있다.

따라서 적당한 지점까지 올라가는 것이 최적이고, 이는 이분 탐색으로 찾을 수 있다.

 

2. 경찰이 도둑보다 느린 경우

1과 다르게, 도둑이 루트 방향으로 올라간 후 항상 리프 노드에 도달할 수 있다. 도둑이 잡히는 유일한 경우는 루트 방향으로 이동하다 경찰과 마주치는 것으로, 경찰에게 잡히지 않고 올라갈 수 있는 가장 위 정점을 이분탐색으로 구하면 된다.

 

sparse table을 사용하면 전체 시간복잡도는 $O((N+Q)\lg N$이다.

 

이제 경찰의 위치가 루트가 아닐 수 있을 때 문제를 해결하자. dfs를 하면서 각 정점에 도착했을 때, 경찰의 위치가 그 정점인 모든 쿼리를 해결하면 된다. 디테일이 좀 복잡하지만, 여기서는 생략한다.