8/3~8/6 연습

그 동안 쉬운 문제만 푸느라 문제 정리를 올리고 싶은 의욕이 없었다. 앞으로는 그냥 의식의 흐름대로 풀리는 문제는 적당히 필터링하겠다.

---

1052. 물병

http://icpc.me/1052

일단 물병을 무한정으로 사올 수 있기 때문에, 항상 답을 찾을 수 있다. 그냥 입력의 \(N\)보다 큰 최소의 \(2^p\)꼴의 숫자를 찾으면 물병을 1개로 만들 수 있기 때문에, 답은 항상 \(2N\)보다 작다는 것도 알 수 있다.

그런데 그대로 내면 당연히 4%대에서 틀리게 된다. 아이디어를 조금만 발전시키자. \(X\)개의 물병을 압축할 수 있는 최소 개수는 \(X\)를 이진수로 나타냈을 때 각 자리수의 합, 즉 \(s_2 (X)\)가 됨을 알 수 있다. 즉 물병을 더해 가면서 \(s_2 (X) \le K\)가 성립하는지를 체크해주면 되는데, 물병을 1개씩 더하면 \(O(N)\)이 되고, 그 대신 \(X \& -X\) (X의 0 아닌 최초 비트) 값을 더해주면 \(O(lg N)\)만에 문제를 해결할 수 있다.

여담인데, 이진수의 자리수 합을 직접 구현해도 되지만, GCC의 경우 __builtin_popcount라는 함수를 제공한다. CPU 연산을 이용해서 속도도 더 빠르다고 하니 사용해 보자.

Time Complexity : \(O(lg N)\)

---

13309. 트리 (KOI '16)

http://icpc.me/13309

http://oj.uz/problem/viiew/KOI16_tree

트리에 대한 dynamic connectivity problem이다. 갓-skykhs3의 풀이를 따랐다.

http://drugstoreoftamref.tistory.com/12 에서처럼, 각각의 노드를 DFS-numbering 하여 구간 처리를 할 수 있도록 준비한다.

세그먼트 트리를 준비하는데, 배열(리프 노드)에는 (각 노드에서 가장 높이 올라갈 수 있는 노드의 깊이)를 저장한다.

Update Query : 정점 \(u\)와 그 부모를 끊는 쿼리는 \([dt[u], ft[u]]\) (폐구간 주의!) 의 배열 값을 \(depth[u]\)로 갱신해 주는 쿼리이다. 즉, \(highest[x]\)를 \(max(highest[x], depth[u])\)로 갱신하는 쿼리 를 수행하면 된다.

Check Query : \(highest(LCA(u,v)) == max\{highest(u), highest(v)\}\) 가 성립하면 연결되어 있고, 그렇지 않다면 끊겨 있다.

Time Complexity  : \(O (LCA + Query)\) = \(O(N lg N + Q lg N) \)

---

14554. The Other Way (HYEA Cup '16)

정점 \(S\)에서 \(E\)로 가는 최단 경로의 개수를 묻는 문제. 킹-갓-HYEA님께서 만드신 문제라 까다롭게 처리해야 할 게 많을 줄 알았는데, 의식의 흐름대로 짰더니 풀린다(...)

당연히 최단경로는 다익스트라 알고리즘을 사용하는데, 다익스트라 알고리즘을 도는 와중에 가능한 최단 경로의 개수를 세어 주면 된다.

\(dist[v]\)를 \(S\)에서 \(v\)로 가는 최단 경로의 길이, \(cnt[v]\)를 \(S\)에서 \(v\)로 가는 최단 경로의 개수라고 하자.

다익스트라 알고리즘을 돌면서 정점 \(u\)에서 \(v\)에 가게 되었을 때, 지금 막 계산된 \(cost = dist[u] + w[u\rightarrow v]\)와 \(dist[v]\)를 비교한다.

\(cost < dist[v] : dist[v]=cost, cnt[v]=cnt[u]\), \(v\)를 heap에 넣어 준다.

\(cost = dist[v] : cnt[v] = cnt[v] + cnt[u]\)

\(cost > dist[v]\) : *아무 일도 일어나지 않았다.

답은 \(cnt[E]\).

Time Complexity : \(O(E lg V)\)