lmlmlm
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
'문제풀기' 카테고리의 다른 글
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 |