Notice
Recent Posts
Recent Comments
Link
«   2025/06   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Tags
more
Archives
Today
Total
관리 메뉴

lmlmlm

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

문제풀기

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

lml 2024. 7. 4. 13:16

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

'문제풀기' 카테고리의 다른 글

UCPC 2024 예선 후기  (0) 2024.07.15
NCPC 2022  (0) 2024.07.05
Educational Codeforces Round 167 (Rated for Div. 2)  (0) 2024.06.28
Codeforces Round 955 (Div. 2, with prizes from NEAR!)  (0) 2024.06.27
Codeforces Round 949 (Div. 2)  (1) 2024.06.15
Comments