rkm0959

문제

(Graham, Pollak 1972) Prove that the edge set of \(K_n\) cannot be partitioned into the edge-disjoint union of less than \(n-1\) complete bipartite subgraphs. Also, prove that this bound is tight.

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

(증명) \(K_n\)의 각 정점을 \(1, 2, \cdots , n\)이라 하자. 우선 \(n-1\)개의 완전 이분 그래프로 \(K_n\)을 분할하는 것은 쉽다. 

귀류법으로, 완전 이분 그래프 \(B_1 , B_2, \cdots B_m \)이 \(K_n\)을 분할한다고 하자. (단, \(m \le n-2\)다.)

또한, 각 완전 이분 그래프 \(B_k\) 안에서 두 disjoint independent set을 \(L_k, R_k\)라고 부르자.

즉, \(B_k\)의 간선은 \(L_k\)의 정점과 \(R_k\)의 정점 사이를 모두 연결한 것이다.

다음 조건을 만족하도록 \(K_n\)의 정점 \(v\)에 실수 \(x_v\)를 놓자. 

조건 1: 모든 \(1 \le k \le m\)에 대하여, \( \displaystyle \sum_{v \in L_k} x_v = 0 \)이고, \(\displaystyle \sum_{v=1}^n x_v = 0\) 

조건 2: \(\displaystyle \sum_{v=1}^n x^2_v \neq 0 \)이다. 즉, 모든 \(v\)에 대해 \(x_v\)가 전부 \(0\)은 아니다.

이것이 가능함을 보이자. 기초적인 선형대수학을 알면 쉽게 보일 수 있다.

조건 1은 식의 개수가 \(m+1\)개인 하나의 Homogeneous한 연립방정식을 이룬다. 

변수의 개수가 \(n\)개이고 \(m+1 < n\)이므로, 이 연립방정식은 non-trivial 해를 가진다. 

그러므로 조건 1, 2를 만족하도록 정점 \(v\)에 실수 \(x_v\)를 놓을 수 있다. 

이제 \(B_1 , B_2, \cdots B_m \)이 \(K_n\)의 edge set을 완벽하게 분할하므로, 다음 식이 성립한다.

$$ \sum_{1 \le i < j \le n} x_ix_j = \sum_{k=1}^m \left(\displaystyle \sum_{i \in L_k} x_i \right) \cdot  \left(\displaystyle \sum_{j \in R_k} x_j \right) $$

팀: glycine (rkm0959, TAMREF, leejseo) 결과: 8솔브, 4등

스코어보드: https://www.acmicpc.net/contest/scoreboard/346 

입시 공부와 이 대회 참가 사이에서 고민하고 있었는데, 탐레프가 leejseo랑 같이 팀으로 나가자고 해서 나갔다.

결과도 잘 나왔고 대회 자체도 엄청 재밌었다. 물론 3컴에 인터넷도 엄청 썼지만...

각자 코드를 짜서 AC를 받은 문제는 다음과 같다. 문제 순서는 AC 순서.

밑에 문제 이름 옆에 괄호 안에 써놓은 사람은 그 문제를 잡은 사람 목록이다.

rkm0959: G, L, H, F 

TAMREF: J, C, D

leejseo: B

G: 등록 (rkm0959, 1분)

대회 중 풀이: 그냥 출력하면 되는데 팀 계정 기본 언어가 Text여서 한 번 틀렸다. 상큼한 시작.

J: The Chosen Sub Matrix (TAMREF, 28분)

대회 중 풀이: 범위가 작으니, 문제의 조건을 잘 읽고 구현하면 된다. 여러 이유로 3WA.

대회 후 내 풀이: 그냥 구현 문제라 크게 다른 건 없었다. 짜는 방식이 살짝 달랐다.    

L: Weights (rkm0959, 65분)

대회 중 풀이: 생각을 깊게 안하고 코드를 짜고 내다보니 쓸데없이 시간도 오래 걸리고 WA도 2번이나 났다. 

답에 대한 이진탐색이 가능하므로, 이진탐색을 하자. \( x \)개의 weight를 올리는 것이 가능한지 판별하고 싶다면, 당연히 가장 무게가 작은 \(x\)개의 weight들을 올릴 수 있는 지만 확인하면 된다. 이제 그리디하게 weight를 올리자.

durability가 큰 컨테이너 순으로 다음 시행을 한다.

올릴 수 있는 가장 무거운 weight를 컨테이너에 올려주는 것을 반복 

이 방식으로 모든 weight를 올릴 수 없으면, \( x \)개의 weight를 올리는 것은 불가능하다. 

또한, 주어진 배수 조건 때문에 서로 다른 weight 종류 개수는 \(\mathcal{O}(\log W)\)이다. 

이 두 가지 관찰을 하면 문제를 해결하는 것은 간단하다. 주어진 input을 정렬하고 weight의 종류/개수를 전처리를 하자.  

이제 결정문제를 쉽게 \(\mathcal{O}(N \log W)\)에 해결할 수 있고, 전체 문제도 제한 시간 안에 풀 수 있다.

이런 문제가 어떻게 8분 컷이 될까 싶다 ㅋㅋ

C: Cross Spider (TAMREF and leejseo, 68분)

대회 중 풀이: 모든 점이 한 평면 위에 있는지 판별하는 문제다. \( N \le 3 \)일 때는 당연히 참이고, \(N \ge 4\)를 보자. 

일직선 위에 있지 않은 세 점은 한 평면을 이루니까, 이 평면 위에 모든 점이 있으면 충분하다.

네 점의 Coplanarity는 벡터의 외적/내적을 활용하여 \( \mathcal{O}(1)\)시간에 판별할 수 있다. 

이걸로 \(\mathcal{O}(N) \) 풀이가 완성된다. overflow에 주의할 필요가 있다. 어쩌다보니 7WA;;

대회 후 내 풀이: '일직선 위에 있지 않은'을 빼먹어서 한 3WA 정도 한 것 같다. 극혐.    

D: Gophers (TAMREF and leejseo, 152분)

대회 중 풀이: 각 CD가 영향을 줄 수 있는 길이가 동일하므로, 각 CD가 '독점적으로 영향력을 발휘하는 영역'은 선분이다. 

그래서 이 구간을 구해주면서 그 구간에 속하는 구멍의 개수를 더하고 빼면서 쿼리에 답하면 된다. 

대회 중에는 OSRank와 펜윅을 써서 2928ms 뚝딱 AC. 사실 펜윅을 쓸 필요는 없다. (OSRank도 쓸 필요 없다. ㅋㅋ!)

대회 후 내 풀이: 독점구간 및 그 구간에 속하는 구멍 개수는 set을 사용하면 쉽게 계산 가능. lower/upper bound 쓰자.

H: Store-Keeper (rkm0959, 221분)

대회 중 풀이: http://www.usaco.org/index.php?page=viewproblem2&cpid=769 이 문제가 상당한 도움이 된다.

bfs를 돌려야 할 것 같은 문제인데, 상태를 (내 위치, 박스 위치)로 두면 상태 개수가 저세상으로 간다. 

그러니까 상태를 (박스 위치, 박스 기준으로 내가 있는 방향 - U/D/L/R)로 두자. 이러면 상태 개수가 \( \mathcal{O} (NM) \)이다.  

가능한 행동은 둘 중 하나다. 내가 있는 곳에서 박스를 밀어 움직이거나, 다른 방향에서 박스를 밀기 위해 내가 움직이는 것이다. 첫 번째 행동은 박스를 밀 수 있는지를 판별하는 게 \( \mathcal{O}(1)\)에 되니 문제 없다.

두 번째 행동은 조금 까다로운데, 내가 한 위치에서 다른 위치로 움직일 수 있는지를 판별해야 하기 때문이다.

이 과정에서 flood-fill을 하는 등의 방법을 쓰면 \( \mathcal{O}(N^2M^2)\) 풀이가 나온다. 

잘 짜여진 \( \mathcal{O}(N^2M^2)\)는 실제로 AC를 받았지만, 그렇지 않으면 TLE가 뜬다고 한다. 

시간을 줄이려면 두 번째 행동이 가능한지 여부를 빠르게 판별할 수 있는 방법을 찾아야 한다.

여기서 biconnected component를 떠올릴 수 있다. grid를 그래프로 보고, biconnected component를 구하자. 

grid의 각 칸이 (즉 그래프의 각 노드) 속한 biconnected component를 set 등으로 모두 저장하자.

각 칸이 속한 biconnected component의 개수는 최대 4개니까 (why?) set을 써도 큰 문제는 없다. 

이제 처음 위치와 끝 위치가 같은 biconnected component에 속하는 지 여부를 확인하여, 두 번째 행동이 가능한 지 불가능한 지 판별할 수 있다. 이 판별은 앞선 관찰에 의해 \( \mathcal{O}(1) \)에 가능하다. 이제 bfs를 그대로 돌리면 문제가 \( \mathcal{O}(NM) \)에 풀린다. 

Tarjan BCC를 처음 써봤다. 많은 것을 배울 수 있었던 문제. 위에 저 USACO 문제도 풀어봐야 할 듯.

F: Laundry (rkm0959, 244분)

대회 중 풀이: \(i\)번째 오는 사람은 \(2d_i\)개 양말용 빨래집게, \(3d_i\)개 셔츠용 빨래집게가 필요하다. 

이 문제는 그리디로 풀 수 있는 문제다. \(d_i\)가 큰 사람 순서로, 다음과 같이 집게 색깔을 고르자.

1. 집게가 \(5d_i\)개 이상 있는 색깔이 있으면, 그 중 집게 개수가 가장 작은 색깔을 골라 양말/셔츠용으로 한다.

2. 1이 실패했다면, 집게가 \(3d_i\)개 이상 있는 색깔 중 집게 개수가 가장 작은 색깔을 골라 셔츠용으로 한다.

3. 1이 실패했다면, 집게가 \(2d_i\)개 이상 있는 색깔 중 집게 개수가 가장 작은 색깔을 골라 양말용으로 한다.

이렇게 해서 색깔 분배가 가능한 지 확인하면 된다. set과 lower/upper bound를 쓰면 쉽게 구현할 수 있다. \( \mathcal{O}(N \log N) \).

B: Bytean Road Race (leejseo, rkm0959, 283분)

대회 중 풀이: leejseo와 내가 각자 맞는 풀이를 발견했고, 각자 짜서 냈다. 내 코드는 틀렸고, leejseo가 맞았다. 갓...

leejseo의 풀이는 https://en.wikipedia.org/wiki/Reachability#Kameda's_Algorithm을 쓴다. 

간단하게 설명하면, 주어진 그래프에서 reachability는 하나의 partial order와 같다. 

그런데 dfs를 2번 '잘' 하면, dfs에서 정점이 label된 순서를 통하여 reachability의 partial order를 얻을 수 있다!   

https://www.sciencedirect.com/science/article/pii/0020019075900198?via%3Dihub 참고. 

알고리즘이 선형이라서 진짜 개빠르다 ㄹㅇ;;; 대신 대회장에서 생각하기는 좀 어려운 풀이인듯 싶다.

대회 중 풀이/대회 후 내 풀이: 풀이를 설명하기 위해 먼저 정의를 하나 내리자.

Definition: 정점 \(v\)에 대하여, 경로 \(DP(v)\)와 \(RP(v)\)를 다음과 같이 정의하자. 

\(DP(v)\): \(v\)에서 시작해 아래쪽으로 갈 수 있을 때는 아래쪽으로 이동하고, 아니면 오른쪽으로 이동하여 \(n\)에 도착하는 경로. 

\(RP(v)\): \(v\)에서 시작해 오른쪽으로 갈 수 있을 때는 오른쪽으로 이동하고, 아니면 아래쪽으로 이동하여 \(n\)에 도착하는 경로. 

또한, 정점 \(v\)에 대하여, 정점 \(DPnext(v)\)와 \(RPnext(v)\)를 다음과 같이 정의하자. 

\(DPnext(v)\): 경로 \(DP(v)\)에서 \(v\) 다음으로 방문하는 정점. 편의상 \(DPnext(n)=n\)으로 둔다.

\(RPnext(v)\): 경로 \(RP(v)\)에서 \(v\) 다음으로 방문하는 정점. 편의상 \(RPnext(n)=n\)으로 둔다.

풀이의 핵심은 다음 관찰이다. 

Claim 1: 두 정점 \(u, v\)가 있다. 이때, 다음 두 명제는 동치다.

명제 1: \(u\)에서 \(v\)로 갈 수 있는 경로가 존재한다. 

명제 2: \(v\)는 \(DP(u)\)와 \(RP(u)\) 사이에 존재한다.

이 Claim은 \(1\)번 정점에서 모든 점에 도달할 수 있고, 모든 점에서 \(n\)번 정점에 도달할 수 있다는 문제 조건에 의해 성립한다. 

직관적으로 이해하기 쉬운 Claim으로, 그 증명 자체도 크게 어렵지 않을 것으로 예상한다. 

이제 명제 2가 참인지 거짓인지를 어떻게 빠르게 판별할 지 생각해보자. 다시 두 가지 관찰을 해야 한다.

Claim 2: 앞선 Claim 1에서의 명제 2는 다음 명제 3와 동치다. 

명제 3: \(DP(u)\)에서 처음으로 \(y\)좌표가 \(v\)의 \(y\)좌표보다 작거나 같은 점을 \(w_1\)이라 하자.

또한, \(RP(u)\)에서 처음으로 \(x\)좌표가 \(v\)의 \(x\)좌표보다 크거나 같은 점을 \(w_2\)이라 하자.

이때, \(w_1\)의 \(x\)좌표는 \(v\)의 \(x\)좌표보다 작거나 같고, \(w_2\)의 \(y\)좌표는 \(v\)의 \(y\)좌표보다 크거나 같다. 

Claim 3: \(DP(u)\)는 \(u\) 뒤에 \(DP(DPnext(u))\)를 붙인 것이다. \(RP(u)\)도 마찬가지.

두 Claim 다 직관적으로 이해하기 쉽고 자명하다. 경로 위에서 \(x, y\) 좌표는 모두 단조적이므로, Claim 2와 이진탐색을 섞으면 명제 2가 참인지 거짓인지를 판별할 수 있을 것 같다! 실제로 이는 가능하다.

이진탐색을 떠올리면 남은 것은 \(DP(u)\)에서 \(k\)번째 정점을 빠르게 구하는 방법을 찾는 것이다.

Claim 3에서 나온 관찰에서, Sparse Table을 사용할 수 있음을 파악할 수 있다.

자세한 설명은 고려대학교 2017 경시 Line Friends 참고. http://koosaga.com/206에 잘 설명되어 있다.

이제 이진탐색 대신 LCA를 구하는 방법처럼 binary lifting을 하여 명제 3이 성립하는지 확인할 수 있다. 

대회에서는 binary lifting 부분에서 케이스 하나를 놓쳐서 틀렸다. 시간복잡도는 \( \mathcal{O}((N+Q)\log N)\)이다.

문제

\( a_1, a_2, \cdots a_n \)은 \( a_1 a_2 \cdots a_n = 1 \)과 \( 0<a_1 \le a_2 \cdots \le a_n \)을 만족하는 실수들이다.

각 \( 1 \le k \le n \)에 대하여, \( b_k = 2^k (1+a^{2^k}_k) \)라고 정의하자. 이때 다음 부등식이 성립함을 보여라.

$$ \sum_{i=1}^n \frac{1}{b_i} \ge \frac{1}{2} - \frac{1}{2^{n+1}} $$

스포 방지선

_______________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

많은 학생들이 삽질을 했고, 일부가 아주 복잡한 테크닉을 활용해서 힘겹게 푼 문제다. 준-보스 문제.

나는 이 문제를 당시에 아주 깔끔하게 풀었는데, 지금 생각해보면 이거 덕분에 점수를 좀 딴 것 같다.

(증명) 일단 다음 Lemma를 먼저 증명한다. 

(Lemma) \( x, y \)는 \( 0< x \le 1, y>0 \)을 만족하는 실수들이다. 이때 다음 부등식이 성립한다.

$$ \frac{1}{2(1+x)} + \frac{1}{4(1+y)} \ge \frac{1}{4} + \frac{1}{4(1+x^2y)} $$

(Proof of Lemma) 항을 적당히 묶어주면서 계산하자. 

$$ \frac{1}{2(1+x)} + \frac{1}{4(1+y)} \ge \frac{1}{4} + \frac{1}{4(1+x^2y)} $$

$$ \iff \frac{1}{2(1+x)} - \frac{1}{4} \ge \frac{1}{4(1+x^2y)} - \frac{1}{4(1+y)} $$

$$ \iff \frac{1-x}{1+x} \ge \frac{(1-x^2)y}{(1+y)(1+x^2y)} \iff (1+y)(1+x^2y) \ge (1+x)^2y$$

$$ \iff 1+x^2y + y+x^2y^2 \ge y+2xy+x^2y \iff (xy-1)^2 \ge 0$$

등호 성립은 보다시피 \( x=1 \) 또는 \( xy=1 \)에서 이루어진다. 

본 문제로 돌아오자. \(n \)에 대한 귀납법으로 문제를 해결한다. \( n=1 \)은 자명.

\( n=2 \)인 경우는 Lemma에 \( x=a^2_1, y=a^4_2 \)를 넣어주면 바로 성립함을 확인할 수 있다.

이때, 등호 성립 조건은 Lemma와 문제에서 주어진 조건에 의해 \( a_1 = a_2 = 1 \)이다. 

이제 귀납법을 적용해보자. 엄밀한 귀납 서술은 생략한다. 

\( a_1 a_2 \cdots a_n = 1 \)과 \( 0<a_1 \le a_2 \cdots \le a_n \)를 만족하는 \( a_1, a_2, \cdots a_n \)를 잡자. 

이제, \( c_1=a^2_1a^2_2 \), \(c_2=a^2_3 \), \(c_3 = a^2_4 , \cdots ,c_{n-1} = a^2_n \)로 새로운 변수를 두자.

Fact. \( 0<c_1 \le c_2 \le \cdots \le c_{n-1} \)이고, \( c_1c_2 \cdots c_{n-1} = 1 \)이다. 

첫 번째 사실은 \( a_1 \le 1\)과 \(a_i \le a_{i+1} \)에서 자명하고, 두 번째 사실은 자명하다.

즉, \( c_i\)들을 가지고 (\(n\)이 하나 줄었으니) 귀납 가정을 사용할 수 있다. 여기서 우리는 

$$ \frac{1}{2(1+a^4_1a^4_2)} + \frac{1}{4(1+a^8_3)} + \cdots \frac{1}{2^{n-1}(1+a^{2^n}_n)} = \sum_{k=1}^{n-1} \frac{1}{2^k(1+c^{2^k}_k)} \ge \frac{1}{2}-\frac{1}{2^n} $$를 얻는다. 이제 \( x= a^2_1, y=a^4_2 \)에 대하여 Lemma를 적용시켜주면, 

$$ \sum_{i=1}^n \frac{1}{b_i} = \frac{1}{2(1+a^2_1)} + \frac{1}{4(1+a^4_2)} + \sum_{k=3}^n \frac{1}{2^k(1+a^{2^k}_k)} $$

$$ \ge \frac{1}{4} + \frac{1}{4(1+a^4_1a^4_2)} + \sum_{k=3}^n \frac{1}{2^k(1+a^{2^k}_k)} \ge \frac{1}{4} + \frac{1}{2} \left( \frac{1}{2} - \frac{1}{2^n} \right) = \frac{1}{2} - \frac{1}{2^{n+1}} $$

등호 성립 조건은 \( a_1 = a_2 = \cdots a_n = 1 \)인 경우이고, 이 경우 밖에 없음을 귀납적으로 보일 수 있다.

스케치만 하자면, \( (a_1, a_2, \cdots a_n) \)에서 등호가 성립하면 \( (a^2_1a^2_2, a^2_3, \cdots a^2_n) \)에서도 등호가 성립하고, 귀납적으로 \( a_1a_2=a_3= \cdots = a_n=1 \)임을 알 수 있다. 이제 Lemma에서의 등호 성립 조건에 의하여 \( a_1=a_2=1 \)를 얻는다. 

초기 조건은 (\(n=1,2\)) 앞에서 했으니 증명이 끝난다. 이에 이 문제에 대한 증명이 끝난다. \( \blacksquare \) 

\( \LaTeX \) 테스트를 먼저 조금 해보려고 한다.

사실 미리보기에서만 잘 나오고 글을 쓰면 잘 안 나와서 멘탈이 터졌는데, king god @subinium님이 해결해주셨다.

$$ \sum_{i=1}^n \tau (n) = \sum_{a \le \sqrt{n}} \sum_{b \le \frac{n}{a}} 1 + \sum_{b \le \sqrt{n}} \sum_{a \le \frac{n}{b}} 1 -\sum_{a \le \sqrt{n} } \sum_{b \le \sqrt{n}} 1$$

$$= 2\sum_{a \le \sqrt{n}} (\frac{n}{a} + O(1)) - (\sum_{a \le \sqrt{n}} 1)^2= 2n \sum_{a \le \sqrt{n}} \frac{1}{a} + O(\sum_{a \le \sqrt{n}} 1) - (\sqrt{n}+O(1))^2$$

$$= 2n(\log \sqrt{n} + \gamma + O(\frac{1}{\sqrt{n}})) + O(\sqrt{n}) - n-O(\sqrt{n})+O(1) = n\log n +(2\gamma -1)n + O(\sqrt{n})$$

TODO

이 블로그에서 하고 싶은 거를 먼저 간단하게 정리한다. 

1. 경시 수학 - KMO 하면서 풀었던 진짜 좋은 문제들, 최근에 나온 좋은 문제 등등을 소개하고자 함

2. 해석학 - 입시 끝나고 Rudin (PMA) 해석학을 돌 생각인데, 내용 정리/연습문제 풀이를 진행하고자 함

3. 기타 재밌는 것들 - 재밌는 정리들을 소개하고자 함. 위 두 항목에 들어오지 않는 수학 포스트는 다 여기에 넣을 듯 싶음

4. 수학 계열 PS - PS에서 가끔 나오는 수학과 (특히 정수론) 관련된 다양한 알고리즘을 소개하고 이를 활용해 문제를 풀고자 함.

여기서는 Project Euler 문제, BOJ 문제, Codeforces 문제 등 다양한 곳에서 출제된 수학 알고리즘 문제를 풀고자 함.

5. Problem Solving - "진짜" PS를 여기서 하고자 함. 내가 자료구조를 진짜 더럽게 못하니까 자료구조 공부도 좀 하고...

6. 대회 후기 - 대회를 치거나 대회를 검수하거나 대회를 출제하거나 등등 일이 있을 때 여기서 후기를 쓰고자 함.

7. 기타 - 게임 얘기, 잡담, 여행 얘기, 테스트 글 등등을 넣으려고 한다. 

특히 지금 쓰고 싶은 글은

1. 피타고라스 쌍 (BOJ 16123) - 레시테이션 (BOJ 16141) - Mobius Madness (BOJ 16164) 설명

2. 정사각형 만들기 (BOJ 10803) 증명, Szemeredi-Trotter 정리 관련 포스트 다시 깔끔하게 쓰기

3. 좋은 수올 문제 몇 개 가져오고 풀이

4. 지금까지 동아리에 낸 모의면접 문제 소개 및 풀이

5. Project Euler 문제 어려운 거 몇 개 풀이

정도인데, 이걸 보면 내가 "진짜" PS를 얼마나 안 했는지 볼 수 있다. ㅋㅋ 백준은 꽤 한 것 같은데 다 수학이냐 ㅋㅋ 에휴...