Codeforces Round #343 div2

문제 : http://codeforces.com/contest/629

A.
각 열과 행마다 C의 개수를 세고 kC2 만큼 더해주면 된다. O(n^2)

코드 : http://ideone.com/8i1SUj

B.
모든 날짜에 대해 돌면서 세보면 된다. O(n * 366)

코드 : http://ideone.com/I7k54a

C.
DP[open][len] = 안 닫힌 열린 괄호 수가 open이고 길이가 len인 경우의 수
라고 정의하고 왼쪽과 오른쪽에 놓을 수 있는 열린(닫힌) 괄호의 수를 계산해서 답에 더해주면 된다. O((n - m)^2)

코드 : http://ideone.com/jo81en

D.
LIS와 비슷하다. DP[i] = i번째 케이크를 제일 밑에 깔고 그 위에 적절히 쌓아서 만들 수 있는 최대 케이크의 부피라고 정의하자.
주어진 케이크 n개의 초기 인덱스와 부피를 계산해서 저장해놓고 부피순으로 정렬하고, 정렬된 순서대로 DP테이블을 채워 나간다. 이렇게 하면 해당 DP테이블을 채울 때 필요한 테이블의 값은 언제나 정확하게 들어가 있게 된다.
DP[i]를 채울 때 j < i 이면서 DP[j]가 최대인걸 찾아야 하는데, 이는 세그먼트 트리같이 구간 최대 쿼리를 처리할 수 있는 자료구조를 사용하면 찾을 수 있다.
부피가 같은 케이크는 같이 쌓을 수 없다는 점만 주의해서 처리하면 풀 수 있다. O(nlgn)

코드 : http://ideone.com/WrdiFa

E.
r(u, v) = 정점 u와 v의 길이 기대값

일단 r(u, v)에는 u와 v의 거리가 언제나 더해진다.(u에서 v로 가는 경로에 속하는 정점에 간선을 놓는 경우에는 u, v를 포함하는 사이클이 생기지 않는다.)

size(u, v) = u에서 출발하여, u에서 v로 가는 경로를 경유하지 않고 도달할 수 있는 정점의 개수
sum(u, v) = u에서 출발하여, u에서 v로 가는 경로를 경유하지 않고 도달할 수 있는 정점들과 u간의 거리의 합
dist(u, v) = u에서 v까지의 거리

라고 하면 r(u, v) = sum(u, v) / size(u, v) + sum(v, u) / size(v, u) + dist(u, v) + 1

dist(u, v)는 dfs로 정점의 깊이를 저장해놓고, lca를 이용해서 depth[u] + depth[v] - 2 * depth[lca(u, v)]로 구할 수 있다.

관련 : https://www.acmicpc.net/problem/1761

sum(u, v)와 size(u, v)는 DFS로 전처리하고 구할 수 있다.

alldep(u) = u에서 다른 모든 정점까지의 거리의 합

subdep(u) = u에서 u를 루트로 하는 서브트리에 있는 정점까지의 거리의 합

subsize(u) = u를 루트로 하는 서브트리의 정점의 개수

를 구해놓자.
관련 : https://www.acmicpc.net/problem/7812

이제 size(u, v)와 sum(u, v)를 구할 수 있다.

v가 u를 루트로 하는 서브트리에 속하는 경우와 아닌 경우를 나눠서 생각할 수 있다.

(서브트리에 속하는지는 DFS 할때 시작시간 종료시간 저장해서 알 수 있음)

관련 : http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2615

속한다면 : 

sum(u, v) = alldep(u) - subdep(u의 자식 정점이면서, v를 포함하는 서브트리를 가지는 정점) + subsize(u의 자식 정점이면서, v를 포함하는 서브트리를 가지는 정점)

size(u, v) = n - subsize(u의 자식 정점이면서, v를 포함하는 서브트리를 가지는 정점)

속하지 않는다면 : 

sum(u, v) = subdep(u)

size(u, v) = subsize(u)

u의 자식 정점이면서, v를 포함하는 서브트리를 가지는 정점은, 자식들의 DFS 종료시간을 저장해놓고 종료시간이 증가하는 순으로 저장돼 있다는 점을 이용해 이진탐색으로 찾는다.

전처리 O(n)이고 m개의 쿼리가 있는데 쿼리 하나당 O(lgn) 이니깐 총 시간 복잡도 O(n + mlgn)

코드 : http://ideone.com/WfPGWp