Ps-20200811

rkm0959, jhhope1이랑 진행한 문제풀이의 간략한 풀이. 스포일러에 주의하자.

BOJ 15313. 정과프 해적단

$[l, r]$ 값이 없는 문제는 좌표압축 + 세그먼트 트리를 이용한 dp로 $O(n\log n)$에 해결할 수 있다. 이 때 $l$이 증가할수록 조건을 만족하기 위해 필요한 최소의 $r$도 증가하므로 inchworm을 얹어주면 $O(n^{2}\log n)$이 된다.

BOJ 15504. 프로그래밍 대결

제일 실력이 높은 선수를 제외하고, 각 선수마다 ‘자신을 이기는 선수’를 정해주면 스패닝 트리가 유일하게 결정된다. 해당 작업을 mcmf로 모델링하면 $O(n^{4})$. 늘 그렇듯 플로우 문제에서 시간복잡도는 아무 의미 없다.

BOJ 17101. Dynamic Centroid

트리 $T$에 리프가 하나 추가된 $T’$의 경우, 센트로이드는 변하지 않거나 최대 한 칸 움직인다. 움직인다면 어떤 서브트리 방향으로 움직일지를 정해주면 되는데, 결국 서브트리 사이즈를 dynamic하게 정해줄 필요를 느낀다. 오일러 투어와 펜윅 트리를 이용해서 구해주면 $O(n\log n)$. 좋은 문제인듯.

BOJ 10916. Xtreme GCD Sum

구해야 할 식은 결국 $\sum_{g = 1}^{10^{6}} \phi(g)\prod_{i=1}^{n}\left(\lfloor \frac{b_{i}}{g} \rfloor - \lfloor \frac{a_{i} - 1}{g} \rfloor\right)$가 된다. 위 식이 바뀌는 지점은 많아야 $O(n\sqrt{X})$개 있으므로, $\phi(n)$합 테이블이랑 같이 들고다니면 $O(X\log X + n\sqrt{X})$가 된다.

BOJ 17975. Strike Zone

KOI 2014 금광으로 $O(n^{2}\log n)$.

BOJ 13518. 트리와 쿼리 9

트리에서 MO’s algorithm을 돌리는 문제이다. 길이 $2n$의 오일러 투어를 먼저 얻은 뒤, 정점 $v$가 탐색되는 시점을 $d[v]$, 정점 $v$에서 빠져나가는 시점을 $f[v]$라고 하자. 쿼리가 되는 경로 $u \to v$를 두 가지로 나누어 생각해보자. 편의상 $d[u] < d[v]$를 가정한다.

1. $\text{lca}(u,v) = u$ 인 경우, $[d[u], d[v]]$의 구간을 생각하면 경로 위의 점들은 홀수 번, 경로 밖의 점들은 짝수 번 등장한다.
2. $\mathrm{lca}(u,v) = x$인 경우, $[f[u], d[v]]$의 구간을 생각하자. 그럼 $x$를 제외하고 경로 위의 점들은 홀수 번, 경로 밖의 점들은 짝수 번 등장한다. 유일하게 $x$는 등장하지 않으므로, $x$를 따로 처리해 주면 된다.

결국 어떤 수가 등장하는 횟수의 ‘기우성’이 중요하게 되고, XOR의 느낌으로 자료구조를 관리하는 MO’s algorithm 문제가 된다. 시간복잡도 $O(Q\sqrt{N})$.

BOJ 8452. 그래프와 쿼리

쿼리를 역순으로 생각하면 간선 추가 쿼리와 최단경로 쿼리가 있는 셈이 된다. 최단 경로 쿼리를 매번 BFS를 이용하여 구해주면 되는데, 나이브하게 구하면 $O(Q(V + E))$가 된다. 그런데 $u \to v$ 간선이 추가될 때 $u$에서 나가는 간선들만 최단경로를 갱신해준다고 생각하자. unit graph라는 특성상 각 노드에 도달하는 최단경로 길이가 갱신되는 건 많아야 $V$번이므로, 이 노드가 BFS를 전파하는 건 $O(V \cdot \mathrm{odeg}(v))$번이 된다. 이를 모든 노드에 대해 합하면 $O(Q + VE)$.

BOJ 16027. Global Warming

한 원소를 $d$만큼 증가시켰다면 그 뒤의 원소를 증가시키지 않을 이유가 없다. 그리고 $d = x$로 고르는 게 항상 유리하다. 따라서 각 $i$에 대해 $[i, n]$ 구간을 $x$만큼 들었을 때 LIS의 길이를 관리해주면 $O(n\log n)$.

BOJ 19568. 직사각형

약 팔기 (2). 귀여운 문제다.