BOJ '바리스타와 함께하는 대회 테스트' 풀이

Main Page / Scoreboard

A. 농부 후안은 바리스타입니다
2차원 fenwick tree를 이용하여 O(Q log N log M)에 해결할 수 있다.
[x1, y1]×[x2, y2] 영역에 +d하는 연산을, (x1, y1)와 (x2+1, y2+1)에 +d하고 (x1, y2+1)와 (x2+1, y1)에는 -d하는 연산으로 치환한다.

이렇게 치환한 상황에서 (x, y)에 위치한 씨앗의 개수는 [1, x]×[1, y]에 있는 씨앗의 개수를 계산하는 연산으로 치환된다.
아래의 코드를 참고하자.

B. 로스팅하는 엠마도 바리스타입니다
어떤 정점 X를 루트로 하는 트리를 가정하자. 이 때 다른 정점들에서 X로 이르는 최단거리의 합 S(X)에 대해 관찰하자.
트리에서 임의의 두 정점 사이를 잇는 경로는 유일하므로, 부모 정점 u와 자식 정점 v를 잇는 간선의 길이가 w일 때에 이 간선이 S에 포함되는 횟수는 정점 v가 루트인 부트리(subtree)의 정점의 개수와 동일하다.
따라서 임의의 정점 X에서 깊이우선탐색을 시작하여, 각 정점이 루트인 부트리의 정점 개수를 계산하고, S(X)를 계산한다.
다시 한 번 X에서 깊이우선탐색을 시작하여, 트리의 루트 노드를 다른 정점 Y로 바꾸어보면서 S(Y)를 빠르게 계산할 수 있다.

부모 정점 X와 자식 정점 Y를 잇는 간선의 길이가 W고 정점 Y의 부트리에 속한 정점의 개수가 sub(Y)일 때에, S(Y) = S(X) + W{N - sub(Y) - sub(Y)}이다.

C. 추출하는 폴도 바리스타입니다
i번째 커피콩을 정답이 되는 수열에 포함하는 경우 2가지를 고려해주면 된다.
첫째는 A(i-1)≡A(i) (mod k)이다. 이는 D([x = A(i)] mod k)에 대한 동적계획법 테이블을 이용해서 계산할 수 있다.
둘째는 A(i-1)-d≤A(i)≤A(i-1)+d이다. 이는 구간 트리를 이용한 동적계획법 테이블을 이용해서 계산할 수 있다.