JAG Summer Camp 2018 Day 2

너무 수학 셋이다. 하지만 수학 문제 기준으로는 퀄리티가 높은 문제를 풀 수 있었다.

JAG Summer Camp 2018 Day 2 E Self-Contained

좋은 집합의 조건이 무엇인지를 먼저 판별해보자. 가장 typical한 것은 역시 \(0, a, 2a, 3a, \cdots \)다. 

좋은 집합 \(X\)를 생각하자. 일단 최대 원소 \(M\)을 잡으면, 문제 조건에서 \(2M\) 또는 \(0\)이 \(X\)에 속한다.

결론적으로 \(M=0\)이거나, \(0 \in X\)를 얻는다. 이건 어쨌든 \(0 \in X\)라는 뜻이다. 이제 \(X\)의 원소를 \(0, x_1, x_2, \cdots , x_n\)이라 하자. 

그러면 문제 조건에서 \(x_n-x_1, x_n-x_2, \cdots , x_n-x_{n-1}\)이 전부 \(X\)에 속해야 한다.

그런데 \(0<x_n-x_{n-1}<x_n-x_{n-2} < \cdots < x_n-x_1<x_n\)이니까, \(x_n=x_i+x_{n-i}\)가 전부 성립함을 알 수 있다.

비슷하게, \(x_{n-1}-x_2, x_{n-1}-x_3, \cdots , x_{n-1}-x_{n-2}\)를 생각할 수 있다. 

이를 반복하다 보면, 결국 \(x_i\)들이 앞에서 언급한 'typical한 경우'가 됨을 알 수 있다. 그런데 한 가지 예외 케이스가 발생한다.

\(X\)의 원소가 \(0, a, b, a+b\)인 경우가 조건을 만족함을 알 수 있다. 이 경우를 따로 처리해야 한다.

'typical한 경우'는 간단하게 \(\mathcal{O}(n \log n)\)에 계산할 수 있다. 예외 케이스는 FFT를 활용하여 어렵지 않게 \(\mathcal{O}(n \log n)\)에 계산할 수 있다. 

개인적으로는 재밌는 문제였다. 비슷한 문제를 수학 올림피아드에서 본 것 같은데 어디서 봤는지는 모르겠다.

JAG Summer Camp 2018 Day 2 G Construct One Point

일단 이 문제가 내가 최근에 Project Euler에서 푼 문제들보다는 좋은 것 같다. 재밌는 문제.

우리가 쉽게 계산할 수 있는 것에 어떤 것이 있는지를 먼저 생각해보자. 사전지식 점검이라고 볼 수 있다.

1. 주어진 선분 위에 (끝점 제외) 격자점이 몇 개 있는지를 셀 수 있고, 그 예시도 구할 수 있다. 이는 GCD만 알면 된다.

2. 삼각형의 넓이를 쉽게 구할 수 있고, 그 boundary 위에 놓인 격자점의 개수를 쉽게 셀 수 있다. 

3. 그러니, Pick's Theorem에 의하여, interior에 놓인 격자점의 개수를 쉽게 셀 수 있다. 즉, 답이 있는지 판별은 쉽다.

4. 물론, 특정 격자점이 삼각형 내부에 놓이는지 확인하는 것도 단순한 기하로 할 수 있다. 즉, 답이 맞는지 판별은 쉽다.

첫 번째 아이디어는, 삼각형을 더 작은 삼각형으로 쪼개는 것이다.

삼각형 \(\triangle ABC\)에서 \(BC\) 위에 (끝점 제외) 격자점 \(D\)가 있다고 하자.

그러면 선분 \(AD\) 위에 (끝점 제외) 격자점이 있는지 판별할 수 있고, 있다면 이를 답으로 찍으면 끝난다.

그렇지 않다면 \(\triangle ABD\) 내부 또는 \(\triangle ACD\) 내부에 격자점이 있어야 한다.

격자점 존재 여부는 판단하기 쉬우니, 격자점이 있는 쪽으로 탐색을 줄이면 될 것이다. 

\(D\)가 \(BC\)의 중점에 가깝도록 설정하면, 탐색하는 곳의 넓이가 대강 절반씩 줄어들 것이다.

이 과정을 당연히 각 변에 대해서 반복해가면, 답을 찾는데 성공하거나 \(AB, BC, CA\) 위에 (끝점 제외) 격자점이 없는 상태까지 줄일 수 있다. 

여기까지 로그 제곱의 기간이 걸린다. 이는 물론 각 단계에서 gcd를 계산해야 하기 때문이다.

 

답을 찾지 못했다면, \(AB, BC, CA\) 위에 (끝점 제외) 격자점이 없는 상태에 도달했다는 것이다.

일반성을 잃지 않고, \(AB\)가 가장 긴 변이라고 가정하자. 이제 핵심 결론을 제시한다.

직선 \(AB\)에 '가장 가까운 점' 중 하나가 무조건 삼각형 내부에 들어오게 된다. 

물론, 이 가까운 점이 \(AB\) 기준 위에 있는지 아래에 있는지를 확인하려면 CCW 등의 계산을 해야 한다.

\(AB\)에 가장 가까운 점을 계산하는 것은 어렵지 않게 extended euclidean algorithm으로 할 수 있다.

이제 답을 찾는 것도 크게 어렵지 않다. 적당히 '가장 가까운 점'을 보면서 답이 맞는지 판별하면 되기 때문이다.

가장 가까운 점이 삼각형 내부에 들어오게 된다는 것은, Stern-Brocot Tree를 생각하면 어렵지 않다.

대충 생각하면, 가장 가까운 점이 삼각형 내부에 들어오지 못하도록 \(C'\)을 잡으려면 \(AC'\) 또는 \(C'B\)의 기울기가 굉장히 작은 interval 안에 들어가야 하고, Stern-Brocot Tree의 원리에서 그 interval 안에 들어가려면 \(AC'\) 또는 \(C'B\)의 길이가 \(AB\)보다 커진다는 것을 증명할 수 있다. 디테일은 생략.

지금 생각하는 건데, '가장 가까운 점'에 대한 추측을 하면 이분탐색 + 변 기준 CCW로도 해결할 수 있을 것 같다. 

그런데 이걸 쉽게 하려면 (아마) __int128이 필요할 것이다. Atcoder에서 __int128을 지원하는지는 모르겠다.

JAG Summer Camp 2018 Day 2 K Short LIS

LIS가 2 이하라는 것은, 123-avoiding permutation이라는 것이다. 편의상 \(1\)-index로 문제를 풀자.

123-avoiding permutation 문제에서 경우의 수를 세라는 것은, 대충 카탈란 수에 대한 사전지식을 필요로 한다는 것이다.

123-avoiding permutation과 dyck path (즉, \((0,0)\)에서 \((n,n)\)까지 \(y=x\)를 뚫지 않고 가는 경로) 사이의 대응을 알아야 한다.

123-avoiding permutation \(p_1, p_2, \cdots , p_n\)이 있다고 하자. 이를 오른쪽에서 왼쪽으로 차례대로 볼 준비를 하자.

오른쪽에서 왼쪽으로 가면서, 지금까지 본 "역대 최대"를 기록하자.

"역대 최대"의 index가 순서대로 \(n=x_1 > x_2 > \cdots > x_k\)라고 하고, 그때의 값을 \(y_1 < y_2 < \cdots < y_k = n\)이라고 하자.

핵심 관찰은, "역대 최대" 사이의 "블록"들은 무조건 감소한다는 사실이다.

이게 뭔 뜻이냐면, 주어진 permutation이 \([x_2+1, x_1-1]\), \([x_3+1, x_2-1]\) 등에서 감소한다는 것이다.

만약 \(i, j \in [x_2+1, x_1-1]\)가 있어 \(i<j\)고 \(p_i < p_j\)라면, \(p_i < p_j < p_{x_1}\)이므로 123-avoiding에 모순이다.

또한, 예를 들어 \(i \in [x_3+1, x_2-1]\), \(j \in [x_2+1, x_1-1]\)이고 \(p_i < p_j\)라면, 마찬가지 이유로 123-avoiding에 모순이다.

즉, "역대 최대"로 찍힌 친구들을 제외하면 전부 다 감소한다. 이건 굉장히 중요한 사실이다.

이제 123-avoiding permutation과 dyck path 사이의 일대일대응을 설계할 준비가 끝났다.

\((0,0)\)에서 시작해서, \((y_1, 0)\)까지 가자. 그런 다음, \((y_1, n-x_2)\)까지 쭉 올라가자.

그 다음, \((y_2, n-x_2)\)까지 간 다음 \((y_2, n-x_3)\)까지 쭉 올라가자. 이를 반복해서 \((n,n)\)까지 가자.

이게 dyck path임을 증명하는 것은 어렵지 않다. 또한, 이게 일대일대응임을 증명하는 것도 어렵지 않다.

\(x_1, x_2, x_3, \cdots, x_k , y_1, y_2, \cdots , y_k\)를 결정하면 123-avoiding permutation 자체가 결정되기 때문이다.

추가: 위 논의를 정리하면 결국 123-avoiding permutation이 2개의 감소 수열로 분할된다는 것이다.

이건 사실 Dilworth's Theorem의 입장에서 보면 매우 당연한 사실이다. 이 글의 G번을 참조하자. 

이제 본격적으로 주어진 문제를 풀어보자. \(a, b\)를 전부 \(1\)-index로 바꾸자.

만약 \(a+b < n+1\)이라면, \(a\)를 \(n+1-a\), \(b\)를 \(n+1-b\)로 바꿔주자. 

이것이 가능한 이유는, \(p_1, p_2, \cdots , p_n\)을 \(n+1-p_n, n+1-p_{n-1}, \cdots , n+1-p_1\)으로 뒤집을 수 있기 때문이다.

그런데 \(a+b \ge n+1\)이면, \(p_a=b\)는 "역대 최대"일 수 밖에 없다.

"역대 최대"가 아니라면, \(1, 2, \cdots , b-1\) 전부와 \(b\)보다 큰 값 적어도 하나가 \(p_{a+1}, p_{a+2}, \cdots p_n\)에 들어있어야 한다.

이는 \(n-(a+1)+1 = n-a \le b-1\)이므로 모순이다. 

즉, dyck path의 입장으로 보면 우리의 dyck path는 \((b-1, n-a)\)에서 \((b, n-a)\)로 이동한 뒤, \((b, n-a+1)\)로 올라가는 경로다. 

이 path는 크게 세 단계로 쪼개서 볼 수 있다. 

단계 1에서는 \(y=x\) 위를 뚫지 않고 \((0,0) \rightarrow (b-1, n-a)\)을 한다.

단계 2에서는 \((b-1, n-a) \rightarrow (b, n-a) \rightarrow (b, n-a+1)\)을 한다.

단계 3에서는 \(y=x\) 위를 뚫지 않고 \((b, n-a+1) \rightarrow (n, n)\)을 한다.

이 세 단계는 각각 독립적이다. 그러니, 단계 1, 단계 3으로 고를 수 있는 path의 개수를 세면 된다.

또한, 단계 3의 path는 \(y=x\) 위를 뚫지 않고 \((0,0) \rightarrow (a-1, n-b)\)를 하는 path와 쉽게 대응이 된다.  

즉, \(y=x\) 위를 뚫지 않고 \((X, Y)\)로 가는 (단, \(X \ge Y\)) path의 개수를 셀 줄 알면 된다.

이는 매우 유명한 "대칭" 테크닉으로 쉽게 계산할 수 있다. \(y=x\) 위를 뚫는 path는 \(y=x+1\) 위의 점을 지난다.

path와 \(y=x+1\)의 첫 번째 교점을 잡고, 그 이후의 path를 \(y=x+1\)을 기준으로 대칭하자.

그러면 이는 \((Y-1, X+1)\)으로 가는 경로와 일대일대응됨을 알 수 있다. 즉 답은 \(\binom{X+Y}{X} - \binom{X+Y}{X+1}\)이다.

여담: 계산해야 하는 factorial의 개수가 \(\mathcal{O}(1)\)이라, 이 문제를 쓰면 더 빠르게 풀 수 있다. ㅋㅋ!