rkm0959

관련 코드는 github에서 찾아볼 수 있다.

여기서는 잘 알려진 사실들부터 시작해서, 나중에 중요해질 수학적 사실들을 다룬다.

사실 1단원과 2단원 앞 유클리드 알고리즘만 알아도 퍼플/오렌지에 영향은 없다.

잘 알려진 사실들은, 매우 간단하게만 설명하고 스킵하자. 이미 좋은 자료/블로그가 많으니, 이를 참고하는 것 추천.

다음 사실은 유명하다 : 정수 $a, b$가 있고 $b \neq 0$일 때, $a = bq + r$이고 $0 \le r < |b|$인 정수 $q, r$이 유일하게 존재한다.

이때, $r$을 "$a$를 $b$로 나눈 나머지"라고 정의한다. 만약 $r = 0$인 경우, $a, b$는 서로 약수/배수 관계에 있다고 하며, $b|a$라 쓴다.

이를 통해서 공약수/공배수 개념을 정의할 수 있으며, 나아가 최대공약수/최소공배수의 개념을 정의할 수 있다.

자연수 $n \ge 2$가 각 $2 \le k < n$에 대하여 $k \nmid n$을 만족하면, $n$을 소수라고 부른다. 소수가 아니면 (1 제외) 합성수라고 부른다. 

이를 통해서 소인수분해라는 개념을 정의할 수 있으며, 이는 유일하다는 것이 잘 알려져 있다.

소인수분해를 통해서, 자연수의 약수의 개수와 약수들의 합 등을 계산할 수 있음은 교육과정에도 있는 내용이다.

만약 두 정수 $a, b$가 $n$으로 나눈 나머지가 같다면, $a \equiv b \pmod{n}$이라고 쓴다. 이는 $n|(a-b)$와 같은 뜻이다.

또한, $a$를 $n$으로 나눈 나머지를 $a \pmod{n}$이라고 쓰기도 한다. 다음은 간단 Exercise.

• 정수 $a, b, n$이 $a \equiv b \pmod{n}$이고, $r$이 정수인 경우, 다음이 모두 성립함을 보여라.
• $a + r \equiv b+ r \pmod{n}$, $a - r \equiv b - r \pmod{n}$, $ar \equiv br \pmod{n}$.

즉, mod 연산을 취하는 과정에서도 평소처럼 사칙연산을 할 수 있다. 

나눗셈이 문제인데, 다음 단원에서 modular inverse가 나오면 나눗셈도 modular inverse를 양변에 곱하는 방식으로 할 수 있다.

이 시점에서, 알고리즘 문제를 몇 개 생각해볼 수 있다. 모두 이미 자료가 많으므로, 빠르고 간단하게 한다.

• 자연수가 소수임을 어떻게 판별할 것인가?
• 자연수의 약수의 개수를 어떻게 셀 것인가? 약수를 모두 찾으라고 한다면 어떻게 할 것인가?
• 자연수의 소인수분해를 어떻게 구할 것인가?
• 1부터 $n$까지의 소수를 어떻게 셀 것인가/찾을 것인가?

첫 세 문제에 대해서는, $\mathcal{O}(\sqrt{n})$ 알고리즘이 잘 알려져 있다. 핵심 아이디어는,

• 자연수 $n$이 $2$ 이상 $\sqrt{n}$ 이하 모든 자연수에 의해 나누어떨어지지 않는다면, $n$은 소수다.
• 이유: 소수가 아니라면 $n = ab$이며 $1  < a , b < n$인 자연수 $a, b$ 존재. 둘 다 $\sqrt{n}$보다 크다면 $ab > n$.

이 핵심 아이디어로 세 문제를 해결해보자.

• 소수 판별: $2$ 이상 $\sqrt{n}$ 이하 모든 자연수에 대해 나누어떨어짐을 판별하면 끝.
• 약수 세기/찾기: $a$가 $n$의 약수면 $n/a$ 역시 $n$의 약수. 둘 중 하나는 $\sqrt{n}$ 이하고 하나는 $\sqrt{n}$ 이상이니, $\sqrt{n}$ 이하 약수만 찾으면 모든 약수를 알 수 있다.
• 소인수분해: $2$ 이상 $\sqrt{n}$ 이하 모든 자연수를 순서대로 보자. 현재 보고 있는 자연수 $i$가 $n$의 약수라면, $n$이 $i$의 배수가 아닐 때까지 $n$에서 $i$를 나누어준다. 나누어주는 횟수를 저장하는 것은 당연. 만약 iteration이 끝났을 때, $n$이 $1$이면 그대로 끝. 아니면 남은 $n$ 역시 소수이며, 기존 $n$의 소인수가 된다. 

마지막 문제는 "에라토스테네스의 체"로 잘 알려져 있는 결과다.

• 에라토스테네스의 체: 2부터 $n$까지 순서대로 보면서, 합성수인 것을 지워내자. 만약 지금 보는 값 $p$가 지워지지 않았다면, $p$는 소수다. 
• 이제 $p$의 배수를 ($p$는 빼고) 전부 지워내자. 이걸 반복하면 남는 것은 전부 소수. 예시를 인터넷에서 찾아보면서 이해해보자. 

에라토스테네스의 체는 활용 방법이 굉장히 많다. 다음을 할 수 있는 방법을 생각해보자. 해답은 github에 있다.

• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 가장 작은 소인수"를 계산하는 법
• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 서로 다른 소인수 개수"를 계산하는 법
• 오일러 파이 함수. $n$의 소인수분해가 $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$일 때, $\phi(n) = n \cdot \frac{p_1 - 1}{p_1} \cdots \frac{p_k-1}{p_k}$라 정의하자. 이 값을 모두 계산하는 법.
• 조금 더 난이도가 있지만, "약수의 개수"와 "약수의 배수" 역시 전처리 할 수 있다.

여기서 강력한 결과를 하나 얻을 수 있다.

• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 가장 작은 소인수"를 미리 전처리했다고 가정하자.
• 이제 $2 \le m \le n$인 자연수 $m$의 소인수분해를 원한다고 가정하자. 
• $m$에서 시작해서, "가장 작은 소인수"를 나누어주는 과정을 반복하자. 한 번에 값이 반 이상 줄어드니, 로그 시간에 소인수분해 끝.

에라토스테네스의 체를 사용하면 $1, 2, \cdots , n$ 각각이 소수인지 전부 빠르게 판별할 수 있다.

하지만 꼭 $1$부터 시작할 필요는 없다. $A+1, A+2, \cdots , A+n$ 각각이 소수인지 빠르게 판별할 수는 없을까?

• $2$부터 $\sqrt{A+n}$까지의 수를 순서대로 보자. 현재 보고 있는 수를 $k$라고 하자.
• $A+1, A+2, \cdots , A+n$에 속한 $k$의 배수 중 $k$가 아닌 것을 전부 제거하자. 남는 것은 전부 소수이다.
• 시간복잡도는 어떻게 될까? 각 $k$에 대하여 제거되는 수의 개수는 $\mathcal{O}(n/k)$개이다.
• 이를 $k$를 $2$부터 $\sqrt{A+n}$까지 돌면서 더하면, 아래에서 다룰 Harmonic Sequence에 대한 성질에 의해 총 $\mathcal{O}(n \log n)$이 된다.
• 그러니 $k$에 대하여 for문을 돌리기 위해 필요한 시간 $\mathcal{O}(\sqrt{A+n})$을 더하면, $\mathcal{O}(\sqrt{A} + n \log n)$이라는 결과를 얻는다.
• 에라토스테네스의 체의 다양한 활용 방법을 이 방식에서도 그대로 적용할 수 있다.

참고할 점은, 위의 에라토스테네스의 체가 하는 일을 $\mathcal{O}(n)$에 하는 방법이 존재한다는 것이다.

• Linear Sieve라고 하는 테크닉이다. 이를 위해서는 ahgus89님의 이 자료나, 원본이라고 할 수 있는 이 글을 보자.
• 이후에 다룰 multiplicative function에 대한 글을 읽고 다시 위의 자료를 읽는 것이 이해하기 편할 수 있다.
• 이 가이드에서 굳이 Linear Sieve를 설명하지 않는 이유는, 필자도 Linear Sieve가 필요할 정도로 시간제한이 빡빡한 문제를 본 적이 없기 때문이다.
• 이 외에도, 에라토스테네스의 체는 다양한 최적화 방법이 있다. 개인적으로는 필요한 문제를 본 적이 없었다. 필요하면 나쁜 문제라는 것이 내 생각.
• 당연하지만, 이러한 체 최적화 방법을 알아둬서/팀노트에 넣어서 나쁠 것은 없다. 나중에 관심이 생기면 보는 것으로.

이제 여러 수학적 사실들을 빠르게 다룬다. 중요해지는 때가 온다.

• [매우 중요] 자연수 $n$에 대하여, $\lfloor n/1 \rfloor, \lfloor n/2 \rfloor, \cdots, \lfloor n/n \rfloor$ 중 서로 다른 것은 $\mathcal{O}(\sqrt{n})$개이며, 효율적인 iteration도 가능. github 참조.
• 이유가 꽤 아름다우니 설명한다. $\lfloor n/1 \rfloor, \cdots , \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor$까지 서로 다른 것은 $\mathcal{O}(\sqrt{n})$개. (항 개수가 애초에 $\mathcal{O}(\sqrt{n})$개이므로)
• $\lfloor n / \lfloor \sqrt{n} \rfloor \rfloor, \cdots ,\lfloor n/n \rfloor$까지 서로 다른 것도 $\mathcal{O}(\sqrt{n})$개. (값들이 전부 $\mathcal{O}(\sqrt{n})$ 이하이므로)
• 위 github 코드의 iteration 방법의 원리가 궁금할 수 있을 것이다. 이것의 대한 설명은 ahgus89님의 이 글 참고.
• [매우 중요] Harmonic Sequence. 자연수 $n$에 대하여, $1/1 + 1/2 + 1/3 + \cdots + 1/n = \mathcal{O}(\log n)$.
• 7단원에서 언급하겠지만, 이를 통해서 $1$부터 $n$까지 약수의 개수 합이 $\mathcal{O}(n \log n)$임을 얻는다.
• 그러므로, 만약 필요하다면, $1$부터 $n$이 갖는 약수들을 std::vector 등 자료구조에 $\mathcal{O}(n \log n)$ 시간에 넣을 수 있다.
• 더욱 자세한 내용을 알고 싶다면, 7단원에서 "약수를 iterate 하는 것보다 배수를 iterate 하는 것이 쉽다"는 부분을 읽자.
• Merten's 2nd Theorem. 자연수 $n$에 대하여, $n$ 이하 소수들의 역수의 합은 $\mathcal{O}(\log \log n)$.
• Merten's 2nd Theorem으로, 에라토스테네스의 체의 시간복잡도를 파악할 수 있을 것이다. $\mathcal{O}( n \log \log n)$.
• 후반부의 내용에서, 은근슬쩍 자연수 $a, b, c$에 대하여 $\lfloor \lfloor a/b \rfloor / c \rfloor = \lfloor a/(bc) \rfloor$라는 식을 꽤 사용한다.

마지막으로, 모듈로 연산에 대해 잠깐 언급한다. 이 연산은 덧셈, 뺄셈에 비해서는 물론, 곱셈에 비해서도 느린 연산이다.

그러니, 모듈로 연산을 마구잡이로 사용하면 비효율적인 코드가 나오게 될 것이다. 이를 최적화하는 방법을 간단히 소개한다.

모듈로 연산 횟수를 줄이는 법

• 가능하면 진짜 나머지를 취하지 말고, 모듈러스를 더하고 빼는 것으로 대체한다.
• 예를 들어, $0 \le a < M$, $0 \le b < M$에 대해, $a+b \pmod{M}$을 계산하기 위해서 모듈로 연산을 쓰지 말자는 것이다.
• $a+b$를 계산한 다음, $M$보다 큰 경우 $M$을 빼는 것이 훨씬 효율적이다. 쉽고 확실한 최적화 방법이다.

모듈로 연산 자체를 빠르게 하는 방법

• 모듈로를 가능하면 const로 선언하자. 그러면 상당한 속도 개선을 확인할 수 있다.
• 이러한 고속화의 원리 중 하나는 Barrett Reduction이다. modulo 연산을 곱셈과 시프트 연산으로 대체한다.
• 자세한 내용을 알고 싶다면, 이 위키피디아 글과 이 min_25의 글을 확인하라.
• 어셈블리를 잘 아는 사람이라면 어셈블리를 이용할 수 있는 것으로 안다. 이 부분은 내가 모르니 생략. 이 링크를 보자.
• 관련 내용이 KAIST의 ICPC팀이었던 더불어민규당의 팀노트에도 있다. Fast LL Division/Modulo 부분을 보자.

PS를 위한 정수론 가이드를 쓰기로 했다. 이유는 여러 가지.

• 자료가 부족하다는 의견을 많이 듣고, 동의함
• kipa00님의 NTA가 매우 좋은 자료인 것은 맞지만, 진입장벽이 상당하다
• 수학적 직관이나 엄밀한 증명을 일부 포기하더라도 내용을 간결하게 전달하는 것이 필요한 것 같다
• (나중에 직관/증명이 필요하다면, 그 때 직접 자료를 찾으면 된다. 처음 들이박는 것보다 쉬울 것)
• 그래서 최대한 문제 풀이에 집중하는 가이드가 필요하다고 생각했다
• 그러나, 각 알고리즘의 기본 원리 정도는 배우고 갈 수 있도록 내용을 작성하였다.
• (목표는 PS 정수론을 입문하기 위해 책을 폈다가 수학적 귀납법부터 시작하면서 의지를 잃는 사람들을 배려하는 것) 

이론 설명은 여기에 간단하게 하고, 관련 코드를 github에 올릴 계획. git 연습도 해야하니. 

연습문제도 올릴 예정인데, 이건 천천히 할 생각이다. 초반 주제들은 solved.ac에 관련 태그가 많으니 활용하자.

글을 읽다보면 뭔가 논리에 빈 공간이 있다는 생각이 들 수도 있다. 정수론 책을 그대로 옮기고 싶지 않아서 그런 것이다.

논리의 허점에 아쉬움을 느끼는 때가 오면, 학부용 정수론 책을 사서 읽으면 도움이 될 것이다. 위에서도 말했지만..

(+ 당연한거지만 학부 정수론을 모르는 상태로 어려운 문제를 풀려고 하면 한계가 올 것이다. 그때 필요하면 책을 읽으면 된다. 앞 몇 장만 읽어도 도움된다.)

일단 내용을 최대한 빠르게 퀄리티 신경 안 쓰면서 뽑아내고, 지적이나 제안을 받아가면서 천천히 보완할 생각이다. 

한 번에 완벽한 자료를 만들려고 하면 한 3~4단원하고 접을 가능성이 99.9%라서인데 사실 이게 더 나을수도 ㅋㅋㅋㅋ

가끔 오개념을 글에 쓰고 난 다음 나중에 고치는 일이 생길 수 있어, 글이 올라온 뒤 조금 시간이 지난 다음 읽는 것을 추천한다.

추가적으로 해야하는 언급들

• 시간복잡도 분석은 빡빡하게 하지 않을 것이다. 본격적으로 시간복잡도를 논의하려면 정수 덧셈도 로그 시간이라는 내용들을 녹여내야한다. 하지만 PS/CP에서 이렇게 시간복잡도를 분석하는 경우는 흔치 않으니, 여기서도 모든 덧셈과 곱셈은 $\mathcal{O}(1)$ 연산이라는 것으로 합의하자. 
• 비슷하게, $\mathcal{O}$ notation도 꽤 편안하게 (엄밀하지 않게) 사용할 것이다. 적당히 이해하고 넘어가자 :)
• 자료 수정/추가는 가끔 오류가 보이거나 필요가 생기면 할 것이다. github에서도 수정이 많을 수 있다.
• github에 올라온 코드는 팀노트에 복붙해서 넣을 퀄리티가 아니라, proof of concept 정도로 보는 것이 나을 것이다.

solved.ac 기준. 1~3 및 5 초반은 플레 중하위권 이하, 4, 5 후반은 플레 중상위권, 6번은 플레, 7, 8은 플레 상위권, 9~11번은 다이아 이상.

예상 커리큘럼

1. 기본기 잡기
2. 유클리드, 확장 유클리드 알고리즘
3. 중국인의 나머지 정리
4. 페르마 소정리, 오일러 정리 및 활용
5. 팩토리얼과 이항계수
6. Miller-Rabin 소수 판별 알고리즘과 Pollard-Rho 소인수분해
7. Mobius function과 그 활용
8. 원시근, 이산로그, 이산제곱근
9. 유클리드 알고리즘의 활용
10. 소수의 개수 빠르게 세기
11. more on multiplicative functions
12. 개인적인 후기, 그리고 그 이후의 이야기

1단원은 이미 자료가 많은 부분을 다루어, 덜 친절할 예정이다. 이 부분은 다른 자료를 찾는 것을 추천한다.

UPD: 백준 문제집 - 6593번 ~ 6603번

질문은 댓글로 항상 환영 :) (나도 내가 설명을 쉽게 못하는 사람인 걸 안다)

그래도 후기를 쓰기는 해야 할 것 같아서 ㅋㅋㅋㅋㅋ 아쉽지만 작년에 비해서 좋은 결과가 나오지는 못했다. 이유는

• 작년처럼 팀연습을 10번 이상 열심히 굴리지를 않았음 (올해 팀연습 0회)
• 팀들이 작년보다 전반적으로 강해지고 센 팀들도 더 등장함
• 일단 내가 작년에 비해서 간절함이 없었음 (애초에 작년에 뽑은 성과가 너무 좋았음) 

그래서 솔직히 결과에 아쉬움이 있어도 "이거 이상을 바라면 그건 그거대로 양심 X"라고 생각하고 있다.

아쉽다고 쳐도 9등이면 동상이고 이정도면 꽤 깔끔한 CP 대회 마무리 아닐까 싶기도 하고 ^__^ 

• 열었더니 B가 쉬워서 빠르게 풀었음
• A가 풀이 자체는 쉽다는 콜이 나옴. C 문제 해석에서 약간의 뇌절
• E가 풀만하다는 콜과 G도 쉽다는 콜이 나옴. G에서 함정 빠짐
• E 맞추고 G는 계속 맞왜틀. J 풀이 나옴. H가 simple FFT인거 보고 바로 구현, AC
• C도 풀이 나오고 L 준비 시작. J 짜서 AC. G 다른 풀이도 짜봤는데 또 틀림.
• G 함정 발견 및 C 구현 후 C, G 모두 AC. L은 DnC 콜이 나왔는데 틀리는 중.
• L DM 돌리면서 틀린 이유 발견. Money For Nothing 생각하면서 풀이 고쳐서 맞음
• 이제 junie가 A 구현하면서 다른 풀 거 찾아 떠남. I 보는게 맞는 판단인데 F가 할만해보여서 (ㅋㅋ) 시작
• F 문제 잘못 이해해서 SCC 문제인줄 알았음 ㅋㅋ
• junie가 A를 개고통받으면서 결국 AC 성공. 8솔해서 대충 이정도면 그래도 나쁘지 않다고 생각했음
• F 예제 만들어보다가 결국 문제 이해를 못해먹겠다는 결론을 얻고 그대로 사망

이제 내년부터 ICPC 판 재밌어질텐데 팝콘각이나 열심히 재야겟다 ^____^

2등상을 받았다. 실제 실력에 비해 너무 높은 상이다.

UPD: 상금과 트로피까지 전달 받았다. 이제 수상 소감이 올라오면 끝인데 얼굴 팔릴 생각에 걱정이다 ㅜㅜ

UPD: 수상 소감까지 올라왔습니다. 얼굴도 팔렸네요 ㅋㅋ;

대회 과정

• 1번 열었더니 쉬워서 빠르게 풀었다. 새로고침하니 퍼솔 같아서 기분이 좋았음 ^~^
• 2번 열고 일단 SCC를 짤 줄 알면 $\mathcal{O}(m^2)$이 뚝딱임을 파악했다
• 그런데 뇌절해서 그 풀이가 $\mathcal{O}(nm)$인 것으로 착각을 했다.
• 아무튼 $\mathcal{O}(m^2)$ 풀이를 짜서 긁으려고 했는데 틀리더라. 멘붕 옴
• 나중에 내 풀이가 $\mathcal{O}(nm)$이 아님을 깨달았다. 그래서 목표를 $\mathcal{O}(nm)$ 풀이 찾는 거로 잡았다.
• 그러다가 문제에 오류가 있다는 공지를 받고, $\mathcal{O}(nm)$ 풀이 찾기에 착수했다.
• 풀이 자체는 빠르게 나왔는데, 2번 문제치고 너무 복잡해서 뇌절이었나 걱정했다.
• 그런데 2번 데이터가 수정된 이후에도 만점자가 4명 뿐이더라. 시간이 꽤 지난 것 치고 적은 수였다.
• 그래서 맞는 풀이라는 확신을 할 수 있었고. 빠르게 짜서 바로 AC. 5번째 솔브로 기억한다. 이때가 1시간 정도 지났을 때.
• 3번을 열었는데 일단 문자열에다가 드럽게 복잡한 것 같아서 일단 걸렀다. 전날에 연습을 좀 했는데 힘겨워서 ㅋㅋ
• 그래도 3번은 풀어야 한다고 생각을 했고, 그 전에 4, 5번에서 빠르게 긁을 수 있는 것을 긁어오는 게 좋다고 판단했다.
• 4번을 열었는데, 일단 마음 속으로 $\mathcal{O}(n^3 \log n \log MAX)$ 쯤 되는 풀이가 나왔다. 4-2까지 긁힐 것으로 예상했다.
• 짜는 것도 별로 어렵지 않아서 빠르게 짰는데, 예제 1이 안나오네? 사실 상당히 큰 가정을 기반으로 한 풀이였다.
• 예제가 안 나온다는 것은 가정이 틀렸다는 거고, 결국 간단하게 고치는 것 자체가 쉽지 않다는 것이다. 똑떨...
• 5번을 열었더니 뭔 이상한 트리가 튀어나와서 바로 걸렀다. 결국 소득 없이 3번으로 돌아왔다.
• 3번의 풀이 자체는 스트링 티피컬 짬뽕 국밥 든든 그 자체여서 빠르게 찾을 수 있었다. 문자열 관련 대비도 꽤 했고.
• 그런데 아무리 생각해도 코드가 300줄 뽑히게 생겨서 마음을 굳게 먹어야 했다. 다행히 이때도 2번 만점자 수가 20명인가 그랬다.
• 3번을 풀면 매우 큰 상을 받을 가능성이 높다고 생각해서, 뇌절하지 말자고 생각하고 짜기 시작했다
• 대충 한 파트 짜고 -> 스코어보드 확인하면서 안도하고 -> 한 파트 짜고 -> 안도하고를 반복
• 다 짰더니 에러가 조금 났는데, 인덱스 실수 하나여서 금방 고쳤다. 예제 나와서 제출했더니 한 방에 맞더라 ㅋㅋ
• 이때가 4시 15분. (3시간 15분 지났을 때) 이제 긁을 것을 찾아서 떠났고 5-1이 긁기 쉽다는 결론을 얻었다.
• 사실 긁기 별로 안 어려운데, 뇌가 극도의 흥분상태여서 뇌절도 꽤 해서 40분 정도 걸렸다. 이때가 5시.
• 4번을 긁으면 진짜 2등상에 못 박는 느낌이어서 무리를 좀 했다. 뚫으려고 별 짓을 다하다가 사망하고 패배를 인정했다. 

문제 풀이

1. 더도 말고 덜도 말고

매우 쉬운 문제. 백준에도 비슷한 문제가 많을 것으로 생각한다. std::map 사용하면 뚝딱.

2. 영원한 휴가

작년 2번에 비해서 상당히 난이도가 올라간 문제. solved.ac 기준 플레 1 ~ 다이아 5 정도라고 개인적으로 생각한다.

$\mathcal{O}(m^2)$ 풀이는 간단한데, 그냥 SCC를 모든 경우에 대해서 다 구해주면 된다. 이러면 섭테 2까지 긁힌다.

본 문제를 해결하려면 SCC를 압축하여 DAG를 만드는 과정을 생각할 필요가 있다. 이제 기존 간선 $u \rightarrow v$를 뒤집었다고 생각하자.

• $u, v$가 같은 SCC에 포함되었다면, 그 간선을 뒤집어서 SCC 크기가 증가하지는 않을 것이다. 그러니 무시해도 된다.
• $u, v$가 다른 SCC에 포함되었다면, DAG 상에서 $u$의 SCC에서 $v$의 SCC로 가는 간선이 있다는 것이다.
• 만약 이 간선을 뒤집는다면, 어떻게 될까? 만약 해당 간선이 $u$의 SCC에서 $v$의 SCC로 가는 유일한 경로라면, 무시해도 된다.
• 하지만 $u$의 SCC에서 $v$의 SCC로 가는 경로가 2개 이상이라면, $u$의 SCC와 $v$의 SCC "사이"에 있는 모든 SCC가 묶인다.
• 여기서 "사이"에 있다는 것은, $u$의 SCC -> ??? -> $v$의 SCC 형태의 경로가 존재하는 ??? 들을 의미한다.

이제 문제를 해결할 수 있다. SCC 압축 DAG를 만든 후, $dp[u][v]$를 $u$번 SCC에서 $v$번 SCC로 가는 경로의 개수가 0개인지, 1개인지, 아니면 2개 이상인지로 정의하자. 이 값은 DAG에서 위상정렬 DP를 하듯이 계산할 수 있으며, 시간복잡도는 $\mathcal{O}(nm)$이다. 이 값을 잘 계산해놓으면 위 관찰을 통해서 답을 얻는 것 역시 쉽게 할 수 있다. 구현을 효율적으로 해야 AC를 얻는다는 말이 있으니, 잘 구현해야한다. $dp$ 계산에서 오버플로우에 주의하자.

3. 회문인 부분 문자열

역시 작년에 비해 매우 어렵다. 다3 정도라고 생각. 복잡한 문제인 만큼 천천히 생각해보자. 해야 하는 것은

• 우선 회문인 부분 문자열을 전부 뽑아낸다.
• 그 중 조건을 만족하는 부분 문자열을 전부 뽑아낸다. (즉, 주어진 회문이 어떤 문자열에 포함되는지 판별해야 한다)
• 그 후, 그 부분 문자열들을 사전순으로 정렬해서 $k$번째 것이 무엇인지를 파악해야 한다.

이제 각 단계를 어떻게 할 수 있을지 생각해보자.

• APIO 2014 팰린드롬의 풀이를 생각하자. 길이 $n$ 문자열의 회문인 서로 다른 부분 문자열의 개수는 최대 $n$개다.
• 이 시점에서 $k$의 제한은 페이크임을 알 수 있다. 또한, 회문을 모두 뽑는 것은 Manacher 알고리즘으로 가능하다.
• 서로 다른 것을 뽑아냈는지를 확인해야 하는데, 이건 Rabin-Karp 해시로 가능하다. 충돌 안하게 모듈로 2개 적당히 잡자.
• 위 koosaga 블로그 링크의 설명을 보면 사실 이 부분을 이분탐색 없이 할 수 있는데, 당시에는 이분탐색까지 덮었다.

이러면 1단계가 끝난다. 여기까지 하고 한 번 예제 넣어서 잘 돌아가는지 확인했다. 이제 2단계.

• 어쨌든 후보들은 "특정 문자열의 부분문자열인 회문"들이다. 이제 이것들이 다른 문자열에도 포함되는지 확인해야 한다.
• 그러면 세 문자열을 합친 (사이에 이상한 문자 껴넣고) 새 문자열을 만든 후, Suffix Array + LCP + Segment Tree를 적용한다.
• 이 과정 자체는 꽤 티피컬한데 구현이 드럽게 힘들고 귀찮다. Suffix Array는 로그제곱으로 짜도 충분하다. 

이러면 2단계가 끝난다. 여기까지 하고 한 번 예제 넣어서 잘 돌아가는지 확인했다. 이제 마지막 단계.

• 이제 부분문자열을 사전순 정렬해야 하는데, 단순하게 Suffix Array 상으로 정렬하면 안된다. (why?)
• 제대로 정렬하려면 "이 회문을 prefix로 갖는 suffix 중 가장 Suffix Array에서 앞에 있는 것"을 찾을 필요가 있다.
• 이를 위해서는 또 한 번 LCP + Segment Tree + 이분탐색을 적용하면 된다. 겁나 귀찮은데 해야함
• 이제 회문들을 "SA 위치, 회문의 길이"라는 pair로 정렬하면 사전순 정렬이 됨을 확인할 수 있다. 끝.

가치가 있다고 생각해서, 디버깅 용 코드까지 전부 그대로 올린다. 

5. 돌 옮기기

5-1을 긁는 것은 어렵지 않다. 상태 전이를 전부 파악하고 union-find를 돌리면 된다.

상태 전이를 효율적으로 하는 게 약간 헷갈릴 수 있는데, 비트마스킹을 잘 활용하면 $\mathcal{O}(n \cdot 2^n)$ 풀이를 얻는다.

뇌절을 한 흔적이 진짜 많이 보이는 코드를 짰다. 알아서 잘 해독하시길 ^~^;;

매우 늦게 올린다. 결과는 6등으로, 예상보다는 매우 높았으나 여전히 만족스러운 결과는 아니었다. J를 풀지 못한것이 아쉬움.

작년의 팀과 멤버는 동일하다. rkm0959, junie, bjwj5505다. 내가 1년간 공부를 많이 한 건 맞지만, 정작 최근에는 CTF 참가 등으로 PS, CP에 집중하지 못해서 팀의 전체적인 실력이 강화된건지 퇴화된건지 좀 애매한 것 같다. 다른 팀원도 비슷하다. 일단 지금까지는 나쁘지 않게 하고 있는듯.

타임라인과 함께 간략한 설명을 붙이도록 하겠다. 모든 사람을 3인칭으로 명명하겠다.

• 시작하자마자 문제 12개 모두 출력
• 스코어보드 보니까 I가 0분컷으로 풀렸네? 진짜 쉽네?
• rkm0959가 바로 컴퓨터 잡고 AC (5분)
• 이때쯤 E도 퍼솔이 나왔고, 바로 rkm0959가 이어서 AC (8분)
• bjwj5505는 이때 L을 읽고 있었고, junie는 앞쪽 문제를 읽는 중.
• bjwj5505가 L을 구현했지만 WA 후 코드 프린트
• rkm0959는 G를 보면서 수학 문제라고 생각을 했으나 매우 어려워보여서 대기중
• 대신 K가 쉽다는 것을 확인하고, 풀이를 bjwj5505와 확인
• rkm0959가 H의 풀이를 찾고, 정당성을 bjwj5505와 확인 
• 그러다가 F가 쉬워보여서 rkm0959, junie가 해결 시도
• bjwj5505가 L을 디버깅하고 있으며, rkm0959가 K를 짜기 시작
• bjwj5505가 L을 고치고 AC (39분), rkm0959도 곧 K AC (46분)
• bjwj5505, junie가 F의 풀이를 찾는동안 rkm0959 H 구현
• F의 풀이를 찾고 AC (51분), H도 곧 AC (58분) - 1시간 6솔브 도달
• 정확하게 기억은 안나지만 junie가 느린 J 풀이를 찾았음 (로그 2개)
• 그러나 정확하게 풀이를 이해하고 있는 사람은 junie 혼자
• bjwj5505, junie는 A의 해결에 집중. rkm0959는 B가 DP임을 확인
• rkm0959가 D가 세그먼트 트리로 해결될 수 있는 문제임을 확인
• A, B, D의 동시다발적 구현 + WA + 디버깅 파티 후 전부 AC (115, 133, 149분)
• J를 고치려고 했고, "맞는" 풀이를 1분 전에 찾았으나 TLE. 똑떨....

1. 실력 맞추기

기본적으로 최적의 방식는 각 그룹을 실력 순으로 나열한 뒤 매칭시키는 것이다.

이제 $A$ 그룹의 사람 한 명의 실력을 바꾼다고 가정하자. 이때, 새로운 실력이 $B$ 그룹 중 한 사람의 실력과 일치하는 경우만 고려해도 무방하다.

이제 $A_i$를 $B_j$로 바꾼다고 가정하자. 만약 $i=j$라면, 공정도의 합은 $\sum_{k=1, k \neq i}^{n} |A_k - B_k|$다. 

만약 $i < j$라면, 공정도의 합은 $\sum_{k=1}^{i-1} |A_k - B_k| + \sum_{k=i+1}^j |A_k - B_{k-1}| + \sum_{k=j+1}^n |A_k-B_k|$가 된다.

만약 $i > j$라면, 공정도의 합은 $\sum_{k=1}^{j-1} |A_k - B_k| + \sum_{k=j+1}^i |A_{k-1} - B_k| + \sum_{k=i+1}^n |A_k-B_k|$이다.

이제 각 $i, j$에 대하여 저 값들 중 최솟값을 구하면 된다. 그런데 식의 형태가 상당히 부분합 느낌이 강하게 난다.

$i=j$인 경우는 $|A_k - B_k|$에 대한 부분합을 전부 계산하는 방식으로 처리할 수 있다. 

$i < j$인 경우에는 $-|A_i-B_i| + \sum_{k=i+1}^j (|A_k - B_{k-1}| - |A_k - B_k|) $의 최솟값을 구하는 것과 같다.

이는 최대 연속 구간합을 계산하는 방식과 동일하게 계산할 수 있다. $i$를 고정하고 최적의 $j$를 쉽게 구할 수 있기 때문이다.

$i >j$인 경우에도 동일한 접근이 가능하며, 쉽게 계산하려면 $A$ 배열과 $B$ 배열을 swap 한 뒤 위 경우를 그대로 적용해도 된다.

2. 고구마

$a_i + a_{i+1} + \cdots + a_j \le M$을 만족하면서, $a_i + a_{i+1} + \cdots + a_j$를 최대화하고 싶다.

부분합 배열 $ps_i = a_1 +a_2 + \cdots + a_i$를 만들면, 목표는 $ps_j - ps_{i-1}$을 조건 아래에서 최대화하는 것이다.

$j$를 고정하자. 그러면 목표는 $ps_{i-1} \ge ps_j - M$이면서 최소인 $ps_{i-1}$을 찾는 것이다.

이는 $ps$ 배열을 원소로 갖는 std::set을 이용하여 쉽게 찾을 수 있다. 1번보다 훨씬 쉬운 문제.

3. 아르바이트

1차 4번 문제의 느낌이 나는 문제인 것 같다. 

우선 중요한 점은, 하루의 급여가 바뀐 경우 최대 $k$개의 구간의 총합이 변화한다는 점이다. 즉, 구간의 합이 변화하는 총 횟수는 최대 $Qk$번이다. 

$n-k+1$개의 구간의 총합을 관리하고 있는 multiset이 있다고 하자. 우리는 이 multiset의 중앙값을 계속 구해야 한다.

총합 자체를 관리하는 것은 $\mathcal{O}(Qk + n)$에 쉽게 할 수 있으므로, 우리의 궁극적인 문제는 다음과 같다.

• 집합에 속한 원소 삭제
• 집합에 원소 하나 추가
• 집합의 중앙값 계산

다양한 접근이 가능하다. 첫 번째 접근은 세그먼트 트리를 이용한다.

가능한 구간의 합 $\mathcal{O}(Qk+n)$개를 전부 전처리 한 후 좌표압축하자. 

각 원소의 등장 횟수를 관리하는 합 세그먼트 트리를 관리하면, 이분탐색으로 답을 구할 수 있다.

세그먼트 트리를 구현할 경우 트리를 따라 내려가는 방식으로 이분탐색을 없앨 수 있다.

나는 중앙값을 계산하는 횟수가 $Q$로 적으므로, 세그먼트 트리 대신 펜윅을 사용하는 방식을 택했다.

그런데 이 방식을 구현했는데 TLE가 발생했다. 최적화를 했는데도 TLE여서 접근을 바꾸기로 했다.

두 번째 방식은 priority_queue를 이용한다. 

$n-k+1$개의 수들 중 작은 절반을 관리하는 PQ와 큰 절반을 관리하는 PQ를 생각하자.

이를 관리하는 것은 어렵지 않은데, 다음을 반복하면 된다.

• 원소 삭제시, 해당 원소를 포함하는 PQ에서 원소 삭제
• 원소 추가시, 중앙값과 비교하여 적합한 PQ에 원소 추가
• 중앙값 계산시, 큰 절반을 관리하는 PQ에서 최소 원소 찾기
• 마지막으로, 양쪽 PQ의 원소 개수가 원하는 반반이 되도록 밸런스 맞추기

이제 문제는 PQ에서 원소를 삭제해야 한다는 것이다. 그런데 삭제 가능한 PQ가 있다!

나는 친구에게 들었는데, 대충 top()을 호출할 때 삭제된 얘들을 다 날리는 방식이다. 자세한 것은 코드 참고.

이 방식은 연산 자체가 훨씬 간단해서 더욱 빠르다. 제출 10번 채웠으면 억울해 죽을 뻔 ㅋㅋ

4. 안전운전

가로선은 총합에 고려하지 않는다는 것을 늦게 읽어서 뇌절한 문제다. 

특정 $x$좌표 $T$에서 뒤집기를 시전했다고 가정하자. 그러면 그 후 경로의 모든 가로 좌표 $x$는 $2T-x$로 변환된다.

주어진 경로와 도로를 구간으로 쪼개서, 각 구간에서 경로/도로들의 가로 좌표가 고정되도록 하자.

이제 뒤집기 이전과 이후, 답에 더해지는 값들을 생각해보자.

• 뒤집기 이전에는 기존 경로 그대로 간다. 여기서 더해지는 값은 미리 전처리 가능하다.
• 뒤집는 가로선에서 $T$는 해당 가로선의 양 끝점 사이의 좌표가 된다.
• 뒤집기 이후에는 가로 좌표 $x$가 $2T-x$로 변환된다. 이후 구간에서 기존 가로 좌표가 $x$고, 왼쪽/오른쪽 도로의 가로 좌표가 각각 $L, R$인 경우, $L \le 2T-x \le R$인 경우에만 구간의 세로 길이가 답에 더해진다. 이는 부등식은 $(L+x)/2 \le T \le (R+x)/2$과 같다.

이제 뒤집는 가로선의 위치를 고정하고 생각하자. 이 가로선의 위치를 위에서부터 아래로 순서대로 본다.

매우 커다란 가상의 세그먼트 트리를 하나 준비한다.

• 각 구간에 대해, 세그트리의 구간 $[(L+x)/2, (R+x)/2]$에 해당 구간의 세로 길이만큼의 값을 더한다.
• 가로선이 등장한 경우, 그 가로선의 범위를 $[x_l, x_r]$이라 하자. 이 구간에서 세그트리의 최댓값을 뽑는다.
• 그 가로선 아래에서 얻어지는 값은 미리 전처리하였으므로, 이를 더한다.
• 이렇게 해서 얻어지는 값이 답의 후보이다. 이를 위에서부터 아래로 내려가면서 반복한다.

물론, 커다란 가상의 세그먼트 트리는 단순히 좌표압축으로 단순 세그먼트 트리로 바꿀 수 있다.

이제 필요한 것은 구간에 값 추가 + 구간 최댓값을 지원하는 세그먼트 트리고, 이는 lazy propagation으로 가능하다.

5. 삼각형의 거리

볼록다각형의 경우 작년 ICPC 기출문제다. 그대로 제출하면 47점이다.

이제 본격적으로 문제를 해결해보자. 답에 대하여 이분탐색을 하자. 답이 $m$ 이하가 될 수 있는지 판별하자.

정점을 반시계 순서대로 $v_1, v_2, \cdots, v_n$이라고 하자. 

각 $i<j$에 대하여 $P_{i, j}$를 $v_i, v_{i+1}, \cdots , v_j$로 이루어진 다각형이라고 하자.

단, $v_i v_j$가 문제에서 주어진 다각형 내부에 완전히 위치해야 한다.

이제 $DP[i][j]$를 $P_{i, j}$를 지름을 $m$ 이하로 삼각분할 할 때, [$v_iv_j$를 포함하는 삼각형에서 가장 먼 삼각형까지의 거리]로 가능한 것 중 최솟값에 $1$을 더한 값이라고 하자. 만약 조건을 만족하는 삼각분할이 불가능하면 $\infty$라 하자.

$DP[i][j]$를 계산하기 위해, 점화식을 설계하자. $k \in [i+1, j-1]$을 하나 잡고 $v_i v_k v_j$가 정당한 삼각형인지를 판별하자.

만약 정당하다면, $v_iv_jv_k$와 $P_{i, k}$의 삼각분할, $P_{k, j}$의 삼각분할로 구성된 $P_{i, j}$의 삼각분할을 생각할 수 있다.

이 경우 지름은 $DP[i][k] + DP[k][j]$가 되며, 이 값이 $m$ 초과인 경우 실패라고 볼 수 있다.

성공이라면, $DP[i][j]$로 가능한 값 중 하나는 $\text{max}(DP[i][k], DP[k][j]) + 1$이 된다. 이를 업데이트 하자.

이렇게 되면 고려해야 할 $DP$ 상태는 $\mathcal{O}(n^2)$, 전이 시간복잡도도 $\mathcal{O}(n^3)$이다.

이제 본격적으로 기하적 부분을 처리해야 한다. 고통스러웠다 :(

$v_i v_k v_j$가 정당한 삼각형인지 판별하는 것은 각 변이 주어진 다각형 안에 속하는지만 판별해도 된다.

이제 선분 $v_iv_j$가 주어진 다각형 안에 속하는지 판별하는 방법을 생각해보자.

우선 다각형의 선분들 중 $v_i v_j$와 만나는 것은 없어야 한다. (끝점 제외)

이 판별이 끝나면, $v_i v_j$는 전부 다각형 내부에 속하거나 전부 다각형 외부에 속한다.

그러니, $v_iv_j$의 중점을 잡고 다각형 내부에 속하는지 판별하면 끝난다!

Point in Polygon은 ray casting algorithm으로 하면 되며, 설명은 여기를 참고하자. 

중점을 계산해야 하는데 소수점 나오면 기분이 나쁘니 모든 좌표를 2배해서 계산을 편하게 하자.

아침에 일어나서 1, 2, 3번 풀고 밥 먹고 씻고 4, 5번 풀었다. 4번에서 뇌절한 거 빼고 괜찮았다.

대회가 대회인만큼 풀이는 최대한 자세하게, 코드까지 포함해서 작성한다.

1번. 다이어트

당연하게도 각 식당의 메뉴 중 가장 작은 $K$개를 먹어야 하는데, 짝을 잘 지어주는 것이 중요하다.

직관적으로 A 식당에서 칼로리가 많은 것을 B 식당에서 칼로리가 적은 것과 함께 먹어야 하고, 이는 실제로 정당한 풀이다.

증명하는 방법에는 여러 가지가 있을 수 있는데, 가장 쉬운 것은 exchange argument인 것 같다.

만약 $a_i < a_j$, $b_k < b_l$이 있어 $(a_i, b_k)$, $(a_j, b_l)$이 서로 짝을 이루고 있다면, 이를 $(a_i, b_l)$, $(a_j, b_k)$로 쌍을 바꾸는 것이 합의 최댓값을 감소시키는 방법이 된다. 이를 계속 반복하면 결국 원하는 결론을 얻고, 증명 끝. 다른 증명으로는 수학적 귀납법이 가능할 것으로 보인다. 코드는 매우 간단하다.

2번. 카드 게임

(초고난이도 문제를 제외한) 게임 문제는 대부분 전형적인 풀이를 갖는다. 가장 대표적인 풀이는 특정 상태를 "선공승", "후공승"으로 분류하고, 이 상태를 동적 계획법으로 계산하는 것이다. 특정 상태가 선공승이 되려면, 선공이 도달할 수 있는 상태 중 하나라도 후공승이면 된다. 반대로, 특정 상태가 후공승이 되려면, 선공이 도달할 수 있는 상태가 모두 선공승이면 된다. 이를 기반으로 동적계획법 풀이를 생각해보자. $dp[i][j]$란 더미 $X$에서 아래 $i$개의 카드, 더미 $Y$에서 아래 $j$개의 카드가 남았을 때 선공승인지, 후공승인지 여부라고 하자. 선공승이면 1, 아니면 0이다. 이제 각 상태에서 선공이 할 수 있는 움직임을 따져보자.

$(i, j)$라는 상태에 있다면, $X[t+1] + \cdots + X[i] \le k$을 만족하는 $t$에 대하여 $(t, j)$로 이동할 수 있다.

또한, $Y[t+1] + \cdots + Y[j] \le k$를 만족하는 $t$에 대하여 $(i, t)$로 이동할 수 있다. 

이러한 조건을 만족하는 $t$는 하나의 구간을 이루므로, 부분합 배열을 추가하여 각 DP 값을 $\mathcal{O}(1)$에 해결할 수 있다.

예를 들어, $X[t+1] + \cdots + X[i] \le k$를 만족하는 $t$가 $[u, i-1]$이라고 하자.

그러면 우리가 확인할 것은 $dp[u][j], dp[u+1][j], \cdots, dp[i-1][j]$ 중 $0$인 것이 존재하냐는 것이다.

이는 $dp[u][j]$부터 $dp[i-1][j]$까지의 합이 $i-u$와 같은지 파악하는 것과 같으며, 이는 부분합으로 가능하다.

$Y$의 경우도 마찬가지다. 또한, 이때 조건을 만족하는 $t$의 범위는 $X, Y$에 대한 부분합과 lower_bound 등으로 쉽게 구할 수 있다.