이틀 뒤 UCPC다. 내일은 브론즈 하나만 풀고 잘 듯
이분 탐색을 하면 된다. research를 어떤 task에 해야 하는지에 대한 아이디어를 떠올리는게 힘들었다. 필요한 리셋 횟수가 k일 이상이라면, 이 일을 어려운 일이라고 하자. 일단, 쉬운 일과 어려운 일들을 어떻게 해도 k일 내에(리셋은 k-1회) 끝낼 수 없다면 불가능한 경우이다. 그리고 k-1번의 리셋을 하고, 마지막 k번째 날에 해야하는 어려운 일의 시간들의 합이 c보다 크다면 불가능하다. 아니라면 가능함
B에 대해 정렬하면, 맨 왼쪽은 내가 항상 가져가게 된다. 인덱스가 작은 곳부터 2칸씩 늘리면서, 지금까지 본 것들 중 가장 A값이 높은 것을 가져가면서 밀면 된다.
뿌요를 세로로 떨어뜨린다는 아이디어는 금방 생각할 수 있다. 구현이 약간 까다롭다.
덱을 이용해 구간 최대/최소를 O(N)에 찾을 수 있고, inching worm을 통해 최대 구간을 찾을 수 있다. 난 덱 최대/최소를 이제야 알았다;;
dp[l][r]을 l~r에서 가능한 경우의 수라고 정의하고 풀면 된다. AxBy (A, B는 올바른 괄호 문자열이고, x, y는 길이가 1인 문자열)의 형태일 때, x != y인 경우에 나눠주면 된다.
간선에 대한 트리 dp이다. dfs를 하며 간선 방향이 바뀔 때 dp값에 변화를 주면 된다.
업데이트가 있다 = 세그를 쓴다. 어떤 구간의 왼쪽 부호를 \(l\), 오른쪽 부호를 \(r\)이라고 하면, 이 구간의 최소 비용은 \(dp[l][r] = \min_{0\leq k\leq 2}(L[l][k] + min(R[(k+1)\mod 3][r], R[(k+2)\mod 3][r]))\)가 된다. 구간의 길이가 1일 때에 주의하여 풀면 된다.
아래 3문제는 연습셋을 푼 건데, 3시간 동안 푸는게 되게 힘들었다..
ucpc화이팅!
'백준 문제풀이' 카테고리의 다른 글
| 7/1 ~ 7/8 PS (0) | 2022.07.08 |
|---|---|
| 백준 25213 - 조각 케이크 (Hard) [C++] (0) | 2022.07.05 |
| 6/20 ~ 6/26 PS (0) | 2022.06.26 |
| 6/8 ~ 6/16 PS (0) | 2022.06.16 |
| 6/3~6/7 PS (3) | 2022.06.07 |