200811 Problem solving

algorithm-ps ― [ algorithm-ps ]

Created: Aug 17, 2020 8:43 AM

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). 귀여운 문제다.

Written on August 11, 2020