Sunday, August 24, 2014

20140824

Codeforces Round #151(Div. 2) : All solved

내가 AC 받았던 소스코드들

Problem A

Problem B

Problem C

Problem D

Problem E

E에 관해서 정리를 해보면

1) BFS로 numbering

2) 각 node마다 2^k 위의 parent를 구함

3) 쿼리 (v, k) : depth[v] + k의 깊이에 해당하는 노드 L(i)~R(i)에 대해 이분탐색을 하면서 k 깊이 위의 부모가 v인지 검사하는 식으로 구간 [L, R]을 구함.

4) 구간들을 Bucket Sorting하고( [L/루트(N)]*루트(N) + [R/루트(N)], [ ] : 가우스 기호 ) acmicpc.net 8462 '배열의 힘' 문제 솔루션 대로 쿼리에 대해서 답을 구한다.
(acmicpc.net 8462 솔루션 링크)

전체적인 시간복잡도는 O(Q log^2 N + N루트(N))이 된다.

ALPS 회원들한테 문제를 공유하고나서 좀 더 생각해보니, 쿼리가 만약 (r, v, k) : 루트가 r일 때, 쿼리 (v, k)로 루트가 입력받을 때로 지정된 게 아니라 쿼리에서 바뀔 수 있다면, 에디토리얼에 있는 BIT나 세그먼트 트리를 써야지 풀릴 것 같다. 루트가 바뀌면 구간이 [P,P]+[L,R]꼴이 되는데 [P, P]처리가 안되네 ㅋㅋ

자꾸 연습을 div2만 돌고 있는데, div1에서는 보통 많아야 2~3문제 밖에 못 푸는데 그게 div2랑 겹치다보니 ㅋㅋㅋ... 자꾸 연습하다보면 div1에서 편하게 연습 돌 때가 오겠지ㅎ

No comments:

Post a Comment