rkm0959

NYPC 2018 본선이 10월 27일 있었다. 결과는 5등으로, 동상을 받았다. 예상보다 성적이 잘 나온 것 같다 ㅋㅋ

올해 정올 본선을 걸렀고, 작년 NYPC에서는 아깝게 동상을 못 받아서 올해 NYPC에서 상을 꼭 타고 싶었는데, 기분이 좋다. 

작년에는 없었던 100만원 장학금도 받았고, 부상으로 LG 그램 노트북을 받았다. 대학교에 가면 쓰게 될 것 같다.

간략한 문제 설명과 Subtask 설명을 쓰고, 내가 시험을 친 과정을 적는다. 오류가 있다면 지적 대환영 :) 

________________________________________________________________________________________________________________________

문제

1. \( 1 \le N \le 5000 \)과  \(1 \le W \le 10^9 \)이 주어진다. 

또한, 서로 다른 자연수 \( 1 \le A_1, A_2, \cdots A_n \le 10^9\)이 주어진다. 

이때, \(i<j<k\)이고 \(A_i+A_j+A_k=W\)를 만족하는 순서쌍 \((i,j,k)\)의 개수를 구하시오. 

제한시간 1초, 배점 100

Subtask 1. \(N \le 300\) 

Subtask 2. \(W \le 3 \cdot 10^6\)

Subtask 3. 추가 제한 없음

2. 실수 \( 1 \le L \le 100\)이 주어진다. \(xy\) 평면 위에 길이가 \(L\)인 막대기가 두 개 있다. 또한, \(x=0\)과 \(x=2L\)에 벽이 있다. 

처음에 두 막대기는 벽 \(x=0\), \(x=2L\)에 각각 붙어있다. 

즉, 한 막대기는 양 끝점이 \((0,0), (0,L)\)이고, 다른 막대기는 양 끝점이 \((2L,0),(2L,L)\)이다.

이제 두 막대기가 한 끝점은 벽 위에 있는 상태로 미끄러져 내려온다. 최종 상태에서는 두 막대기가 \((L,0)\)에서 만난다.

이제 한 점 \((x,y)\)가 주어진다. 두 막대기가 미끄러져 내려오는 과정에서, \((x,y)\)가 막대기와 만나는 지 여부를 판별하시오.    

제한시간 1초, 배점 100

Subtask 없음. 

3. 파일로 주어진 input 10개에 대해, output을 뽑아 점수를 얻는 Output Only 문제이다.

자연수 \(1 \le N, M \le 30, 1 \le C \le 3, V\)가 주어진다. 

그 후, 각 격자가 \(1, 2, \cdots C\)번의 색깔 중 하나로 색칠되어 있는 \(N \times M\) 직사각형이 주어진다. 

각 행은 1번부터 \(N\)번까지 순서대로 번호가 붙어있고, 열도 마찬가지로 1번부터 \(M\)번까지 번호가 붙어있다.

다음 조건을 만족하는 \(T\)와, \(r_{1,i}, c_{1,i}, r_{2,i}, c_{2,i}, color_i\) \((1 \le i \le T)\)를 출력하시오. 

단, \(1 \le r_{1,i} \le r_{2,i} \le N\), \(1 \le c_{1,i} \le c_{2,i} \le M\), \(1 \le color_i \le C\)를 만족해야 한다.

조건: 색칠이 되어있지 않은 \(N \times M \) 직사각형이 있다. 

각 행은 1번부터 \(N\)번까지 순서대로 번호가 붙어있고, 열도 마찬가지로 1번부터 \(M\)번까지 번호가 붙어있다.

각 \(1 \le i \le T\)에 대하여, 직사각형 \([r_{1,i}, r_{2,i}] \times [c_{1,i}, c_{2,i}]\)에 속한 격자의 색깔을 \(color_i\)로 바꾼다.

이때, 얻어진 결과물이 입력에서 주어진 \(N \times M\)의 직사각형과 동일하다. 

Input은 총 10개고, 각각에서 얻을 수 있는 최대 점수는 10점이다. 점수는 다음과 같이 계산된다.

1. 우선 출력된 결과물이 조건에 맞지 않으면, 0점이다.

2. \(T < V\)이면 10점이고, \(T \ge N \cdot M \)이면 1점이다.

3. 그 외의 경우, \(10 - 9 \cdot \frac{T-V}{NM-V} \)점을 부여한다. 

데이터 1, 2: \(N=1\) 랜덤 데이터. 데이터 1은 \(C=2\), 데이터 2는 \(C=3\). \(V\)는 최적의 \(T\)값 + 1으로 주어짐.

데이터 3, 4: \(N, M\)이 작은 랜덤 데이터. 데이터 3은 \(C=2\), 데이터 4는 \(C=3\). \(V\)는 최적의 \(T\)값 + 1으로 주어짐.

데이터 5, 6: 직사각형 전체를 한 색으로 칠하고, 랜덤한 직사각형 \(V-1\)개를 골라 색칠하여 만들어진 데이터.

데이터 5는 \(C=2\), 데이터 6은 \(C=3\)으로, 두 데이터 모두 \(N, M\)이 20 이상으로 크다. 

데이터 7, 8: \(N=M=30\)인 랜덤 데이터. 데이터 7은 \(C=2\), 데이터 8은 \(C=3\). \(V = NM \cdot \frac{C-1}{C}\).

데이터 9, 10: \(N=M=30\)인 랜덤 데이터. 데이터 7은 \(C=2\), 데이터 8은 \(C=3\). \(V = NM \cdot \frac{C-1}{2C}\).

4. 자연수 \(1 \le N, M \le 1000\)이 주어진다. 

\(N \cdot M\) 격자로 이루어진 공간이 있는데, 이 중 일부 격자는 지나갈 수 없는 격자이다. 

단, 지나갈 수 없는 격자들은 상하좌우로 인접한 것은 연결되어 있다고 하면, 하나의 컴포넌트로 연결되어 있다.

또한, \(N \cdot M\) 격자로 이루어진 공간에서 가장 바깥쪽 행/열들은 모두 지나갈 수 없는 격자이다.

각 행은 1번부터 \(N\)번까지 순서대로 번호가 붙어있고, 열도 마찬가지로 1번부터 \(M\)번까지 번호가 붙어있다.

이제 \(1 \le Q \le 2 \cdot 10^5\)개의 쿼리가 주어진다. 

각 쿼리는 두 점 \((sy,sx)\), \((ey,ex)\)으로 이루어지며, 두 점 사이의 최단 경로의 거리를 답해야 한다. 

단, 경로가 존재하지 않는 경우에는 -1을 출력하면 된다. \(Q\)개의 쿼리에 모두 답하시오. 

시간제한 2초, 배점 100

Subtask 1. (19점) \(N, M, Q \le 300\)

Subtask 2. (21점) \(N \le 4\)

Subtask 3. (26점) \(M=2k+1\)로 홀수이다. 주어지는 공간은 다음 조건들을 만족한다.

조건 1. \((2,k+1), (3,k+1), \cdots (N-1,k+1)\)은 모두 지나갈 수 있는 격자들이다. 

조건 2. \((u,v)\)가 지나갈 수 있는 격자이면, 임의의 자연수 \(v' \in [v,k+1]\)에 대하여 \((u,v')\)도 지나갈 수 있는 격자이다. 

Subtask 4. (34점) 추가 제한 없음. 

5. \(1 \le N \le 10^5\)개의 울타리가 있다. 

각 울타리는 \(xy\) 평면 위의 서로 다른 두 격자점을 잇는 선분 형태로 주어진다. 

이때, 울타리의 양 끝점에 해당되는 격자점의 \(x, y\) 좌표는 \(-10^9\) 이상 \(10^9\) 이하이다. 

한편, 각 울타리의 양 끝점에는 말뚝이 박혀있다. 또한, 각 울타리는 양 끝점이 아닌 점에서 서로 교차하지 않는다. 

마지막으로 울타리 위에 있지 않는 두 점 \(S, T\)가 주어진다. 

\(S, T\)를 연결하고, 말뚝을 통과하지 않는 곡선을 긋되, 그 곡선이 울타리와 교차하는 횟수를 최소화하고자 한다.

이 최소값을 구하시오. 단, \(S, T\)는 울타리 위에 있는 점이 아니고, 말뚝이 박힌 위치도 아님이 보장된다.

시간제한 2초, 배점 100

Subtask 1. (27점) 모든 말뚝은 정확하게 두 울타리와 연결되어 있다. 

Subtask 2. (41점) 임의의 두 말뚝은 울타리를 통하여 연결되어 있다. 

Subtask 3. (32점) 추가 제한 없음.

________________________________________________________________________________________________________________________

대회 진행

일단 대회가 시작하자마자 1번을 열었고, 워낙 전형적인 문제라 바로 코드 작성을 시작했다. 

std::set이나 map 등을 쓰고 싶은 마음이 좀 컸는데, TLE가 뜰 것 같아서 그냥 이진탐색을 짰다.

나중에 들어보니 set/map 쓰고 TLE를 한 번 낸 분이 있었다. 이진탐색 짜는 판단은 잘 한듯.

아직도 이유를 잘 모르겠는 RTE를 한 번 받은 뒤 무난하게 1번을 AC 맞았다. 이때가 시작 후 8분 정도.

그 후 2번을 열었는데, 왜 이 문제가 입시 대비 수학 프린트가 아니라 NYPC에 있는 지 의문이 들었다.  

이거 https://en.wikipedia.org/wiki/Astroid 아님? 그래서 유도도 하지 않고 저 식을 바로 짰다.

pow 함수를 쓰려다가 좀 쫄려서 이진탐색을 돌렸다. 실수오차도 좀 쫄렸지만 바로 AC.

이때 시계를 보니 16분 정도 지났었다. 2번을 빠르게 밀어서 기분이 아주 좋았다. 벌써 유리해진 느낌.

3번을 열어보니 output only 문제였다. 조금 걱정이 앞섰지만, 문제를 읽어보니 풀 수 있을 것 같았다.

만점을 받으려면 핵심 관찰이 하나 쯤은 필요하지 않을까 싶어서 한 30분 정도 고민했는데, 별로 소득이 없었다. 

그래서 우선 긁기로 했다. 먼저 앞에 있는 4가지의 데이터 중 1, 3, 4번은 그냥 손으로 풀어 제출해서 맞았다.  

2번은 손으로 푸는 것과 프로그램을 짜는 것을 섞어서 풀었는데, 그냥 손으로 푸는 게 빨랐을 것 같다. 

5번, 6번을 풀기 위해 데이터를 다운받았는데, 다운받고 보니 그림이 생각보다 간단했다. 

단순 그리디로도 이 두 데이터에서는 만점을 받을 수 있을 것 같아, 다음과 같은 그리디를 고안한 후 짰다. 

Greedy Algorithm 1 (for #3)

1. 먼저 모든 격자를 색깔 \(x\)로 칠한다.

2. 이제부터 색깔 \(x+1\)과 (\(C=3\)인 경우) \(x+2\)만을 사용한다. 

3. 이제부터 \(x\)가 아닌 색깔로 칠해진 격자는 다시 칠할 수 없다고 가정한다. 

4. 색칠할 수 있는 직사각형 중 가장 큰 직사각형을 색칠하는 것을 반복한다. 

모든 색깔 index는 적당한 mod를 취해서 보고, \(x\)는 알고리즘을 돌리기 전에 \(1, 2, 3\) 중 하나를 선택한다. 

진짜 어마어마하게 비효율적인 알고리즘인데도 5, 6번에서 만점이 나왔다. 조금 예상 밖이었다.  

그래서 7, 8, 9, 10번 데이터를 다운받고 이 알고리즘을 돌려봤는데, 점수가 예상보다 심하게 높게 나왔다. 

7, 8, 9번 데이터에서 10점을 받고 마지막 데이터 10번에서만 9.3점으로, 총 99.3점을 받았다. 

이 시점에서 나는 이 문제에서 \(99 + \epsilon\)점을 받은 사람이 수두룩 할 것 같았다. 

그래서 이 문제에서 \(100\)을 받아야 안정적으로 동상을 받을 수 있다고 판단했다. 

이때가 아마 1시간 40분 정도 지났을 시점이었다. 관찰 찾는다고 시간 더 썼으면 많이 말렸을 것 같다. 

\(100\)점을 지금 바로 노리면 말릴 게 뻔했고, 4, 5번을 읽어보니 긁는 게 엄청 어렵지는 않을 것 같았다. 

그래서 바로 4번을 열었다. \(Q\)가 20만인 걸 보고 온갖 생각이 다 들었다. 100점 풀이가 가능은 할까?

쿼리를 오프라인으로 답하는 방법을 찾거나, 한 쿼리당 로그로 풀라는 건데, 이게 어떻게 가능할까? 

지나갈 수 없는 격자가 연결되어 있다는 게 뭔 도움이 될까? 문제가 일단 좀 신기했다. 

일단 100점 풀이를 바로 구상하다가는 망할 것 같았고, 풀이가 뻔한 Subtask 1, 2를 짜고 Subtask 3을 고민하기로 결정했다. 

Subtask 1, 2는 그냥 bfs를 돌리면 쉽게 긁을 수 있는 Subtask였고, 구현 실수 2번 끝에 다 맞을 수 있었다. 

Subtask 3은 좀 고민해보니 풀이가 빠르게 나왔다. 직관을 천천히 따라가다 보니 풀이가 바로 나왔다.  

두 점이 대칭축을 기준으로 서로 반대쪽에 있거나, 한 점이 대칭축 위에 있으면 답은 그냥 택시거리다.

결국 두 점이 대칭축을 기준으로 같은쪽에 있는 경우가 중요하다. 

쿼리가 들어온 두 점을 \( (sy, sx)\), \( (ey,ex)\)라 하자. 일반성을 잃지 않고 \(sy \le ey\)와 \(sx, ex \le k\)를 가정하자.

\( (sy, sx) \), \( (ey,ex)\)를 잇는 임의의 경로 \(P\)를 잡고, \(P\)에 속한 격자의 \(x\)좌표의 최댓값을 \(X\)라 하자. 

관찰 1. 조건 1에 의해 중심축이 전부 사용 가능한 격자로 구성되어 있으므로, \(X \le k+1\)만 고려해도 충분하다.

관찰 2. \(X \ge \text{max}(sx,ex)\)이고, \(\text{length}(P) \ge |ey-sy|+|X-ex|+|X-sx| \)이다. 

관찰 3. 조건 2에 의해 \((sy, X), (sy+1,X), \cdots (ey,X)\)는 모두 사용 가능한 격자여야 한다. 

관찰 4. 그냥 \((sy, sx) \rightarrow (sy,X) \rightarrow (ey,X) \rightarrow (ey,ex)\)로 가는 경로를 \(P'\)이라 하면 \(\text{length}(P') = |ey-sy|+|X-ex|+|X-sx| \)이다.

관찰 5. 즉, \((sy, sx) \rightarrow (sy,X) \rightarrow (ey,X) \rightarrow (ey,ex)\) 꼴 경로만 봐도 무방하다.

관찰 6. \(X \ge \text{max}(sx,ex)\)면 \(|ey-sy|+|X-ex|+|X-sx|\)는 \(X\)에 대한 증가함수다. 

관찰 7. 조건 2에 의해, \(X<X' \le k+1\)에 대하여 \((sy, sx) \rightarrow (sy,X) \rightarrow (ey,X) \rightarrow (ey,ex)\)가 가능한 경로면, \((sy, sx) \rightarrow (sy,X') \rightarrow (ey,X') \rightarrow (ey,ex)\)도 가능한 경로이다. 

관찰 8. \((sy, sx) \rightarrow (sy,X) \rightarrow (ey,X) \rightarrow (ey,ex)\) 꼴 경로가 가능한 최소의 \( X \ge \text{max}(sx,ex) \)를 찾으면, 답은 \(|ey-sy|+|X-ex|+|X-sx|\)가 된다. 

관찰 9. 이러한 최소의 \(X\)는 이진탐색을 통해 찾을 수 있는 형태이다.

관찰 10. 간단한 전처리를 통해 결정문제를 \(\mathcal{O}(1)\)에 해결할 수 있다. 

이렇게 하면 시간복잡도 \(\mathcal{O}(NM+Q\log M)\)에 Subtask 3를 풀 수 있다. 총 66점. 

여기까지 하고 일단 5번으로 넘어갔다. 이때가 시험 시작 후 약 2시간 30분 정도 지난 후였다. 

5번은 문제를 읽자마자 dual graph를 생성하면 끝나는 문제임을 파악했다. 문제는 내가 이걸 짤 줄 모른다.

좀 생각해보니 Subtask 2부터는 dual graph를 짤 줄 모르면 절대 못 풀 것 같았고, 그냥 Subtask 1만 긁기로 했다.

Subtask 1에서는 모든 연결 컴포넌트가 하나의 cycle - 즉, 다각형을 이룬다.  

결국 주어진 두 점 \(S, T\)가 다각형 안에 포함되어 있는지를 선형 언저리 시간에 확인하는 문제로 환원된다. 

이 문제가 풀리면, 두 점 중 하나만 포함하는 다각형의 개수를 세면 답이 되기 때문이다. 이유는 자명.

맨 처음에는 모든 다각형이 볼록이겠거니 싶어서 바로 ccw를 꺼낼 준비를 하고 있었는데, 당연히 아니었다. 

그래서 다각형 내부 판별을 어떻게 할 지 고민을 상당히 오래했다. ccw를 활용하려고 했는데 도저히 길이 없었다. 

결국에는 판별 대상인 점을 지나는 직선 하나를 긋고, 그 직선과 다각형의 변들 사이의 교점을 보는 방식으로 접근했다.   

직선을 그으면, 그 직선은 다각형으로 들어갔다가, 나갔다가, 들어갔다가, 나갔다를 반복한다. 

그러므로 판별 대상 점이 직선 위에서 어느 두 교점 사이에 속하는 지를 찾으면, 다각형 내부 여부를 판별할 수 있다.

직선이 변과 평행하거나 말뚝을 지나게 되면 많이 피곤해진다. 잘 처리하면 Subtask 1을 맞을 수 있다. 27점.

모든 계산을 정수로 한다면, 분자가 최대 \(10^{18}\)-scale, 분모가 최대 \(10^9\)-scale로 커지는 분수를 다루게 될 수 있다.

이러한 분수들은 몫을 비교한 뒤, 나머지에 해당하는 분수를 뒤집어서 재귀적으로 비교하는 방식으로 비교할 수 있다.

지금 생각해보면 처리 하나 잘못한 것 같은데 어쩌다가 처리가 잘 된건지 데이터가 물인지 잘 모르겠다 ㅋㅋㅋ

이 시점이 대강 3시간 20분 정도 지났을 때였다. 3번을 100 맞고, 4번 풀이를 고민하기로 했다.

앞서 짠 그리디가 상당히 비효율적임은 자명하다. 그래서 다음과 같이 수정했다. 

Greedy Algorithm 2 (for #3)

1. 일단 만들어야 하는 결과물을 하나 복사해 놓자. 역순으로 본다. 

즉, '이게 다 이렇게 색칠되어 있어야 해'에서 '아무렇게나 색칠되어 있어도 시행하면 결과물이 나오니까 괜찮아'로 간다. 

2. 만들어야 하는 결과물에서, 한 색으로 구성된 가장 큰 직사각형을 찾는다.

3. 그 직사각형을 '맨 마지막'에 색칠한다고 선언한다. 그러면 그 직사각형은 이제 '자유'롭다.

4. 이제 한 색으로 구성된 직사각형을 (자유로운 직사각형도 그 색으로 친다) 다시 찾자.

그 중에서 가장 '자유롭지 않은 격자'의 개수가 많은 직사각형을 찾는다. 그 직사각형은 이제 자유롭다. 

5. 4를 모든 격자가 자유로울 때까지 반복한다. 

이렇게 하면 시행 횟수가 302개가 나와서, 99.95점을 얻을 수 있다. 역겨운 점수다 ㄹㅇ

4에서 우리는 '자유롭지 않은 격자'의 개수가 최대인, 즉 '넓이 - 자유로운 격자 수'가 최대인 직사각형을 선택했다.

이제 적당한 실수 Magic을 잡아서, '넓이 - Magic * 자유로운 격자 수'가 최대인 직사각형을 뽑도록 해보자. 

Magic의 값에 따라서 시행의 횟수가 크게 달라지는데, Magic=1.01을 넣으면 시행 횟수가 296개가 나온다. 

좀 추하긴 했지만 아무튼 3번 100점을 이렇게 얻을 수 있었고, 이때가 3시간 40분이 지났을 때였다. 

4번을 잡았지만 다익스트라 생각에서 벗어나지를 못했다. 너무 어렵다. 나중에 보니 IOI 변형... 

http://blog.myungwoo.kr/20?category=516575 여기에 풀이가 있다. 신기함

그래서 1시간 30분 동안 아무것도 못하고 기도메타를 시전하며 끝났다. 393점 마무리.

고등학생으로 치는 마지막 정보대회를 기분 좋게 끝내서 좋다. 입시도 좀 잘 끝났으면 ㅋㅋ!

문제

다음 식을 만족하는 non-constant 다항식 \(P(x), Q(x)\)가 존재하는지 판별하시오.

$$ P(x)^{10}+P(x)^9 = Q(x)^{21}+Q(x)^{20} $$

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

이 문제도 얘들이 많이 못 풀었는데, 내가 시험장에서 깔끔하게 푼 문제다. 여기서도 점수 좀 딴 듯 ㅋㅋ

(증명) 불가능하다. 귀류법으로 보이자. 조건을 만족하는 non-constant 다항식 \(P, Q\)가 존재한다 가정하자.

다항식 \(f\)에 대하여 \(S_f\)를 \(f(x) = 0\)의 (복소수) 해집합이라 하자. 중근은 한 번만 센다. 다음 관찰을 하자.

관찰 1. \(S_{P} \cap S_{P+1} = S_{Q} \cap S_{Q+1} = \emptyset\)이고, \(S_P \cup S_{P+1} = S_{Q} \cup S_{Q+1} \)이다.

관찰 2. 주어진 식 양변의 차수를 비교하면, \(\text{deg}(P)=21x , \text{deg}(Q)=10x\)인 자연수 \(x\)가 있음을 알 수 있다.  

관찰 3. \(|S_{f}| \le \text{deg} (f)\)가 성립한다. 그러므로 \( |S_P| + |S_{P+1}| = |S_Q|+|S_{Q+1}| \le 20x \)다.

이제 여기서 다음 Lemma를 보이자. 

Lemma. non-constant 다항식 \(f\)에 대하여, \(|S_f| + |S_{f+1}| \ge \text{deg}(f) +1 \)가 성립한다. 

Proof of Lemma. 우선 \( \displaystyle f(x) = \prod_{i=1}^n (x-r_i)^{c_i} \), \( \displaystyle f(x)+1 = \prod_{i=1}^m (x-r'_i)^{c'_i}\)라 하자.

여기서 \(n=|S_f|\), \(m=|S_{f+1}|\)이다. \(r_i, r'_i\)들은 앞선 관찰 1에 의해 모두 서로 다른 복소수다.

한편, \(f'(x)\)는 \(r_i\)를 \(c_i-1\)-중근으로 가지고, \(r'_i\)를 \(c'_i-1\)-중근으로 가진다. 그러므로

$$ \text{deg}(f)-1 =\text{deg}(f')  \ge \sum_{i=1}^n (c_i-1) + \sum_{i=1}^m (c'_i-1) = 2 \text{deg}(f)-n-m$$

가 성립하고, 정리하면 \( |S_f|+ |S_{f+1}| \ge \text{deg}(f)+1\)을 얻는다. \(\blacksquare\)

Lemma와 관찰 3으로 \(20x \ge |S_Q|+|S_{Q+1}| = |S_P|+|S_{P+1}| \ge \text{deg}(P)+1 = 21x+1\)을 얻고, 이는 모순. \(\blacksquare\)

문제

(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를 얼마나 안 했는지 볼 수 있다. ㅋㅋ 백준은 꽤 한 것 같은데 다 수학이냐 ㅋㅋ 에휴...