EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)

https://codeforces.com/contest/1987

F 못 푼건 억까다.

아침에 일어나서 커피 한잔 하고 Morning clarity 상태로 푸니 풀린다.

 

A. Upload more RAM

 

K초에 1GB만 올릴 수 있으니, 1, K + 1, 2K + 1, ...에 올릴 수 있다.

따라서 (N - 1) * K + 1

 

B. K-Sort

 

a[i] > a[i + 1]이라면 그만큼 a[i + 1]을 증가시켜줘야 한다.

그러면 증가횟수는 우선 sum(max(0, b[i] - b[i + 1]))이다. (단, b[i] = max(a[0], a[1], ...a[i]))

이때 한 번 increase할 때마다 1의 추가비용이 있으니 MAX(b[i] - b[i + 1])을 더해주어야 한다.

 

C. Basil's Garden

 

[x, n - 1]이 모두 0이 되는데 걸리는 시간을 t[x]라고 생각하자.

t[x]값을 알고 있다고 할 때 t[x - 1]을 구하는 것을 생각해보자.

1) h[x - 1] <= h[x] : h[x]가 더 작아졌을 때만 h[x - 1]이 감소하면서 t[x - 1] = t[x] + 1

2) h[x - 1] > h[x] : 아무튼 h[x - 1]은 그만큼 감소해야 하기 때문에 t[x - 1] = max(t[x] + 1, h[x - 1])

t[x] + x = u[x]인 u를 생각한다면, u[x] = max(u[x - 1], h[x] + x)가 성립하게 된다.

따라서 답은 MAX(h[x] + x)

 

D. World is Mine

 

Alice는 먹을 수 있는 제일 작은 걸 먹는게 무조건 이득이다.

Bob은 Alice가 특정 크기를 못 먹도록 하는 것이 무조건 이득이다.

다음과 같은 dp를 생각하자 

dp[x][y] = (Alice는 x이상을 먹을 수 있는 상태이고, Bob은 y번 버틴 상태)

-> 만일 Alice가 x를 먹도록 내버려둔다면 dp[x + 1][y + 1] = min(dp[x + 1][y + !], dp[x][y] + 1)

-> 만일 Bob이 x를 못 먹도록 먹어치운다면 dp[x + 1][y - cnt[x]] = min(dp[x + 1][y - cnt[x]], dp[x][y])

 

E. Wonderful Tree!

 

child의 합이 더 크거나 같도록 해야 한다.

a[v] < sum(a[u])가 성립한다면, a[v]는 아무때나 sum(a[u]) - a[v]를 증가시켜도 무방하다.

하지만 만일 a[v] = sum(a[u])라면 a[v]를 증가시키고 싶으면, a[v], a[u], ...을 순서대로 증가시켜주어야 한다.

즉, a[v] < sum(a[u])가 성립하거나 (v is leaf)인 제일 가까운 노드까지의 거리를 찾아야 증가가 가능하다.

dp[x][y] = (x로부터 거리 y인 노드 중 a[v] < sum(a[u])거나 v is leaf인 노드에 대해 증가가능 횟수)라 하면

-> a[v] < sum(a[u])면 dp[v][0] += sum(a[u]) - a[v]

-> v is leaf면 dp[v][0] = INF

-> v의 parent인 w에 대해서 dp[w][y] += dp[v][y - 1]

 

F. Interesting Problem

 

마지막으로 제거되는 (a[i], a[i + 1])의 원래 초기에 position이 x, y라고 하자.

그러면 [x, y]의 숫자들이 모두 제거된 것은 물론, 내부의 숫자들은 외부와 엮일일이 없다.

gone[x][y] : [x, y]의 숫자들이 모두 제거되기 위해서 x보다 앞에 필요한 operation의 수 (불가능하면 1e9)

-> x가 지워지는게 가능해야하므로, 당연히 (x - a[x]) / 2 이상이다.

-> [x + 1, y - 1]이 먼저 지워져야하므로 gone[x][y] >= gone[x + 1][y - 1]이다.

-> gone[x][y]가 갱신되면, gone[x][y + 2], gone[x][y + 4], ...을 모두 갱신해주어야 하고, O(N^3)

dp[x] : x까지 최대로 지워질 수 있는 횟수

-> 모든 y에 대해 gone[x][y] <= dp[x]여야 [x, y]가 제거될 수 있고, dp[y + 1] = max(dp[y + 1], dp[x] + (y-x+1)/2)

 

Editorial을 보면 상당히 흥미로운게, 이것이 마치 bracket sequence같다는 점이다.

 

G1. Spinning Round

 

어떤 제일 P가 큰 중심에 대해 왼쪽 노드들과 오른쪽 노드들이 칼같이 나뉜다.

즉 A -> B -> C -> ... MID ... <- C' <- B' <- A'에 대해 (A, B, C ...) <= x <= (A', B', ..)인 x가 존재한다.

그러면 애초에 Cartesian tree처럼 왼쪽과 오른쪽이 나뉘도록 할 수 있는가?

4 3 2 1 5와 같은 배치에서, 1 -> 2 -> 3 -> 4 -> 5가 좋아보이고, (1->5), (2->5), (3->5)가 필요없어보인다.

-> 즉 (R[x] = cur)인 x 중에서 제일 큰 x만 관리해도 괜찮아보인다.

다만, 한가지 경우가 있는데 적당히 ~ -> 4 -> 5 <- 3 <- 2 <- 1 <- ~와 같은 path가 있을 수 있다.

즉, (2, 1, 3)과 같이 R[2] = 3, R[1] = 3라면, 2 -> 3 <- 1 형태의 path가 존재한다.

 

path를 만드는 방법은 다음이 존재한다

1) 일직선으로 쭉 올라오는, 제일 기본적인 방식. 이것은 dp[cur]이라 지칭한다.

-> 이것은 단순하게 cur와 연결된 모든 노드에 대해 MAX(dp[child] + 1)로 구할 수 있다.

2) 양쪽에서 올라오는, 마찬가지로 제일 기본적인 방식.

-> dpL[cur]는 왼쪽에서 올라온 제일 긴 길이, dpR[cur]는 오른쪽에서 올라온 제일 긴 길이라 하자.

-> 위에서 양쪽에서 올라오면 겹칠 수 없음을 확인했으므로 단순히 dpL[cur] + dpR[cur] - 1

3) 한쪽에서 두 개가 올라오는, 일명 skewed된 형태.

-> 둘 다 나의 왼쪽에 있는 노드 a, b에서 cur로 온다고 가정하자. (R[a] = R[b] = cur, L[b] = a)

-> 일단 여기서 만일 R[L[a]] = cur이라면, a -> L[a] -> cur로 가는 것이 더 이득이다.

->  따라서 alpha = (a, L[a], L[L[a]]], ... 중에서 R[x] = cur인 x의 개수)라 정의하여 이 값을 더해주어야 한다.

3-1) a의 왼쪽과 b의 아래에서 올라온 형태 : dpL[a] + dp[b] + alpha

3-2) b의 아래에 있던 경로가 적당히 쪼개지면서 a와 이어지는 형태 : dpL[b] + dpR[b] + alpha

3-3) a와 b에 사이에 있는 mid에 대해, mid의 경로가 적당히 쪼개지면서 이어지는 형태

       -> 이때에는 생각보다 많은 양의 노드들이 추가될 수 있다

       -> mid를 기준으로 생각했을 때, 위쪽으로 연결된 모든 노드들을 타고 올라갈 수 있다.

       -> 따라서 새로운 dpmidL[cur] = MAX(dpmid[child] + 1)를 정의.

       -> cur 왼쪽의 제일 큰 dpmid값을 dp2L[cur]라 하면... 현재 우리가 찾는 경로는 dp2L[b] + alpha