8월의 PS 일지 - Part 6

이제 개강 + SNUPC 검수 + CTF 정식입문 + 등등으로 PS 일지가 일시정지 될 것 같다.

대신 CTF write-up을 최대한 열심히 써보려고 한다. 팀에 들어갔으니 진짜 열심히 해보려고 한다 :)

BOJ 1910 Two Parties

문제를 선형대수학으로 넘기는 것이 첫번째 핵심이다. 각 정점 $v$마다 $x_v \in \mathbb{F}_2$라는 변수를 하나 잡자.

이는 이 정점이 첫 번째 그룹으로 가면 $0$, 두 번째 그룹으로 가면 $1$이 된다. 이제 주어진 조건을 식으로 써보자.

만약 $x_v=0$이라면, $v$의 neighbor 중 $0$이 짝수 개 있어야 한다. 즉, $1$의 개수와 $v$의 차수는 기우성이 같다.

이는 $\sum_{u \in N(v)} x_u \equiv \text{deg}(v) \pmod{2}$와 같다. 이는 $\mathbb{F}_2$ 위의 방정식이 된다.

$x_v=1$이라면, $v$의 neighbor 중 $1$이 짝수 개이며, 이는 $\sum_{u \in N(v)} x_u \equiv 0 \pmod{2}$와 같다.

이는 결국 합쳐서 $\sum_{u \in N(v)} x_u + \text{deg}(v) \cdot x_v \equiv \text{deg}(v) \pmod{2}$로 쓸 수 있다.

이는 순수하게 $x$ 변수들에 대한 연립 일차방정식이 된다. 문제는 이들 중 최대한 많은 것을 만족시키는 것이다.

핵심 결론은, 이들 전부를 만족시킬 수 있다는 것이다. 이제 그냥 가우스 소거를 적용하여 문제를 해결할 수 있다.

왜 만족시킬 수 있을까? 모순이 발생하려면 결국 식 몇 개를 조합하여 $0=1$ 형태의 식을 얻어야 한다.

이제 각 정점에 대해 존재하는 방정식 중 몇 개를 뽑아서 더했다고 하자. 뽑은 정점을 $v_1, v_2, \cdots , v_k$라 하자.

여기서 좌변은 모든 미지수에 대한 계수가 짝수, 즉 $0$이며, 우변은 결과가 홀수, 즉 $1$이 나와야 한다.

즉, $\sum_{i=1}^k \text{deg}(v_i) \equiv 1 \pmod{2}$가 성립해야 한다. 이제 이게 가능한지 잘 생각해보자.

대충 그래프에서 차수 다 더하면 짝수인 것과 비슷한 논리를 잘 생각해보면, 바로 모순을 얻을 수 있다. 직접 생각하자.

Petrozavodsk 2018 Winter Day 8 : Saratov SU Contest

• A : 귀찮고 어렵지 않은 문제. 최솟값을 하나 고정하고 생각하는 게 편한데, 중복 카운팅을 잘 처리해야 한다.
• C : 직선을 생각하면 오른쪽 끝을 기준으로 정렬하여 그리디를 적용하는 것이 가능하다. 트리에서도 크게 다르지 않다. 루트를 임의로 하나 잡고, LCA의 깊이가 깊은 것부터 차례대로 선택하는 것이 가능하다. 점 업데이트 + 경로 쿼리니까 HLD가 필요할 것 같지만, 이 그리디의 특성을 이용하면 DFS 오더링 + 단순 세그트리로도 가능하다. 점을 추가할 때마다 "그 서브트리의 점을 하나 이상 포함하는 경로"는 모두 해결된다는 점을 파악하면 된다. 
• J : 이 문제의 쉬운 버전. 그냥 분할 정복을 그대로 박으면 된다. 이게 가장 쉬운 문제 중 하나라는 게 참 ㅋㅋ
• K : 쿼리에서 등장할 수 있는 서로 다른 문자열의 길이가 루트 개 정도라는 것을 이용하는 문제다. 쿼리에서 다루는 문자열의 길이를 고정하면, 해싱을 통해서 각 문자열에 대한 답을 한 번에 계산할 수 있다. 매칭이 발생하는 위치를 모두 찾고, 그리디하게 뽑아가면 된다. 해싱은 두 번 해야 하는 것 같다.
• G : 이 문제의 강화판이다. 이분탐색과 저 문제의 풀이의 변형을 합치면 문제를 해결할 수 있다. 변형은 어렵지 않으니 설명 생략.
• L : 때려 맞춘 것 같다. 일단 문제를 해석해보면, Shortest Path DAG의 Dominator Tree를 구하라는 문제가 된다. 일반적으로도 Dominator Tree는 빠르게 구해진다고 하는데, 이건 대충 매우 어려운 것 같다. 링크 참고. 여기서는 DAG임을 이용해야 하는데, 이를 활용하는 간단하고 빠른 알고리즘이 있다. 이 글 참고. 증명 안하고 짜서 맞았다 ㅋㅋ 저 두 번째 글은 아직 읽어보지 않았는데 한 번 읽어봐야 할 듯.
• D : DP 식을 설계해보자. $dp[i]$를 첫 $i$명을 태운 뒤 도착하기까지 걸리는 시간이라고 하자. 그러면 $dp[i] = \text{min}_{j<i} \left( \text{max}(dp[j], t[i]) + 2 \cdot \text{max}_{k \in [j+1, i]} a[k] \right)$가 성립한다. 이를 빠르게 계산할 방법을 찾자. 일단 $dp$ 배열이 단조증가이므로, $dp[j]$와 $t[i]$ 사이의 크기 관계를 기준으로 $j$의 범위를 두 개로 나눌 수 있다. $dp[j] < t[i]$인 경우, 중요한 것은 $[j+1, i]$에 속한 $k$ 중 $a[k]$의 최댓값이므로, $j$가 가능한 크면 좋다. 즉, 이 경우에는 배열 $a$에 대한 range maximum 세그트리로 해결이 가능하다. 문제는 $dp[j] > t[i]$인 경우이다. 저 $[j+1, i]$ 구간의 $a$ 최댓값 부분이 관리하기가 상당히 까다로운데, 좋은 해결 방안이 있다. 스택을 사용하는 것이다. 스택을 사용하면 저 구간 최댓값이 언제 달라지는지를 쉽게 관리할 수 있고, $i$가 증가함에 따라 관리하는 것도 어렵지 않다. 조금 더 생각을 하면 결국 구간에 값을 더하고 구간 최댓값을 계산하는 segment tree with lazy propagation으로 문제를 풀 수 있다. 개인적으로는 재밌게 푼 문제였다.
• F : $k$에 대한 조건이 강력하다. 임의의 수를 하나 선택했을 때, 그 수가 답에 포함될 확률이 50% 이상이라는 뜻이기 때문이다. 그러니, 수 하나를 잡은 다음 약수를 전부 구하자 (pollard-rho). 이제 중요한 것은 "약수들 중 그 배수가 $n-k$개 이상 존재하는 것 중 최댓값은 무엇인가"를 구하는 것이다. 이건 소인수들의 지수 입장에서 생각하면 일종의 11차원 부분합과 다를 게 없다. 이는 이 문제의 요령으로 해결할 수 있다. 시간 제한이 빡센듯.

BOJ 11617 Export Estimate

문제의 핵심은 답에 대한 공식을 구하는 것이다. 결론적으로 차수 0 정점, 차수 2 정점, 단순 사이클의 개수가 중요하다.

쿼리를 오프라인으로 처리하여, 빈 그래프에서 간선을 추가하는 방식으로 쿼리를 처리해보자. 이제 위 값들을 관리해야 한다.

이는 union-find를 하는 과정에서 전부 처리할 수 있다. 단순 사이클의 판별은 최소/최대 차수를 관리해서 하면 된다. 

BOJ 19281 Short Random Problem

지름이 여러 개 존재할 가능성 / 지름의 중점이 정점에 놓일 가능성 등은 전부 직관적으로 0이니 무시해도 괜찮다.

문제 풀이의 핵심은 지름의 중점이 어느 간선 위에 놓이는지를 기준으로 케이스를 나누는 것이다.

간선 하나를 고정하고, 이를 $u$와 $v$를 잇는 간선이라고 하자. 이 간선의 가중치를 $e$라고 하자.

또한, 이 간선을 잘랐을 때 $u$를 루트로 하는 트리, $v$를 루트로 하는 트리 두 개의 트리가 나온다.

$u$를 루트로 하는 트리에서 $u$를 끝점으로 하는 경로의 최대 길이를 $l_1$, $v$를 루트로 하는 트리에서 $v$를 끝점으로 하는 경로의 최대 길이를 $l_2$라 하자.

지름의 중점이 $u-v$ 간선 위에 놓일 필요충분조건은 $e+l_1 \ge l_2$, $e+l_2 \ge l_1$이다. 

이때, 지름의 길이는 $e+l_1+l_2$가 된다. $e$의 분포는 자명하니, $l_1, l_2$의 분포가 필요한 상황이다.

이를 DP + DFS로 구해야 하는데, 대강의 sketch를 하자면 다음과 같다. 굉장히 힘겨우니 옆에 토할 비닐 하나 준비하자.

대충 $w$와 $w$의 서브트리에 속하는 리프 중 $w$와 가장 먼 것 사이의 거리를 $l(w)$라 하자. 

$l(u)$의 분포, $l(v)$의 분포를 구하는 것이 우리의 목표고, 이를 일종의 DP로 구하는 것이 그 방법이 될 것이다.

즉, $w$의 자식이 $c_1, c_2, \cdots , c_k$일 때, $l(c_1)$부터 $l(c_k)$의 분포를 기반으로 $l(w)$의 분포를 구해야 한다.

이를 위해서는 다음 두 가지 과정을 거쳐야 한다. 

• $e$를 $[0, 1]$에서 uniform distribution을 따르는 확률변수라고 하자. $l(c_i)$의 분포를 알 때, 이를 $l(c_i) + e$의 분포로 변환시켜야 한다.
• $l(c_1)+e$부터 $l(c_k)+e$의 분포를 전부 구했다고 하자. 이때, 이들의 최댓값에 대한 분포를 구해야 한다.

쉽지 않다. 이를 그나마 쉽게 구하려면, 다음과 같은 핵심 관찰을 해야 한다.

우선 두 번째 과정을 쉽게 해결하려면, PDF를 사용하는 것보다는 CDF를 사용하는 것이 좋다는 것이다. 

CDF를 구하고, 이를 전부 곱하면 바로 최종 결과의 CDF가 되기 때문이다. 이는 정말 좋은 성질이 아닐 수 없다.

이제 또 다른 핵심 관찰을 할 수 있다. 각 정점 $w$에 대해서 $l(w)$의 PDF 및 CDF가 각 구간 $[a, a+1]$에서 다항식이라는 것이다. 여기서 $a$는 음이 아닌 정수.

이를 증명하는 것은 귀납법과 위 두 관찰로 가능하다. 그러니 CDF를 다항식의 수열로 관리할 수 있다.

이제 식을 열심히 오지게 쓰다보면 이게 계산이 가능하다는 것을 알 수 있다. 지렸다!

하지만 끝이 아니다. $e+l_1 \ge l_2$, $e+l_2 \ge l_1$이 성립하는 영역에서 $l_1+l_2+e$의 값 역시 계산해야 한다.

즉 해당 영역에서 $(l_1+l_2+e)$와 $l_1$에 대한 확률밀도함수, $l_2$에 대한 확률밀도함수를 곱한 것을 적분한 결과를 얻어야 한다.

오지는 삼중적분을 계산해야해서 매우 고통스럽지만 어쨌든 계산해놓은 것들로 충분히 계산할 수는 있다. 

다행히 다항식을 가지고 노는 과정에서 FFT 등을 요구하지는 않고 대충 하면 된다. 졸라 힘들다... 

BOJ 19579 물건 가져가기

민컷으로 환원해서 푸는 문제. 음수 값을 가지는 것들이 있어서 어떻게 다루나 걱정했는데, 정말 멋진 풀이가 있었다.

슬라이드가 풀이 설명을 거의 완벽하게 한 것 같으므로 그 링크로 풀이를 대체한다. 그래프 모델링하는 법 다 까먹은듯 ㅋㅋ

BOJ 14460 Why Did the Cow Cross the Road III (Platinum)

$|i-j| >k$, $A_i < A_j$, $B_i > B_j$가 성립하는 $(i, j)$의 개수를 세는 문제다. 대충 3차원 쿼리 느낌의 문제...

$A$에 대한 정렬 + 분할 정복 + $B$에 대한 정렬 + 인덱스에 대한 세그먼트 트리로 해결할 수 있다.

BOJ 15756 Disruption

서브트리 안 - 서브트리 밖을 잇는 간선 중 가장 가중치가 작은 것을 찾는 문제다.

서브트리 안 - 서브트리 밖을 잇는 간선인지를 판별하는 가장 쉬운 방법은, 간선의 양 끝점 중 서브트리 안에 존재하는 것이 정확히 하나인 것이다. 

이제 각 정점에 대응되는 [추가 간선의 집합]을 관리할 것이다. 우선 각 추가 간선에 대해서, 그 양 끝점에 대응되는 집합에 해당 간선을 추가하자. 

$v$와 그 부모를 잇는 간선을 삭제했을 때, 우리가 원하는 답으로 가능한 후보군은 $v$의 서브트리에 존재하는 집합들의 symmetric difference가 된다. 

이제 이 집합을 DFS를 돌면서 관리해야 하는데, small-to-large를 박으면 알아서 잘 된다. 물론, 집합의 원소 순서는 가중치 순서로 해야 한다.

BOJ 17031 Moorio Kart

우선 BFS로 연결 컴포넌트 및 각 컴포넌트의 점들 사이의 거리를 전부 구하자. 이제 문제는 다음과 같다.

"각 연결 컴포넌트에서 경로를 하나씩 선택한 후 배치하여, 총 길이를 $Y$ 이상으로 할 때 가능한 경로의 길이 합을 구한다"

보통 이러면 $d[i]$를 길이가 $i$인 경로의 개수라고 한 다음 이를 차례대로 구하고 싶어진다. 

그런데 문제는 경로의 길이가 수백만 수준으로 커지고, 이를 모두 관리하기가 매우 어려워진다. $Y$ 자체는 2500 이하이므로, 이를 활용해야 한다.

이를 위해서, $0 \le i \le 2499$에 대해서는 $d[i]$를 길이가 $i$인 경로의 개수라고 하되, $d[2500]$은 길이가 $i$ 이상인 경로의 개수라고 하자. 

또한, $0 \le i \le 2499$에 대해서는 $s[i]$를 길이가 $i$인 경로의 길이의 합이라고 하고, $s[2500]$을 길이가 $2500$ 이상인 경로의 길이 합이라 정의하자. 

이를 전부 계산하려면 해당 배열을 각 연결 컴포넌트에 대해서 전부 계산하고, 이를 합치는 방식을 사용하면 된다. 

굉장히 다항식 곱셈 같은 방식으로 계산이 되는데, 이를 단순하게 하면 시간 초과가 발생한다. 

최적화를 하려면, $d[i], s[i] \neq 0$인 인덱스에 대해서만 계산을 하면 된다. 실제로 두 컴포넌트의 결과를 합치는 방법은 어렵지 않으므로 독자에게 남긴다. 

또한, 위 최적화를 하면 시간복잡도가 유의미하게 줄어드는데, 이를 증명하는 것도 좋은 연습문제가 된다. 고민해보는 것 추천.

BOJ 18356 Movie-goer

$i$번째 영화부터 볼 때 얻을 수 있는 최대 만족도를 각 $i$에 대해서 구하는 것을 목표로 한다. $i=1$부터 생각하자.

특정 영화 $p$를 하나 고정하자. $p$의 첫 상영까지 시청하면 $w_p$를 얻고, 두 번째 상영까지 시청하면 다시 $w_p$를 잃는다.

즉, "첫 번째 상영부터 두 번째 상영 직전까지" $w_p$를 얻게 된다. 일종의 구간에 값을 더하는 쿼리라고 볼 수 있다.

이제 $i=1$에서 $i=2$로 넘어간다고 하자. 첫째 날의 영화를 $p$라고 하자. 즉, $p$의 첫 상영은 첫째 날이다.

그러면 기존에 $p$의 첫 상영 ~ 두 번째 상영에 $w_p$를 추가한 업데이트를 취소하고, 두 번째 상영 ~ 세 번째 상영에 $w_p$를 추가해야 한다. 

결국 특정 영화의 다음 상영 시간을 전부 전처리하고, 구간에 값을 더하고 전체 최댓값을 구하는 lazy propagation segment tree를 쓰면 문제가 해결된다.

BOJ 18358 Gluttons

처음에는 모두 큰 케이크를 먹게 하고, 불만이 생기는 사람이 생기면 그 사람의 선택지를 바꿔주는 것을 반복하자.

이를 효율적으로 계산하기 위해서는 불만이 있는 사람으로 구성된 큐를 관리하면 된다. 

답지를 보니까 퍼텐셜 분석으로 이게 유한 시간에 끝남을 증명한 것 같다. (여기서 답은 무조건 존재한다는 것도 얻는다)

BOJ 18360 Logistics

$\sum \text{min}(a_i, s) \ge cs$가 성공 필요충분조건임을 직관적으로 생각할 수 있고 증명도 귀납으로 가능하다.

이제 이 식이 성립하는지 확인하는 게 남았는데, $s$가 크니까 좌표압축을 해준 후 세그먼트 트리를 사용하면 된다.

원소 중 $s$ 이상인 것의 개수와, $s$ 이하인 것의 합을 구하면 되므로 합과 개수를 관리하는 세그트리를 각각 만들면 된다.

BOJ 19651 수열과 쿼리 39

Range GCD 문제와 비슷한 향이 나는 문제라고 생각한다. 문제를 살짝 변형시켜서 쿼리를 단순하게 만들 수 있다는 점에서다.

주어진 문제는 $a_{i+2}-2a_{i+1}+a_i = 0$이 성립하는 연속된 $i$의 최대 길이를 구하는 문제와 동치이다.

또한, 등차수열을 더하는 쿼리에 의해서 $a_{i+2}-2a_{i+1}+a_i$의 값이 변화하는 인덱스의 개수는 최대 4개이다.

그러므로, 단일 원소에 값을 더하는 쿼리와 연속된 0의 개수의 최댓값을 구하는 세그먼트 트리를 짜면 된다.

이는 금광 문제처럼 구간의 길이, 왼쪽에서 연속된 0의 개수, 오른쪽에서 연속된 0의 개수, 답을 관리하면 된다.