Never Knows Best

https://youtu.be/xshuvos1bm0?si=YQR4x4AlUTZKKdVZ

 

https://www.acmicpc.net/problem/16311

문제를 간단히 요약하자면, 간선에 가중치가 있는 방향 그래프가 주어지고 두명의 플레이어가 게임을 한다. 시작 노드에서 끝 노드로 가야하는데 선공은 최대한 게임을 오래 하고 싶고, 후공은 게임을 최대한 빨리 끝내고 싶다.

 

그래프가 DAG라 해보자. 그럼 DP로 어렵지 않게 문제를 해결할 수 있다. $DP_0(v) = $ 정점 $v$에 있고 선공 차례일 때 게임이 끝나는 시간, $DP_1(v) = $ 정점 $v$에 있고 후공 차례일 때 게임이 끝나는 시간으로 정의해보자. 그럼 $DP_0(v) = \max_{v \rightarrow u} DP_1(v) + c(u, v)$, $DP_1(v) = \min_{v \rightarrow u} DP_0(v) + c(u, v)$ 이다.

 

DAG가 아닐 때 문제를 해결해보자. 이때 $DP_0$ 값이 단조증가함을 생각해보면, $DP_1$을 다익스트라 처럼 채워줄 수 있다. 그럼 $DP_0$은 언제 갱신해줄 수 있을까? 인접한 모든 정점의 $DP_1$값이 전부 갱신되었을 때만 가능하다. 그래프에서의 shortest path는 쉬운 문제지만 longest path는 어려운 문제니까 $DP_1$부터 채워주는 느낌?

 

만약 $DP_0(s)$가 계산되지 않았다면 답은 무한대일것이다. 만약 $DP_0(s)$가 계산되었다면 올바른 값임을 보이는 것은 어렵지 않고, 계산되지 않았다면 무한대임을 보이는 것은 좀 어려운데 뭔가 그럴 것 같다(...)

 

https://www.acmicpc.net/problem/32836

스몰투라지 또는 센트로이드 분할을 사용하면 어느정도 티피컬한 $\mathcal{O}(N \log^2 N)$ 알고리즘이 나온다. 그러나 제한이 돌 것 같지가 않기 때문에 다른 방법을 생각해보자.

 

트리 DP를 할 때 두 서브트리 $T(a), T(b)$의 결과를 $\mathcal{O}(|T(a)| \cdot |T(b)|)$시간에 합쳐줄 수 있다면 전체 문제를 $\mathcal{O}(N^2)$시간에 해결할 수 있음은 검은돌 트릭이라는 이름으로 잘 알려져 있다. 비슷하게 트리 DP의 시간복잡도가 잘 bound되는 방법이 하나 더 있다.

 

서브트리의 깊이 $D(a)$를 $T(a)$에서 가장 먼 정점까지의 거리라고 정의하자. 만약 정점 $v$의 자식들 $c_1, c_2, c_3, \dots, c_k$에 대해 $DP(v)$를 $\mathcal{O}(\sum_i D(c_i) - \max_i D(c_i) )$시간에 계산할 수 있다면, 전체 문제를 $\mathcal{O}(N)$에 해결할 수 있다.

 

$D(v) = \max D(c_i) + 1$임을 생각해보자. 총 시간복잡도를 생각해보면, $\sum_{v \neq r} D(v) - \sum_v \max_i D(c_i)$ 가 될 것이다. 근데 각 $v$에 대해서 $\max_i D(c_i) = D(v) - 1$이기 때문에 각 $v \neq r$에 대해서 더해지는 값은 $1$이다. 즉 저 합은 $D(r) + N - 1$이 된다. 

 

이 방법을 활용하면 이 문제를 $\mathcal{O} (N \log N)$ 또는 $\mathcal{O} (N)$에 해결 가능하다.

 

https://www.acmicpc.net/problem/32831

모든 point $(r, c)$에 대해 이 point가 colorful quadrants가 될 수 있는지 테스트해보자. $0, 1, 2, 3$사분면을 각각 그 사분면에 존재하는 색으로 매칭시켜줄 수 있다면 $(r, c)$는 colorful quadrants가 될 수 있다. 즉, 이분그래프에서 완전매칭이 존재하는지 판별해야한다.

 

$DP_k(r, c) = $ $(r, c)$를 기준으로 나눠지는 사분면 중 $k$ 사분면에 대해 그 사분면에 속한 색의 집합으로 정의하자. 잘 생각해보면 각 사분면에 색이 $4$개 초과로 있는 것은 의미가 없다. 그래서 이 DP 테이블을 스위핑하며 $\mathcal{O}(NM)$시간에 채울 수 있고, 각 점에 대해 테스트 하는 것은 홀의 결혼정리를 통해 해결할 수 있다.

 

그러나... 이 문제는 제한이 정말 쓰레기같다. qoj.ac에서는 별다른 최적화 없이 맞을 수 있었지만 백준에서는 각종 상수최적화 + 캐시히트를 잘 고려 + fastio를 사용해야 AC를 받을 수 있었다.

 

https://www.acmicpc.net/problem/5009

모델링이 재밌는 문제이다. 우선 $T$에 대한 파라메트릭을 해주자. 그러면 결정문제가 각 정점마다 칠할 수 없는 색이 주어질 때 3-coloring이 가능한지 판별하는 것이 된다. 이는 선호도가 $T$초과인 것들에 간선을 이어줬을 때 생기는 그래프를 만들면 된다.

 

문제 자체는 3-coloring (NP-hard)이지만 각 정점당 칠할 수 있는 색은 두가지 밖에 없기에 뭔가 풀릴 것도 같다. 각 정점마다 가능한 상태가 두가지이기에 2-SAT의 냄새가 나고, 여기까지 왔다면 모델링은 크게 어렵지 않다. 2-SAT이란 만족하면 안되는 조건들의 나열임을 생각해보자.

 

https://www.acmicpc.net/problem/20090

에일리언 트릭을 배운지는 좀 되었지만, 에일리언 문제 자체를 풀어보진 않아서 복습할 겸 잡아봤다. 문제에 대해서는 딱히 할말은 없다. $r \leq c$인 형태로 환원을 할 수 있고, $(r, c)$이 strictly increasing하는 점들만 봐도 된다는 곳 까지 왔다면 CHT를 통한 $\mathcal{O}(NK)$ 풀이를 유도하는 것은 어렵지 않다. 이제 "믿음"을 가지고 답이 $K$에 대해 볼록함을 찍고 에일리언 트릭을 짜면 된다.

 

에일리언 트릭에 대해 첨부해보자면,

볼록성을 어떻게 믿을 수 있을까? cost가 monge임을 보이거나 mcmf로 모델링 됨을 보이는 방법이 정석이다. 될 것 같은 적당한 직관은 볼록성의 정의인 $f(x + 1) - f(x) \leq f(x + 2) - f(x + 1)$이 의미하는 바가 뭔지 생각해보면 된다. mcmf에서의 증가경로의 최단경로는 단조증가함이 볼록성을 의미하니까...

 

에일리언 트릭은 항상 우리가 원하는 $K$를 찾아주진 않는데, 그래서 보통 반정수 구간에서의 이분탐색을 사용한다. $DP$값이 정수이면 차분도 항상 정수이고 그렇기에 기울기 또한 정수인데, 반정수인 $\lambda + 0.5$ 기울기에 대해 접선인 좌표는 유일하기 때문이다. 하지만 구현이 좀 귀찮아진다.

 

https://seyun0501.tistory.com/25

Alien Trick과 구현시 팁

이 글에 나온 방식이 반정수보다 훨씬 편리하기 때문에 한번 읽어보는 것을 추천한다.

 

https://www.acmicpc.net/problem/30859

재밌는 문제다. 잘 생각해보면 $a_i$ 또는 $b_i$중 적어도 하나는 항상 답에 포함시킬 수 있음을 보일 수 있다. 또한 그러한 값을 우리가 선택할 수 있음도 보일 수 있다. 그렇다면 선택되는 값을 $\max (a_i, b_i)$로 고정하고, 두 값 모두 선택되는 경우를 최대화하는 문제가 된다. 두 값 모두 선택되는 경우는 이 값들이 모두 strictly increasing 하는 경우밖에 없기에 DP를 통해 계산해줄 수 있다.