Google Kickstart 2021 Round B

소스 코드 위치: Google Kickstart 2021 Round B

 

A. Increasing Substring

  거저 주는 문제.. 이전 값과 비교해서 현재가 크면 이어주고 아니면 끊는다.

B. Longest Progression

  음? 갑자기 구현이 빡세진 느낌.

  prefix array, suffix array를 유지하면서 현재 i번째를 바꾸려고 할 경우 i기준 왼쪽과 함께할 것인지 오른쪽과 할 것인지를 결정한다. 이때 양쪽 어디든 합치려고 할 때 그 차이값을 다른 한쪽과 비교하여 이어질 수 있는지도 판단해야 한다.

  양끝 처리 때문에 좀 시간이 걸렸던 문제.

C. Consecutive Primes

  Analysis보고 풀었다..

  10^9보다 작은 인접한 두 소수의 차이는 계산할만큼 작다. Prime gap이라고 하던데 10^9 내에서 두 소수의 차이가 가장 크다면 그 차이는 282가 최대다. 따라서 주어진 Z에 대해 범위 [max(2, sqrt(Z) - 282), sqrt(Z)] 사이에서 소수(p)를 찾고 이를 찾고자 하는 두 소수(p, q) 중에서 작은 소수로 둔다. 다음으로 q 후보가 되는 소수를 찾는다. 어차피 prime gap은 최대 282이므로 충분한 시간 내로 찾을 수 있다.

D. Truck Delivery

  정말 재밌는 문제.

  풀이를 보기전에 www.acmicpc.net/problem/14268문제를 안푸셨거나 푸는 것을 추천, 푸셨다면 다시 한 번 아이디어를 생각해보는 걸 추천합니다.

 

  눈치채야하는 점이 몇 가지 있습니다.

  1. 항상 쿼리는 도시 C에서 도시 1로 와야하고 트리 형태, 단순 경로를 택한다고 했기 때문에 C에서 1로 가는 경로는 유일하다.

  2. 도시1을 루트로 두는 트리를 구성했다면 1.에 의해 C에서 1로 가는 경로에 속하는 도시 중 C와 1이 아닌 임의의 도시 X에 대해서 최소 공통 조상 LCA(C, X) = X이다.

  3. 2.에 의해 X의 경로는 C의 경로의 부분 집합이기 때문에 X가 영향을 받으면 C역시 영향을 받는다.

 

  여기서 잠시 N-1 도로에 대해서 생각해봅시다. i번째 쿼리 Qi에 대해 Ci와 Wi가 있는데 Wi보다 제한 Li가 큰 도로가 필요할까요 ? 당연히 필요 없죠. 그러면 쿼리를 Wi 기준으로 정렬하고, Wi보다 작거나 같은 Li들을 새롭게 가중치를 "부여"해주는 건 어떨가요? 마치 오프라인 쿼리+DSU처럼 여기서도 똑같이 진행할 수 있습니다.

 

  4. 도로 i 번째가 건설된다. 도로가 건설된다는 건 반드시 방향성을 가지게 되어 있습니다. 위에서 도시 1을 기준으로 트리를 구성했기 때문에 양쪽 도시 u, v 중 반드시 하나는 도시 1과 가깝습니다.

  5. 4.에서 보다 가까운 도시를 u, 먼 도시를 v라고 하면 이 도로를 건설할 때 v를 루트로 하는 서브 트리에 영향을 미칩니다. (이해가 안된다면 3. 을 다시 읽어봅시다)

 

  여기서 또 잠시. 서브 트리에 대해서 영향을 미쳐야합니다. 구조에서 연속으로 처리할 방법은 없을까요? 서브트리이기 때문에 '오일러 투어 테크닉'을 사용합니다. 부모 노드가 자식 노드보다 작은 id 값을 갖도록 합니다. 부모 노드는 자신을 루트로 하는 서브 트리 내에 있는 모든 id 범위를 다룹니다. 저는 왼쪽 L, 오른쪽 R로 둬서 노드가 범위를 가질 수 있도록 구현했습니다.

int dfs(int u, int p) {
	int& ui = ordered[u] = tindex++;
	R[ui] = L[ui] = ui;
	for (int& v : adj[u]) if (v ^ p)
		R[ui] = dfs(v, u);
	return R[ui];
}

  6. 다시 i번째 도로를 건설한다고하면, L[u]부터 R[u]까지 가중치를 먹이면(?) 됩니다. 여기까지 생각이 도달했다면 연속적인 부분에 대해서 업데이트 하고, 쿼리를 해오니, 레이지 세그트리가 적합함을 알 수 있습니다.