rkm0959

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

문제

주어지는 양의 정수 \(N, L, K\)에 대하여, 다음 값을 \(10^9 + 7\)로 나눈 나머지를 구하시오. $$ \sum_{d=1}^N \mu (L \cdot d) \left \lfloor \frac{N}{d} \right \rfloor^K $$ 단, \(1 \le N \le 10^9\), \(1 \le L \le 10^{15}\), \(1 \le K \le 10^9\)이며, 시간 제한은 2.5초이다. 

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

풀이

우선 여기에 설명되어 있는 테크닉인 xudyh's sieve에 대한 이해가 필요하다. 

두 multiplicative function \(f(x)\)와 \(g(x)\)가 다음을 만족한다고 하자.

• \(g(x)\)의 partial sum, 즉 \(\sum_{i=1}^n g(i)\)를 빠른 시간에 구할 수 있다. 
• \((f * g)(x)\)의 partial sum, 즉 \(\sum_{i=1}^n (f*g)(i)\)를 빠른 시간에 구할 수 있다.
• 단, 여기서 \((f*g)(x)\)는 \(f(x)\)와 \(g(x)\)의 Dirichlet Convolution이다. 
• 여기서 빠른 시간은 상수 시간이나 로그 시간, 로그 제곱 시간 정도를 말한다.

그러면, 각 \(1 \le k \le n\)에 대해 \(\sum_{i=1}^{\lfloor n/k \rfloor} f(i)\)를 \(\mathcal{O}(n^{2/3})\) 정도 시간에 구할 수 있다. 

여기서 가능한 \(\lfloor \frac{n}{k} \rfloor\)의 값의 종류가 \(\mathcal{O}(\sqrt n)\)개임을 참고하자. 자세한 방법론과 구현 방법은 링크 참조. 

문제를 풀기 위해서, 먼저 \( \left \lfloor \frac{N}{d} \right \rfloor ^K\)라는 항부터 보자. \( \left \lfloor \frac{N}{d} \right \rfloor \)로 가능한 값의 종류가 \(\mathcal{O}(\sqrt N)\)개이므로, 그 값에 따라서 \(d\)를 \(\mathcal{O}(\sqrt N)\)개의 구간으로 묶어줄 수 있다. 예를 들어, \(lef_v \le d \le rig_v \iff \left \lfloor \frac{N}{d} \right \rfloor = v\)라고 하면, \(lef_v \le d \le rig_v\)에 대하여 \( \left \lfloor \frac{N}{d} \right \rfloor^K\)라는 값은 \(v^K\)로 일정하므로, \( \sum_{d=lef_v}^{rig_v} \mu(L \cdot d)\)를 구해주면 된다. 

또한, 모든 \(\left \lfloor \frac{N}{d} \right \rfloor\) 형태로 쓸 수 있는 자연수 \(v\)에 대하여, \(rig_v = \left \lfloor \frac{N}{v} \right \rfloor \)임을 쉽게 확인할 수 있다. 

그러므로 모든 \(\left \lfloor \frac{N}{d} \right \rfloor\) 형태로 쓸 수 있는 자연수 \(v\)에 대하여, \(rig_v\)와 \(lef_v-1\)은 모두  \(\left \lfloor \frac{N}{d} \right \rfloor\) 형태로 쓸 수 있다.

결국 남은 것은 각 \(1 \le k \le n\)에 대해 \(\sum_{d=1}^{\lfloor N/k \rfloor} \mu(L \cdot d) \)를 빠르게 구하는 것이다. 

우선 \(L\)이 square-free하지 않다면, \(\mu(L\cdot d)\)는 \(d\)와 관계 없이 무조건 \(0\)일 것이다. 

그렇지 않다면, \(\mu_L(d) = \frac{\mu (L \cdot d)}{\mu (L)}\)이라 하자. 이제 목표를 다시 쓰자. 

우리의 목표는 각 \(1 \le k \le n\)에 대해 \(\sum_{d=1}^{\lfloor N/k \rfloor} \mu_L(d) \)를 빠르게 구하는 것이다. 

Claim: \(\mu_L(x)\)는 multiplicative function이다. 

Proof of Claim: \(\text{gcd}(d,L) \neq 1\)이라면 \(\mu_L(d)=0\)이고, \(\text{gcd}(d,L)=1\)이면 \(\mu_L(d) = \mu(d)\)이다. 

이제 xudyh's sieve를 쓸 각을 재보자. \(g(x)=1\)을 선택한다. 이제 \( (\mu_L * g) (x)\)에 대해 생각해보자. 

\(p|L\)인 소수 \(p\)와 자연수 \(k\)에 대해, \((\mu_L * g)(p^k) = \sum_{i=0}^k \mu_L(p^i) = 1\)이다.

\(L\)의 약수가 아닌 소수 \(q\)와 자연수 \(k\)에 대해, \((\mu_L * g)(q^k) = \sum_{i=0}^k \mu_L(q^i) = 0\)이다.

\((\mu_L * g)(x)\)도 multiplicative function이니, 우리는 다음과 같은 결론을 얻을 수 있다. 

모든 소수 \(p\)에 대해 \(p|x \implies p|L\)이 성립하면, \((\mu_L * g)(x) = 1\)이고, 그렇지 않다면 \((\mu_L * g)(x)=0\)이다. 

결국 \(\sum_{i=1}^n (\mu_L * g)(i)\)는 \([1, n]\)에 속한 자연수 중 \(L\)의 소인수들로만 구성된 자연수의 개수이다. 

\(L\)의 소인수들로만 구성된 자연수는 생각보다 많지 않다. \(L \le 10^{15}\)이므로, \(L\)이 가질 수 있는 소인수의 개수도 적다. \([1,N]\)에 속한 자연수 중 \(L\)의 소인수들로만 구성된 자연수는 priority_queue 등을 통하여 모두 구할 수 있다. 

이제 \(\sum_{i=1}^n (\mu_L * g)(i)\)는 lower_bound 등의 함수를 통해 빠르게 구할 수 있다. 

결국 xudyh's sieve를 쓰기 위한 필요 조건이 모두 갖추어졌고, 구현만 하면 된다. 끝.

Aim: Solve \(x^2 \equiv n \pmod p \) in \( \mathcal{O}( \log^2 p ) \).

Tonelli-Shanks Algorithm은 \(\mathbb{Z}/p\mathbb{Z}\)에서 이차방정식을 빠르게 풀어내는 알고리즘이다.

Step 1. \(n\)이 \(\text{mod   } p\)에서 quadratic residue인지 확인한다. \( n^{\frac{p-1}{2}} \equiv 1 \pmod p\)인지 여부를 확인하면 된다.

Step 2. \(p-1 = Q \cdot 2^S\)인 홀수 \(Q\)와 음이 아닌 정수 \(S\)를 구한다. 

Step 3. \(\text{mod   } p\)에서 quadratic non-residue인 자연수 \(z\)를 하나 찾는다. 

Step 4. \(M=S\), \(c=z^Q\), \(t=n^Q\), \(R = n^{\frac{Q+1}{2}} \)라 하자. 전부 \(\text{mod   }p\)로 본다.

Step 5. 이제 다음을 반복한다.

• \(t=0\)이면 \(0\)을 출력한다. \(t=1\)이면 \(R\)을 출력한다. 
• 이제 \(0<i<M\)이면서 \(t^{2^i} \equiv 1 \pmod{p}\)를 만족하는 최소의 자연수 \(i\)를 찾는다.
• \(b=c^{2^{M-i-1}}\)이라 두고, \(M \leftarrow i\), \(c \leftarrow b^2\), \(t \leftarrow tb^2\), \(R \leftarrow Rb\)로 값을 바꿔준다.

알고리즘을 통해 출력된 값이 \(r\)이라면, \(r\)와 \(-r\)이 \(x^2 \equiv n \pmod p\)의 두 근이 된다.

이 알고리즘을 활용하여, \(ax^2+bx+c \equiv n \pmod p\)도 쉽게 풀 수 있다.  

Claim 1: 이 알고리즘으로 출력된 값이 \(r\)이라면, \(r^2 \equiv n \pmod p\)가 성립한다. 

Proof of Claim 1: 우선 \(c^{2^{M-1}} = -1\), \(t^{2^{M-1}} = 1\), \(R^2 = tn\)이 항상 성립함을 보이자. 

초기에 \(c^{2^{M-1}} = z^{Q \cdot 2^{S-1}} = z^{\frac{p-1}{2}} = -1\)이다. (\(z\)는 quadratic non-residue니까)

초기에 \(t^{2^{M-1}} = n^{Q \cdot 2^{S-1}} = n^{\frac{p-1}{2}} = 1\)이다. (\(n\)은 quadratic residue니까)

초기에 \(R^2 = n^{Q+1} = n \cdot n^Q = nt\)가 성립한다. 초기에서는 세 식이 모두 성립함을 확인했다.

Step 5에서 \(M, c, t, R\)이 \(M', c', t', R'\)으로 바뀐다고 하자. 

\(c'^{2^{M'-1}} = b^{2^i} = c^{2^{M-1}} = -1\)이므로, 바뀐 뒤에도 첫번째 식이 성립한다. 

\(t'^{2^{M'-1}} = t^{2^{i-1}} \cdot b^{2^i} = -1 \cdot -1 = 1\)이므로, 바뀐 뒤에도 두번째 식이 성립한다. (why?)

\(R'^2 = R^2b^2 = tnb^2 = t'n\)이므로, 바뀐 뒤에도 마지막 식이 성립한다.  

\(t^{2^{M-1}} = 1\)이므로, Step 5에서 항상 조건을 만족하는 \(i\)를 찾을 수 있다.

또한, Step 5를 반복하면서 항상 \(M\)의 값이 감소하게 된다. \(M'=i<M\)이기 때문이다. 

그러다가 \(M=1\)이 되면 그 순간 \(t=1\)임이 보장되며, \(R^2 = tn = n\)이므로 \(R\)은 합동방정식의 해가 된다. 

Claim 2: 이 알고리즘은 \(\mathcal{O}(\log^2 p) \)번의 사칙연산을 필요로 한다. 

Proof of Claim 2: Step 1, 2, 4는 로그 시간에 할 수 있음이 자명하다. 

Step 3는 그냥 \(z\)를 랜덤하게 잡아보면서 quadratic non-residue가 나오면 terminate하는 방식으로 \(z\)를 찾아도 된다. 

\(z\)가 quadratic non-residue일 확률이 \(\frac{1}{2}\) 정도이므로, 평균 2번 정도의 시행을 필요로 한다. 

Step 5의 loop는 최대 \(S = \mathcal{O}(\log p)\)번 돌아가고, 각 loop에서 소모하는 연산 횟수는 \(\mathcal{O}(M)\)번, 즉 \(\mathcal{O}(\log p)\)번이다.

그러므로 Step 5에서는 최대 \(\mathcal{O}(\log^2 p)\)번의 사칙연산을 활용한다. 

시간복잡도를 \(\mathcal{O}(S^2)\)로도 쓸 수 있으며, \(S\)가 작은 경우도 많다는 점도 주목하자.

이제 Hensel's Lemma를 걸어주면, \(x^2 \equiv n \pmod{p^k}\)도 빠르게 풀어줄 수 있다. 

활용문제: Project Euler 216, 437

https://www.acmicpc.net/contest/view/392

12월 20일에 나는 코더다 2018 송년대회가 열렸고, Open Contest는 12월 22일에 열렸다. 

본 대회에서는 L번을 제외하고 모든 문제가 풀렸고, 1등이 8문제, 2등이 7문제, 3/4등이 6문제를 풀었다.

마지막 AC가 종료 3분 전에 뜨고, 마지막 First Solve도 종료 7분 전에 뜨는 등 흥미진진한 대회였다. 

오픈 대회에서는 ainta님이 해결되지 못했던 L번을 포함한 11문제를 해결하셨다. 대신 C가 아예 안 풀렸다.

풀이는 난이도 순으로 작성한다. 난이도의 기준은 본 대회에서 문제를 해결한 팀 수로 정했다. 

I: Inspiration (bjwj5505, First Solve: 본 대회 6분, Open 14분) 

각 진법 수 \( B \)에 대하여, \(N\)을 \(B\)진수로 나타내었을 때 자릿수의 합은 \( \mathcal{O} (\log N)\)에 구할 수 있다. 그러니 그냥 모든 진법 수에 대해서 자릿수의 합을 계산해주면 \( \mathcal{O}(N \log N)\)에 문제를 풀 수 있다. 본 대회에서는 이 문제에 대한 short coding 상이 있었다. 짧은 코드로 이 문제를 해결하려면, 답에 규칙성이 있음을 파악해야 한다. \(N=8\)을 제외한 경우에서 최적의 진법 수는 \( B = \lfloor \frac{N}{2} \rfloor + 1\)이고, 이때 답은 \( \lceil \frac{N+1}{2} \rceil \)이다. \(N=8\)에서는 \(3\)진법일 때 자릿수의 합이 \(4\)가 나오는 경우가 최적이다. 이를 활용하여 코드를 작성하면 코드 길이가 매우 짧아진다. 대회에서는 76B의 코드로 문제를 해결한 팀이 두 팀 나왔다.    

G: Generic Queries (william202, First Solve: 본 대회 4분, Open 6분)

부분합의 개념을 그대로 활용하면 풀 수 있는 아주 쉬운 문제다. 

F: Finding Love (tae826, First Solve: 본 대회 22분, Open 17분)

단순 구현문제다. 문제에서 요구하는 것은 \(M-1\)명의 정보 실력이다. 그러니 단순히 정렬한 후 \( V_i\)번째에 위치한 사람의 정보 실력을 새로 들어올 사람의 정보 실력으로 바꿔주면 충분하다. 즉, 줄에 서 있는 순서는 정렬 기준에서 포함될 필요가 없다. 원래 문제는 줄에 서 있는 순서와 대회에서의 등수 사이의 상관관계에 대한 설명이 없었다. 그러나 이 경우에는 \(V_1\)등이 어떻게 정의되는지 논란이 생길 수 있고, 여러 생각 끝에 줄에 서 있는 순서를 등수를 결정하는 요소로 포함시켜서 이 애매한 요소를 없앴다.

의외로 많은 팀이 - 본 대회, 오픈 대회 모두 포함해서 - 여러 번 틀린 문제다. 1등한 윤교준 팀도 3틀 후 맞았다.

데이터나 디스크립션에 오류가 있는 줄 알고 출제자와 함께 많이 걱정했다. 디스크립션을 내가 고쳐서... 

J: JeoGyuk (william202, First Solve: 본 대회 50분, Open 66분)

저격 장소가 하나인 경우, 문제를 \(\mathcal{O}(N \log N + N \log MAX)\)에 풀 수 있다. 기울기를 다 구한 후 모두 약분하고 서로 다른 기울기의 개수를 세면 된다. 이제 저격 장소가 두 곳인 경우를 보자. 첫 저격 장소에서 제거할 적의 집합을 고정하면, 필요한 총알의 개수를 앞에서처럼 계산할 수 있다. 먼저 저격 장소와 적을 잇는 반직선의 기울기를 미리 전처리를 통해서 계산하자. 이제 첫 저격 장소에서 제거할 적의 집합 \( 2^N\)개에 대하여 필요한 총알의 개수를 모두 구하고, 이를 통해 답을 구할 수 있다. 이렇게 되면 시간복잡도는 \(\mathcal{O}(2^N \cdot N \cdot \log N)\)다. 만약 저격 장소와 적을 잇는 반직선의 기울기를 전처리하지 않았다면, 시간복잡도는 \(\mathcal{O}(2^N \cdot N \cdot \log MAX)\)가 되고, 이는 TLE를 받는다. 본 대회 1등팀이 5틀하고 맞았다. 이유는 반직선을 직선으로 봐서?

E: Erasing Matrix (rkm0959, First Solve: 본 대회 112분, Open 11분)

내가 냈고, 조금 부끄럽긴 하지만 IMO Shortlist 1989에서 나온 문제다. 이제 30년이나 된 문제다.

내도 되나 고민을 했는데, 문제 자체가 크게 어렵지도 않고, 최근 문제도 아니며, bjwj5505가 괜찮다고 해서 냈다.

그리고 실제로 본 대회나 오픈 대회나 '중간 난이도의 문제' 역할을 적당히 수행해 낸 것 같다. 

우선 \( N \times M \) 격자의 모든 칸을 한 번씩만 지나는 경로를 하나 잡자. 당연히 경로에서 인접한 칸은 실제 격자에서도 인접한 칸이도록 한다. 이런 경로는 간단하게 ㄹ자 모양으로 만들어 줄 수 있다. 이제 이런 경로를 잡으면, 문제를 \(1 \times NM\) 격자에서, 즉, 하나의 수열에서 해결해도 충분해진다. 이제 수열에서 문제를 풀자.

이제 우리는 \(a_1 , a_2, \cdots a_{NM}\)이란 수열을 가지고 문제를 풀고 있다. 먼저 생각할 것은, 어떠한 시행을 하더라도 홀수 index를 가진 수들의 합과 짝수 index를 가진 수들의 합의 차이는 일정하다는 것이다. 최종 상태에서 이 차이는 \(0\)이므로, 이 차이가 \(0\)이 아니면 바로 \(-1\)을 찍고 끝내자. 그렇지 않다면, 시행을 통해 수들을 모두 \(0\)으로 만들 수 있다. 차례대로 \(0\)을 만들어보자. 

세 수 \(a\), \(b\), \(c\)가 수열에서 인접한 상태라고 생각해보자. 만약 \(a \le b\)라면, 앞쪽 두 수에 \(-a\)를 더하여, \(0\), \(b-a\), \(c\)를 만들 수 있다. 만약 \(a > b\)라면, 뒤쪽 두 수에 \(a-b\)를 더하고 앞쪽 두 수에 \(-a\)를 더하여 \(0\), \(0\), \(a-b+c\)를 만들 수 있다. 이 방법을 통해서 맨 뒤에 있는 수 2개를 제외한 모든 수를 \(0\)으로 만들 수 있다. 한편, 홀수 index를 가진 수들의 합과 짝수 index를 가진 수들의 합은 항상 일치하므로 맨 뒤에 있는 수 2개는 동일하다. 그러니 맨 뒤에 있는 수 2개 역시 \(0\)으로 만들 수 있다. 이제 구현. 

D: Dragging (bjwj5505, First Solve: 본 대회 293분, Open 63분)

이 문제부터 난이도가 크게 올라갔다. 앞선 문제들은 본 대회에서 절반 이상의 팀이 풀었다.

이 문제는 총 2팀이 풀었고, 퍼솔이 대회 종료 7분 전, 두 번째 솔브가 대회 종료 3분 전에 나왔다. 

개인적으로 정말 예쁜 문제라고 생각한다. 사전지식도 많이 필요 없고... bjwj5505가 만든 갓문제다.

우선 \(K=0\)이면 바로 \(C_1\)을 답으로 찍어주자. 낚시성이 조금 있지만 디스크립션 잘 읽는 것도 실력이다.

이제 \(K \ge 1\)을 가정하고 문제를 풀자. 이 문제의 핵심은, \(K\)의 값이 아예 중요하지 않다는 것이다. 

답은 \(ans\)라 하면, \(ans \ge CUT\)인 것은 태영이가 \(CUT\) 이상의 '짠 정도'를 가진 점으로 갈 전략이 있음과 같다.

이렇게 생각하면, 이진탐색이 가능함을 알 수 있다. 이제 결정문제를 해결하자. 

\(ans \ge CUT\)이 성립하는지 여부를 확인해보자. 이제 '짠 정도'가 \(CUT\) 이상인 음식점을 '좋은 점'이라 하자. 

'좋은 점'이 아닌 음식점을, '나쁜 점'이라 하자. 다음 Claim이 이 문제의 핵심이다.   

Claim: 태영이가 '좋은 점'으로 이동할 수 있을 필요충분조건은, 다음을 만족하는 음식점 \(x\)가 존재하는 것이다.

1. \(x\)와 \(1\) 사이의 거리는 2 이하이다. (즉, 1번 음식점에서 20분 거리 안에 \(x\)가 있다.)

2. \(x\)에서 거리가 2 이하 떨어진 모든 음식점 \(y\)는 '좋은 점'이다. (즉, 20분 거리 안에 있는 모든 음식점이 '좋은 점'이다.)

Proof of Claim: 조건을 만족하는 \(x\)가 존재한다고 가정하자. 그러면 태영이는 먼저 20분 동안 \(x\)로 이동한다. 그 후에 승한이가 10분 간 어디로 끌고 가던, 태영이는 다시 \(x\)로 돌아온다. 그러면 승한이는 다시 \(x\)로부터 최대 20분 거리인 음식점으로 이동하게 된다. 다시 태영이는 \(x\)로 돌아온다. 이를 반복해주면, 결국 승한이가 마지막으로 태영이를 끌고 온 음식점은 '좋은 점'이 된다는 것을 확인할 수 있다. 이제 반대로 조건을 만족하는 \(x\)가 없다고 가정하자. 그러면 태영이가 20분을 끌어 도착한 지점을 \(x'\)이라 하면, 가정에 의해 20분 거리 이내에 '나쁜 점' \(y'\)가 있다. 승한이가 \(y'\) 방향으로 10분 이동하면, 태영이가 승한이를 10분 간 어디로 끄냐에 관계 없이 승한이는 태영이를 20분 동안 끌어 \(y'\)에 도착할 수 있다. 이를 반복해주면, 승한이가 마지막으로 태영이를 끌고 \(y'\)에 도착할 수 있다. 즉, 태영이는 '나쁜 점'에 도착하게 된다. 

이제 이 Claim을 알면, 결정 문제를 \(\mathcal{O}(N+M)\)에 풀 수 있다. '나쁜 점'들을 모두 Queue에 넣고 BFS를 한 번 돌려주고, 1번 정점에서 시작하는 BFS를 한 번 돌려주면 된다. 이 풀이와 별개로 검수진이 찾은 \(\mathcal{O}(N+M)\) 풀이가 있다.

A: American Tour (tae826, First Solve: 본 대회 238분, Open 61분)

양방향 간선을 단방향 간선 두 개로 나누고 시작하자. 간선이 겹치는 것을 막기 위해서, 1번 정점에서 2번 정점으로 가면서 가는 도중의 길을 역방향으로 바꾸고, 가중치를 음수로 바꿔준다. 이렇게 되면 두 번 방문한 간선이 취소가 되는 효과가 나타나게 된다. 1번에서 2번으로 간 후 2번에서 \(N\)번으로 가면, 역방향 간선 때문에 2번 정점을 아예 안 지나게 되는 효과가 나타날 수 있다. 이를 해결하기 위해서, 1번에서 2번으로 가는 최단경로를 구한 뒤, 간선 정보를 수정하고 N번에서 2번으로 가는 최단경로를 구한다. 결국 벨만포드 2번으로 문제는 해결된다. 이 문제를 푼 팀이 한 팀 밖에 없어서 아쉬웠다. 

B: Bob's Rummikub (pasa3232, First Solve: 본 대회 146분, Open 201분)

놀랍게도 정해는 백트래킹이다. 원래 출제자의 의도는 '정보를 잘 못하는 친구들이 FGI 다 풀고 아무것도 못하는 상황일 때 열심히 코딩해서 맞던 틀리던 의미있게 시간을 보낼 수 있는 문제'였다. 제한이 좀 빡세게 보였던 것 같다. 

정해는 백트래킹이고, 여기서 굳이 더 설명할 이유는 없을 것 같다. 본 대회에서 이 문제를 유일하게 해결한 1등팀은 이 문제를 bit dp로 해결했고, 이것 역시 출제자와 검수진 쪽에서 예상한 풀이 중 하나였다. 

C: Congruence Equation (rkm0959, First Solve: 본 대회 190분, Open N/A)

안 좋은 문제인 것은 이미 알고 있었지만 그냥 출제했다. B처럼 어려운 정보문제를 잡을 수 없는 친구들이 풀라고 낸 문제다. 

본 대회에서 0솔브였으면 조금 추해졌을 것 같은데, 1솔브가 나왔고 최종 스코어보드에 유의미한 영향을 주었다.

풀이는 수학 90%, 프로그래밍 10%다. 프로그래밍이 10%면 문제를 뭔 생각으로 출제했냐고 생각할 수 있다.

프로그래밍 지분이 높은 수학 문제 - 즉 xudyh sieve 등의 고난이도 수학 테크닉을 필요로 하는 수학 문제를 내면 일단 문제를 출제한 명분도 사라지고 아무도 시도조차 할 수 없는 문제가 되어버릴 것 같았다. 그래서 포기했다.

내가 낸 빡센 수학 문제를 보고 싶으면 https://www.acmicpc.net/problem/16164 여기로 가자.    

\(a^b \equiv b^a \equiv 0 \pmod{p}\)인 경우는 \(a, b\)가 모두 \(p\)의 배수인 경우로, \((p-1)^2\)개 있다.

아니라면, 원시근 \(g\)를 하나 잡고 시작하자. \(a \equiv g^x \pmod{p}\), \(b \equiv g^y \pmod{p}\)인 \(0 \le x , y \le p-2 \)를 생각하자. 

그러면 \( a^b \equiv b^a \pmod{p}\)는 \(xb \equiv ya \pmod{p-1}\)과 동치이다. 

한편, \(a, b\)를 \(p-1\)로 나눈 나머지와 \(x, y\)를 고정하면, CRT에 의해 유일한 자연수 순서쌍 \((a,b)\)가 대응된다.  

이는 당연히 \(1 \le a, b \le p(p-1)\)이란 조건이 주어졌기 때문이다. (문제 풀이의 힌트가 될 수 있는 조건이다) 

결국 목표는 \(0 \le x, y \le p-2\)와 \(xb \equiv ya \pmod{p-1}\)을 만족하는 \(a, b, x, y\)의 개수를 구하는 것이다.   

\(a, x\)를 고정하고, 가능한 \(b, y\)의 개수를 세자. 

\(u=\text{gcd}(a,p-1)\)이라 하면, \(bx \equiv 0 \pmod{u}\)이므로, \(b \equiv 0 \pmod{ \frac{u}{\text{gcd}(x,u)} } \)다. 

이제 \(bx \equiv ay \pmod{p-1}\)은 \(\frac{bx}{u} \equiv \frac{a}{u}y \pmod{ \frac{p-1}{u} } \)과 동치다. 

그러므로 각 \(b\)당 가능한 \(y\)로 가능한 수는 \(u\)개이다. 또한, \(b\)로 가능한 수는 \( \frac{(p-1)\text{gcd}(x,u)}{u} \)다. 

결론적으로 \(b, y\)로 가능한 것의 개수는 \((p-1) \text{gcd}(x, u)\)다. 

이제 각 \(1 \le x, a \le p-1\)에 대해서 \(\text{gcd}(x, a, p-1)\)을 더한 값을 구하자.

각 \(u|p-1\)에 대해서, \(\text{gcd}(a,p-1)=u\)인 \(a\)의 개수는 \(\phi( \frac{p-1}{u})\)개다. 

그러므로 우리가 계산할 값은 \( \sum_{u|p-1} \phi(\frac{p-1}{u}) \cdot \sum_{x=1}^{p-1} \text{gcd}(x,u)\)다. 

다시 \(\text{gcd}(x,u)\)를 보면, 각 \(v|u\)에 대해 \(\text{gcd}(x,u)=v\)인 \(x\)의 개수는 \(\frac{p-1}{u} \phi(\frac{u}{v}) \)이다.

이제 남은 것은 $$ \sum_{u|p-1} \phi(\frac{p-1}{u}) \cdot \sum_{v|u} \frac{p-1}{u} \cdot v \cdot  \phi(\frac{u}{v})$$ 를 계산하는 것이다. \(u\)를 \(\frac{p-1}{u}\)로 바꿔치면, $$ \sum_{u|p-1} \phi(u) \cdot \sum_{uv|p-1} uv \cdot  \phi(\frac{p-1}{uv})$$를 얻고, 여기서 \(uv=k\)를 고정하는 방식으로 식을 조작하면 $$ \sum_{k|p-1} k \cdot \phi(\frac{p-1}{k}) \sum_{u|k} \phi(u)  = \sum_{k|p-1} k^2 \phi(\frac{p-1}{k})$$를 얻는다. 결국 이 값을 구하면 문제가 해결되고, 이는 Dirichlet Convolution 등 방법으로 구할 수 있다. 

참고로, \(p-1\)의 약수의 개수의 제곱에 준하는 계산량이 필요한 풀이는 TLE를 받는다. ainta님 까비...

H: Hosting MT (ddokddogi, First Solve: 본 대회 251분, Open 234분)

친구가 문제를 만들 시간이 없어 문제를 가져오기로 했는데, 놀랍게도 수학 문제를 가져왔다. ㅋㅋㅋ....

IPSC 2008년 L번 문제다. 원순열 느낌의 counting을 연습할 수 있다. https://ipsc.ksp.sk/2008/real/solutions/l.html

K: Katty and Wonki (william202, First Solve: 본 대회 99분, Open 167분)

Tree DP 문제다. 정해는 \(\mathcal{O}(N \log N)\)이다. 원래는 \(\mathcal{O}(N^2)\)이 정해인 문제였으나, 검수진 중 한 명이 더 빠른 \(\mathcal{O}(N \log N)\) 풀이를 발견하여 문제가 버프를 먹었다. 풀이는 출제자가 제작한 ppt로 대체한다. 캐티와 원기.pptx

L: Love Triangles (rkm0959, First Solve: 본 대회 N/A, Open 126분)

퍼즐 문제로 출제했으며, 다양한 construction이 존재할 수 있는 문제다. 본 대회에서는 꽤 많은 팀이 시도를 했으나, 푼 팀은 없었다. 1등 윤교준팀이 이 문제에서 시간을 좀 낭비했다. 체커가 잘못된 것 같다며 체커를 확인하러 오기도 했다 ㅋㅋㅋ... 

물론 윤교준팀이 자체적으로 짠 체커가 틀린 것이었다. 오픈 대회에서는 ainta가 처음으로 해결했다.  

풀이에 따라 아이디어가 다양할 것 같은데, 우선 내 풀이의 첫 아이디어는 다음 그림에서 나온다. 

중요한 아이디어가 하나 더 필요하다. 만약 A1이 B에 속한 학생과 친구 관계를 아예 맺지 않았다면, A1은 Love Triangle에 속할 수 없다. 현재 문제 상황에서는 이 아이디어는 필요가 없다. \(N+1\)개의 친구 관계를 맺으려면, 자신이 속하지 않은 두 학교 모두에 친구가 한 명 이상은 있어야 한다. 하지만 첫 아이디어처럼 각 학교의 학생들을 두 그룹으로 분할하면 이야기는 달라진다. 물론 학교를 64명의 그룹 2개로 분할하면 상황은 크게 달라지지 않는다. 그렇지만 그룹을 불균일하게 분할하면 어떨까?

이렇게 분할해보자. 그러면 A1, C2는 66명, B1, B2는 64명, C1, A2는 65명의 친구 관계를 필요로 한다. 

보이다시피 \(G_1\)의 상황과 \(G_2\)의 상황이 완전히 동일하므로, \(G_1\)만 만들어주면 된다. 

또한, \(G_1\)만 보면 각 학교의 인원이 모두 다르므로, 위에서 언급한 아이디어를 사용할 수 있다. 

이제 \(G_1\)을 직접 construct 하는 것은 그렇게 어렵지 않다. 아래는 내가 사용한 예시다. 

입시가 끝이 났고, 학교 과제도 어느 정도 마무리된 것 같다. 이제 진짜로 하고 싶은 것을 할 시간.

1. Principles of Mathematical Analysis (Rudin) 읽기

2. 선형대수와 군 (李仁碩) 읽기 + A Rough Guide to Linear Algebra (김동률) 읽기

3. Competitive Programming 연습: 알고리즘 더 배우고 junis3/TAMREF와 Atcoder 역주행

4. Mathematical PS 연습: Project Euler 많이 풀기

5. 열심히 놀기: 해외여행도 가고, 새로운 사람도 만나고, 게임도 열심히 (ㅎㅎ) 하기

6. 1~5를 하면서 블로그 활동도 열심히 하기

UPD) 5번 포함해서 하나도 안 함 ㅋㅋ

D-1

시험을 하루 앞두고 마지막 점검에 들어갔다. 컨디션이 많이 안 좋아보였다. 

문제 푸는 방법도 잘 안 보이고... 계산도 계속 실수를 해서 자신감이 조금 떨어지고... 정신적으로 힘들었다.

자기 직전에 멘탈 마지막으로 잡으려고 레미제라블의 'One Day More'를 들었는데, 멘탈이 더 깨졌다.

솔직히 내일이 심판의 날이네 주의 뜻을 알 수 있는 날이네 뭐네 이러는데 멘탈에 도움이 될리가 없다 ㅋㅋ

잠도 더럽게 안 와서 12시 근처에 잔 것 같다. 시작되지도 않은 시험에 크게 말린 느낌이 들어서 걱정이 앞섰다.

D-Day

새벽 5시에 일어나서 씻고 바로 출발, 새벽 6시 30분 정도에 익숙한 수리과학부 건물에 도착했다.

잠을 좀 깨고 정신을 차려서 면접 건물로 이동하고, 학교 선생님의 격려 속에서 친구와 같이 면접 대기실로 갔다.

면접 장소인 4층에 올라가보니, 복도에 책상이 깔려 있었다. 여기서부터 약간 소름 ㅋㅋ

대기실로 들어가서, 주변에 아는 사람이 있나 좀 둘러보았더니, 면접자 라인업이 상당히 살벌했다.

특히 서울과학고에서 온 친구들은 거를 타선이 없을 정도로 수학을 잘하는 친구들만 와서 무서웠다.

면접을 보는 순서를 곧 알려주셨고, 내가 5번째 순서로 면접을 본다는 사실을 확인했다.

대기하는 동안에는 내가 전날 확인해둔 자소서 관련 내용을 다시 상기하고, 프린트 몇 개 꺼내서 읽었다. 

면접 대기실의 분위기가 그렇게 무겁지는 않아서 좋았던 것 같다. 학생들의 긴장을 풀어주기 위해 많이 노력하신 것 같다.

아무튼 내가 면접을 보는 시간인 9:45는 빠르게 다가왔고, 운명의 45분이 시작되었다. 

문제

1. \( A(-10,2), B(10,2)\)가 \(xy\) 평면 위에 있다. 또한, 점 \(C, D\)는 \(x\)축 위의 점이다. 

(1) \( AC + CD + DB\)가 최소일 때, \(C, D\)의 좌표를 구하시오.

(2) \( 0< k \le 1\)인 \(k\)에 대해 \(AC+kCD+DB\)가 최소가 되도록 \(C, D\)를 잡자. 

이때, \(C\)와 \(D\)가 \(y\)축에 대해 대칭임을 보이시오. 

(3) \(k\)가 1에서 시작하여 감소하다 어느 값이 되면 \(AC+kCD+DB\)의 값을 최소로 하는 점 \(C, D\)가 움직이기 시작한다. \(C, D\)가 움직이기 시작하게 되는 \(k\)의 값을 구하시오.

2. \(xy\) 평면에서 다음과 같은 영역 \(S, T\)를 정의하자. 

$$ S = \{(x,y) | |y| > x^2\} $$ $$ T = \{(x,y)|0<|y|<|x| \} $$ 또한, 시행 \((P)\)와 \((Q)\)를 다음과 같이 정의하자. 

시행 \((P)\): \(0\)이 아닌 정수 \(m\)을 선택하고, \((x,y)\)를 \((x^2+2my,y)\)로 옮긴다.

시행 \((Q)\): \(0\)이 아닌 정수 \(n\)을 선택하고, \((x,y)\)를 \((\sqrt{|x|},y+2nx)\)로 옮긴다.

(1) \(S\)에 속한 점은 시행 \(P\)를 통해 \(T\)의 점으로 옮겨진다는 것을 보이시오.

(2) '되돌이점'을 다음과 같이 정의하자. 

점 \((x,y)\)에 대하여, 시행 \((Q)\)와 시행 \((P)\)를 번갈아 진행했을 때 다시 원위치로 돌아올 수 있는 점들을 되돌이점이라고 한다. 단, 시행은 반드시 시행 \((Q)\)로 시작되어야 한다. 

(예시) \((0,0) \rightarrow (0,0)\), (\(n=1\) 선택하여 시행 \((Q)\))

\((1,2) \rightarrow (1,0) \rightarrow (1,0) \rightarrow (1,2)\), (\(n=-1\), \(m=1\), \(n=1\)을 순서대로 선택하여 \((Q), (P), (Q)\) 시행)

그러므로, \((0,0), (1,2)\)는 모두 되돌이점이다. 이제 \((1,0)\)은 되돌이점인지 판단하시오. 

풀이

1번을 보고 약간 당황했다. 이런 기하문제가 입시에 나올 것이라고는 생각하지 못했다.

우선 1-(1)은 \(B\)를 \(x\)축 기준으로 대칭시킨 다음, 삼각부등식을 적용하여 해결할 수 있다. 

\(B'(10,-2)\)를 잡으면, 대칭성과 삼각부등식에 의해서 다음이 성립함을 확인할 수 있다.

$$ AC + CD + DB = AC + CD + DB' \ge AB' $$ 등호는 \(A, C, D, B'\)이 한 직선 위에 있을 때 성립하며, 이 경우는 \(C, D\)가 원점일 때이다. 

1-(2)는 초반에 방향을 잘못 잡으면 말릴 수 있는 문제였다. \(C, D\)가 원점을 기준으로 반대 방향에 있어야 한다는 사실을 가정한다면, \(C, D\)는 각각 \(AC+ k CO\), \(DB+kDO\)를 최소화하는 점으로 잡으면 되고, 이 위치는 각 식의 대칭성에 의해서 원점을 기준으로 대칭임을 확인할 수 있다. 물론, \(AC+kCO\)가 유일한 \(C\)에 대해서 최솟값을 가진다는 사실을 확인해야 한다. 하지만 이 풀이는 \(C, D\)가 원점을 기준으로 같은 방향에 있을 경우를 처리하지 못하고, 이 경우를 처리하는 것이 생각보다 논리적으로 하기 까다롭다. 여기서 말리기 쉽다. 실제로 나도 여기서 한 번 말렸고, 1-(3)을 해결한 뒤에 돌아와서 풀 수 있었다. 

아이디어는 \(CD\)의 길이를 고정하고 생각하는 것이다. 그러면 \(AC+DB\)의 길이를 최소화하는 문제가 된다.

\(B\)를 \(CD\) 길이만큼 \(x\)축 방향으로 (\(C\)에 가까워지는 방향으로) 평행이동시킨 것을 \(B'\)이라 하자.

그러면 \(AC+CB'\)의 길이를 최소화하는 문제가 되고, 이는 다시 1-(1)처럼 \(B'\)을 \(x\)축 기준으로 대칭시켜서 풀 수 있는 문제가 된다. 이제 적당하게 계산을 해주면 원하는 결론이 얻어진다. 

\(D\)가 \(C\)보다 왼쪽에 있는 경우에 관해서 의문이 들 수 있는데, 이 풀이는 이 경우에도 정당하다.

1-(3)은 1-(2)의 결론에 의해 \(C(-u,0), D(u,0), u \ge 0\)을 잡고 (\(C\)가 \(D\)보다 왼쪽에 있어야 최소임은 자명하다) $$ f(u) = AC + k CD + DB = 2ku+2\sqrt{(10-u)^2+2^2} $$를 설정하자. 우리의 목표는 \(f(u)\)의 최솟값이 \(u=0\)에서 얻어지지 않는 \(k\)의 범위를 구하는 것이다. 

\(f\)를 한 번 미분하면, \(f'(u)=2\left(k - \frac{(10-u)}{\sqrt{(10-u)^2+2^2}} \right) \)가 나온다. 

여기서 확인해야 할 점은, \( \frac{(10-u)}{\sqrt{(10-u)^2+2^2}} \)가 \(u\)에 대해서 감소하는 함수라는 것이다. 

즉, \(f'(u)\)는 \(u\)에 대해서 증가하는 함수라는 사실을 확인할 수 있다. 이제 \(k\)에 대한 논의를 시작할 수 있다.

만약 \(f'(0) \ge 0\)이라면, \(f\)는 \(u\)에 대한 증가함수이다. 최솟값은 \(u=0\)에서 나온다. 

만약 \(f'(0) < 0\)이라면, \(f\)는 확실하게 \(u=0\)에서 최솟값을 가지지는 않는다. 

그러므로 커트는 \(f'(0)=0\)일 경우에 일어나며, 이 경우에서 \(k=\frac{5}{\sqrt{26}}\)이다. 

2번으로 넘어갔다. 상당히 새롭고 참신한 문제를 내려고 노력하신 것 같다. 정말 재밌는 문제.

우선 2-(1)을 풀기 위해, 우리가 무엇을 원하는 지를 다시 한 번 확인해보자. 

목표: \(|y|>x^2\)이면 \(0\)이 아닌 정수 \(m\)에 대해 \(|x^2+2my|>|y|>0\)이 성립함을 보이자.

좌변을 \(m\)에 대한 식으로 보면, 이 식은 \(-\frac{x^2}{2y}\)를 기점으로 증/감이 바뀌는 V 모양 함수다.

그러므로, \(m\)이 \(-\frac{x^2}{2y}\)에 가장 가까운 \(0\)이 아닌 정수인 경우에만 부등식을 확인해주면 된다. 

\(|y|>x^2\)이므로 \(\left| \frac{x^2}{2y} \right| \le \frac{1}{2}\)가 성립하고, 결국 \(m=\pm 1\)만 보면 충분하다. 

계산을 간단하기 위해서, 다음 보조정리들을 활용하도록 한다. 아래 논의에서 '부호'는 양수/0/음수로 나뉜다.

보조정리 1: \(0 \le |x|<|y|\)인 실수 \(x, y\)가 있다. \(y\)와 \(y+x\)와 \(y-x\)는 모두 부호가 동일하다. 

보조정리 2: \(x, y\)가 부호가 동일한 \(0\)이 아닌 실수라면, \(|x+y| > |y|\)가 성립한다. 

두 보조정리의 증명은 자명하므로 생략한다. 이제 \(m = \pm 1\)일 때 부등식을 증명해보자. 

\(m=1\)인 경우: \(y\)와 \(y+x^2\)의 부호가 동일하므로, \(|x^2+2y| = |y+(y+x^2)| > |y|\)다.

\(m=-1\)인 경우: \(y\)와 \(y-x^2\)의 부호가 동일하므로, \(|x^2-2y|=|y+(y-x^2)| > |y|\)다.

결국 \(m=\pm 1\)일 때 부등식이 성립하고, 모든 \(0\)이 아닌 정수 \(m\)에 대해 \(|x^2+2my|>|y|\)가 성립한다. 

한편, \(|y|>x^2 \ge 0\)이므로 \(|y|>0\)도 어렵지 않게 얻어진다. 이렇게 2-(1)의 증명이 끝난다. 

2-(2)는 답을 추측하는 게 중요한 문제다. 답은 되돌이점이 '아니다'. 

2-(1)에서와 마찬가지 방식의 논의로, \(T\)에 속한 점이 시행 \((P)\)를 통해서 \(S\)로 이동함을 알 수 있다.

\((1,0)\)에서 시행 \((Q)\)를 적용하면 \((1,2n)\)으로 이동하고, 이 점은 \(n\)이 \(0\)이 아닌 정수면 무조건 \(S\)에 속한다. 

그러므로 우리의 점은 \((P), (Q)\)를 반복 적용하면서 \(S, T\) 사이를 반복적으로 움직이게 된다. 

그러나 \((1,0)\)은 \(S\)에도, \(T\)에도 없다. 그러므로 \((1,0)\)으로 되돌아 오는 것은 불가능하다. 증명 끝.

면접

어마어마하게 떨었다. 면접에서는 풀이지를 교수님께 보여드리면서, 연필로 중요 내용을 짚어가며 설명하게 되었다.  

긴장한 상태에서 최대한 엄밀하게 모든 내용을 설명하려고 하다보니, 시간이 꽤 오래 걸렸다.   

교수님의 질문은 2-(2)에서의 '마찬가지 방식의 논의'에 대한 설명 요구였다. 이 설명을 마쳤더니 시간이 3분 남았다. 

그 후 교수님께서는 자소서 4번 - 독서에 관한 질문을 하셨고, (인상 깊게 읽은 책 소개) 전날에 준비한 덕분에 대답할 수 있었다. 

다음은 다른 친구들이 받았다던 추가질문 몇 개다. 

추가질문 1: 되돌이점의 예시를 하나 더 찾으시오. 

추가질문 2: https://en.wikipedia.org/wiki/Sharkovskii%27s_theorem의 하위호환 (이게 왜 나왔는지 잘 모르겠다)

periodic point of period \(3\)가 존재하면, periodic point of period \(2\)가 존재함을 보이는 문제가 나왔다고 한다.

물론 여기서 다루는 함수는 연속함수. 자세한 내용은 위키 링크를 타고 읽어보는 게 좋을 것 같다. 

3년간 고생이 많았는데 좋은 결과가 나왔으면 좋겠다. 

UPD: SNU 2019.

29.

기본 세팅을 다음과 같이 하자. $$\vec{AP} = p\vec{AB}$$ $$ \vec{AQ} = q\vec{AB} + (1-q) \vec{AC}$$ $$\vec{AR} = r \vec{AC}$$ 여기서 \(p, q, r\)은 모두 \(0\) 이상 \(1\) 이하의 실수이다. 

이제 계산하면 $$ \vec{AX} = \left( \frac{1}{4} p  + \frac{1}{2} q \right) \vec{AB} + \left( \frac{1}{4}r + \frac{1}{2} (1-q) \right) \vec{AC}$$이다. 여기서 \(\frac{1}{2}q \vec{AB} + \frac{1}{2}(1-q)\vec{AC}\)는 \(AB\)의 중점과 \(AC\)의 중점을 연결한 선분이 된다. 

이 선분 위에 있는 점 \(X'\)을 잡자. 그러면 

$$ \vec{AP} = \vec{AX'} + \frac{1}{4} p \vec{AB} + \frac{1}{4} r \vec{AC} $$가 가능한 \(P\)의 자취를 구하는 것이 목적이 된다. 

\(\frac{1}{4}p \vec{AB} + \frac{1}{4}q \vec{AC} \)를 더하는 것은 각 변이 \(AB, AC\)와 평행하고 길이가 \(\frac{1}{4}AB\), \(\frac{1}{4}AC\)인 평행사변형을 그리는 것이다. 

이제 \(\vec{AX}\)가 어떤 영역을 움직이는지 쉽게 파악할 수 있다. 답은 \(S=9 \cdot \left(1- \frac{1}{4} - 2 \cdot \frac{1}{16} \right) = \frac{45}{8}\)이므로 \(53\)이다.

30. 

\(g(x)\)를 미분하는 것으로 시작하자. 미분해보면, 결과는 $$ g'(x) = \frac{-f'(x) \cos f(x)}{(2+\sin f(x))^2} $$이 나온다. 이제 (가), (나) 조건을 통해서 필요한 정보를 얻어보자. 

(가) 조건에서는, \(\alpha_1 = 0\)을 알려준다. \(g'(0)=0\)이므로, \(f'(0)=0\)이거나 \(\cos f(0) = 0\)임을 알 수 있다. 

그런데 \(g(0)=\frac{2}{5}\)이므로 \(\sin f(0) = \frac{1}{2}\)이다. 여기서 \(\cos f(0)=0\)이 불가능하다는 것을 얻는다. 

한편, \( 0< f(0) < \frac{\pi}{2}\)이므로 \(f(0)=\frac{\pi}{6}\)이다. 그러므로 (가)에서 얻은 조건은 두 개로 요약 가능하다.

첫 번째 조건: \(f(0)=\frac{\pi}{6}\)이다. 두 번째 조건: \(f'(0)=0\)이다. 

구해야 하는 \(f\)의 계수 4개에 대한 일차식을 무려 3개를 얻었다. (최고차항 계수가 주어졌으므로.) 

(나) 조건에서는, 식을 살짝 바꿔주면 $$\sin f(\alpha_5) = \sin f(\alpha_2) + \frac{1}{2}$$를 얻는다. \(g'(x)\)의 형태에서, 우리는 임의의 극대/극소점 \(\alpha\)에 대해 다음이 성립함을 안다. 

팩트: \(f'(\alpha)=0\)이거나 \(\cos f(\alpha) = 0\) - 즉 \(\sin f(\alpha) = \pm 1\)이다. 

\(\sin f(\alpha_5) = \sin f(\alpha_2) + \frac{1}{2}\)라는 식을 관찰해보면, 두 \(\sin\) 값이 모두 \(\pm 1\) 형태일 수는 없다. 

또한, \(f'\)의 근은 최대 2개이므로, \(f'(\alpha_2) = f'(\alpha_5) = 0\)일 수는 없다.

그렇다면 결론은 하나다. 두 \(\alpha\) 중 하나는 \(f'\)이 \(0\)이 되고, 하나는 \(\sin f(\alpha)\)가 \(\pm 1\)이 된다. 

\(\sin\) 함숫값의 절댓값이 \(1\) 이하임에 착안하여 경우를 나누면, 다음 둘 중 하나임을 알 수 있다.

Case 1. \(\sin f(\alpha_2) = \frac{1}{2}\), \(\sin f(\alpha_5) = 1\), \(f'(\alpha_2) = 0\).

Case 2. \(\sin f(\alpha_2) = -1 \), \(\sin f(\alpha_5) = -\frac{1}{2}\), \(f'(\alpha_5) = 0\).

이제 두 경우에 따라서 각각 \(f\)가 알맞게 나오는 지 확인해보도록 하자. 

Case 1. \(\sin f(\alpha_2) = \frac{1}{2}\), \(\sin f(\alpha_5) = 1\), \(f'(\alpha_2) = 0\).

이 경우에는 \(g(\alpha_1) = g(0) = \frac{2}{5} = g(\alpha_2)\)가 된다. 

그러므로 \((\alpha_1, \alpha_2)\) 안에서 \(g(x)\)는 극대/극소를 적어도 한 번 가진다. 모순. 

Case 2. \(\sin f(\alpha_2) = -1\), \(\sin f(\alpha_5) = -\frac{1}{2}\), \(f'(\alpha_5)=0\).

이제 \(f'\)의 근은 \(0\)과 \(\alpha_5\)임이 확정되었다. 다른 근은 존재하지 않는다.

그러므로, \((0,\alpha_5)\)에서 \(\sin f(\alpha) = \pm 1\)인 모든 \(\alpha\)는 극대/극소점이다. 

이 점들은 \(f'(\alpha) \neq 0\)을 만족하므로, 그 점에서 \(\cos f(\alpha)\)의 부호가 변하기 때문이다.

또한, 극대/극소점 \(\alpha_2, \alpha_3, \alpha_4\)에서는 모두 \(\sin f(\alpha) = \pm 1\)이 된다. 

마지막으로, \(f\)는 구간 \([0,\alpha_5]\)에서 감소함이 확정되었다. 

그러므로 \(f(\alpha_2) = -\frac{\pi}{2}\), \(f(\alpha_3) = -\frac{3\pi}{2}\), \(f(\alpha_4) = -\frac{5\pi}{2}\)를 얻을 수 있다. 

이제 \(f(\alpha_5)\)를 구할 수 있다. \(\alpha_5 < -\frac{7\pi}{2}\)라면, \(-\frac{7\pi}{2}\) 역시 극대/극소점이 되므로 모순이다. 

그러므로 \(f(\alpha_5) \in (-\frac{7\pi}{2}, -\frac{5\pi}{2})\)이고, \(f(\alpha_5)= -\frac{17}{6} \pi\)를 얻을 수 있다. 

\(\alpha_5 = t\)라고 편의상 두자. 그러면 \(f'(x)=18\pi x(x-t)\)가 된다. 이를 적분하면, \(f(0)=\frac{\pi}{6}\)이므로 \(f(x)=6\pi x^3 - 9\pi t x^2 + \frac{\pi}{6}\)이 된다. 여기서 \(x=t\)를 대입하면, $$ 6t^3 - 9t^3 + \frac{1}{6} = -\frac{17}{6} $$를 얻는다. 그러므로 \(t=1\)이고, \(f(x) = 6\pi x^3 - 9\pi x^2 + \frac{\pi}{6}\)이다. 

이제 남은 것은 계산이다. \(f'\left(-\frac{1}{2}\right) = \frac{27\pi}{2}\)와, \(f\left(-\frac{1}{2}\right) = -\frac{17}{6}\pi\)를 얻는다.

그러면 $$ g'\left(-\frac{1}{2}\right) = \frac{-\frac{27\pi}{2} \cdot -\frac{\sqrt{3}}{2}}{ \left(2 - \frac{1}{2} \right)^2} = 3 \sqrt{3} \pi$$를 얻고, 답은 \((3\sqrt{3})^2 = 27\)이 된다. 

문제 (완벽하게 동일한 statement가 아닐 수 있음)

1 - (1) 다음의 조건을 만족하는 집합 \(A, B, C\)를 고르는 방법의 수는?

조건 1. \(A, B, C\)는 \( \{1,2,3,4,5,6\}\)의 부분집합으로, \( A \cup B \cup C = \{1,2,3,4,5,6\} \)이다.

조건 2. \( n( A \cap B) =2\)이고, \( n(A \cap C)=1\)이다. 

1 - (2) 다음의 조건을 만족하는 집합 \( D, E\)를 고르는 방법의 수는?

조건 1. \(D, E\)는 \( \{7,8,9\} \)의 부분집합으로, \( D \cup E = \{ 7, 8, 9 \} \)이다. 

조건 2. \( n(D) > n(E) \ge 1\)이다. 

2. 다음 조건을 만족하는 함수 \(f\)가 있으면 찾고, 없다면 없음을 보여라.

조건. \(f\)는 \([0,1]\)에서 연속이며, \(f(0)=1\)이다. 또한, 다음이 성립한다. 

$$ \int_0^1 f(x) dx = \int_0^1 xf(x) dx = \int_0^1 x^2f(x) dx = 0$$

________________________________________________________________________________________________________________________

풀이 및 후기

오전 맨 마지막으로 면접을 봤다. 기다리느라 너무 지루했고 피곤했다. 컨디션 떡락 ㅠㅠ

조금 떨린 상태로 문제지를 열었다. 1번은 무난해 보이고, 2번이 변별력이 있어 보였다. 

2번을 읽는데... 이거 완전 https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process 아니냐???

(추가설명) 이걸 알면 삼차함수로 답을 구할 수 있다는 것이 자명해진다. \( 1, x, x^2, x^3\)으로 그램슈미츠 돌리면 답이 나오니까.

아니면 이거 완전 https://en.wikipedia.org/wiki/Legendre_polynomials 아니냐???

(추가설명) 이걸 알면 문제의 답을 아는 것과 마찬가지다. \(P_3(x)\)를 적당히 평행이동/상수배하면 된다.

결국 \( f(x)=x^3+ax^2+bx+c\)를 잡아주고, 적분값이 모두 \(0\)이 되도록 하는 \(a, b, c\)를 계산했다.

이를 계산하는 것은 그냥 연립일차방정식을 세워서 풀어주면 된다. 더럽지만 어쩔 수 없음. 

실제로 식을 세워주면, 다음 세 식을 어렵지 않게 얻을 수 있다. 

$$ \frac{1}{4} + \frac{a}{3} + \frac{b}{2} + c = 0 $$

$$ \frac{1}{5} + \frac{a}{4} + \frac{b}{3} + \frac{c}{2} = 0 $$

$$ \frac{1}{6} + \frac{a}{5} + \frac{b}{4} + \frac{c}{3} = 0 $$ 

\(a, b, c\)가 계산되면, \(f(0)=1\)을 만족하도록 상수배를 해주기만 하면 된다. 이 부분 계산은 생략. 

그렇게 하면 \(f(x)=-20x^3+30x^2-12x+1\)일 경우 주어진 조건이 모두 만족됨을 알 수 있다. 여기까지 7분 소요.

기분이 좋은 상태로 1번을 잡았고, 실제로도 무난한 확통 문제임을 알 수 있었다. 

1-(1)은 \( n(A \cap B \cap C)\)에 대하여 경우를 나눠서 해결할 수 있다. 벤 다이어그램을 그리는 것이 도움이 된다. 

만약 \( n (A \cap B \cap C) = 1\)이라면, 다음이 만족되어야 한다. 

1. \( A \cap B \cap C\)에는 원소가 하나 있어야 함.

2. \( A \cap B \cap C^C\)에는 원소가 하나 있어야 함.

3. \( A \cap B^C \cap C\)에는 원소가 없어야 함.

4. 나머지 원소들은 \( A \cap (B \cup C)^C\), \(B \cap (C \cup A)^C\), \(C \cap (A \cup B)^C\), 또는 \( B \cap C \cap A^C\)에 속해야 함.

1에 해당하는 원소 고르는 게 \(6\)가지, 2에 해당하는 원소 고르는 게 \(5\)가지, 4에서 배치하는 게 \(4^4\)가지. 총 \(7680\)개.

만약 \( n (A \cap B \cap C) = 0 \)이라면, 다음이 만족되어야 한다. 

1. \( A \cap B \cap C\)에는 원소가 없어야 함.

2. \( A \cap B \cap C^C\)에는 원소가 두 개 있어야 함.

3. \( A \cap B^C \cap C\)에는 원소가 한 개 있어야 함.

4. 나머지 원소들은 \( A \cap (B \cup C)^C\), \(B \cap (C \cup A)^C\), \(C \cap (A \cup B)^C\), 또는 \( B \cap C \cap A^C\)에 속해야 함.

2에 해당하는 원소들 고르는 게 \(\binom{6}{2}=15\)가지, 3에 해당하는 원소 고르는 게 \(4\)가지, 4에서 배치하는 게 \(4^3\)가지. 총 \(3840\)개.

이 둘을 합치면 답은 \(7680 + 3840 = 11520\)임을 알 수 있다. 

1-(2)는 \(n(D)\)에 관해 경우를 나눠서 쉽게 풀 수 있다. 

\(n(D)\)가 3이면, \(D\)는 유일하게 결정되고 \(E\)는 크기가 1 또는 2인 부분집합이면 되니까 총 6가지 경우가 나온다.

\(n(D)\)가 2면, \(E\)는 크기가 1인 집합이고 \(D \cup E = \{7,8,9\} \)가 성립하니 \(D\)만 결정하면 \(E\)가 자동 결정되어 총 3가지.  

그래서 이 둘을 합치면 답은 \(6+3=9\)임을 알 수 있다. 여기까지 13분 소요. 나머지 7분은 검산했다. 

발표는 작년처럼 종이 주고 여기에 풀이를 적고 보여주면서 설명하라고 하셨다. 

함수 \(f\)의 형태를 보여주거나, 벤 다이어그램을 그려서 보여주는 용도로 적당히 사용했다.

시간이 좀 남아서 2번에 대한 추가설명으로 Gram-Schmidt 직교화에 대하여 가볍게 언급했다. 

총평하자면 1번은 쉽고, 2번은 어려웠다. 분위기를 보니 수학과 지원하는 친구들이 2번을 꽤 푼 것 같다. 

2번 문제는 연대가 좋아하는 스타일의 함수 찾기 문제였고, 특히 수학에 대한 직관이 뛰어난 친구들이 잘 풀 것 같다. 

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점 마무리.

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