나는 코더다 2018 송년대회

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 하는 것은 그렇게 어렵지 않다. 아래는 내가 사용한 예시다.