rkm0959

스코어보드

우여곡절 끝에 5등으로 첫 ICPC를 마무리했다. A Bus With No Drivers 팀으로 bjwj5505, junie, rkm0959가 한 팀이다.

예상보다는 훨씬 좋은 성적으로 대회를 끝냈지만, 여러 아쉬움도 남는 대회였다.

서울대학교가 top 6팀 중에 5개라는 것도 참 신기하다.

대회에서 우리 팀이 문제를 푼 과정을 대략 복기를 해보면,

• 시작하자마자 bjwj5505가 J를 잡고, K를 나한테 넘겼다. 
• J에 대한 추측을 기반으로 답안 제출 + WA
• junie가 A가 쉽다고 해서 A를 짜서, 맞았다. 8분. 
• junie B 읽기 시작.
• 나는 EFG를 읽었는데 하나 같이 어려워보였다. H를 읽었는데 금광 문제와 똑같았다. 
• 반복되는 J 뇌절
• 그런데 알고보니 뒤에 있는 I, L번이 많이 풀려있었다. 
• bjwj5505 L로 이동, junie B 놓고 I로 이동
• I, L 풀이는 금방 나왔다
• H, I, L 코딩을 동시다발적으로 해서 각각 41, 57, 51분에 맞았다. I는 1틀.
• junie는 다시 B로, 나는 아까 읽은 K로, bjwj5505는 뇌절했던 J로 이동.
• bjwj5505가 J에 대한 추측을 수정하면서 73분에 해결했다. bjwj5505는 D로 이동.
• 나는 K에 대한 내 추측에 확신이 있었고, bjwj5505도 동의했다. 바로 짜서 90분에 해결했다.
• bjwj5505가 D에 대한 추측과 알고리즘을 완성했다. 하지만 WA.
• junie는 B 식을 짰지만 답이 잘 나오지 않았고, 내가 B로 가서 같이 DP 식과 코드를 고쳤다.
• B를 int/ll 문제로 한 번 WA를 받고, 127분에 맞았다. 
• D 코드를 같이 봤지만 문제가 없어보였다. 3번 WA를 받고 잠시 D에서 손을 놓기로 했다.
• G를 같이 읽었는데, bjwj5505가 그냥 풀어버렸다. 코드 디버깅은 같이 했다. 
• 1 WA를 받은 뒤 193분에 AC를 받았다.
• D에 대한 확신을 많이 잃은 뒤라, F를 읽자는 의견이 나왔다.
• 기하가 너무 빡세보여서 나는 D를 어떻게든 잡고 싶었다. stress를 돌리자는 의견이 나왔다.
• 내가 전탐색으로 최소 막대기 개수를 구하는 코드를 짰다. (Dnaive.cpp)
• 내가 우리 코드가 정당한 답을 내는지 확인하는 코드를 D.cpp에 추가했다.
• junie가 테스트 제너레이터를 짰다. (Dgen.cpp)
• junie가 stress test 코드를 짰다. (Dstress.cpp)
• 돌렸더니 금방 반례가 나왔다. 로직의 문제도 곧 나왔다. 
• 로직의 문제를 해결하는 코드를 냈는데, TLE를 예상했지만 바로 AC. 263분에 D를 맞았다.
• 남은 문제는 너무 어려워보여서 던졌다. C, F가 할 만한 문제인줄은 몰랐지 ㅋㅋ
• 끝나고 Ternion 팀하고 같이 술과 고기를 먹었다.

개인적으로 아쉬운 점: 후반부에 루즈해지는 것은 여전한 것 같다. bjwj5505가 G를 짤 때 C나 F를 제대로 봤어야 했다.

개인적으로 잘한 점: 푼 문제는 둘 다 원샷으로 끝냈고, K를 빠르게 풀어낸 것도 잘한 것 같다. 뇌절은 안 한듯.

풀이는 추후에 추가.

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

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

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

팀: 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)\)이다.