이번에도 어김없이 업다운랜디를 돌렸습니다.
학교에서 할 게 없어서 하루종일 문제만 풀고 있네요 ㅋㅋㅋ
12784: 인하니카 공화국(G3, Tree, 16:00)
dp[i]를 i번을 루트로 하는 트리에서 필요한 최소 다이너마이트의 개수로 잡고 트리 dp를 돌릴 수 있다.
사실 재사용되는 값이 없어서 메모이제이션은 필요하지 않다!
오랜만에 트리DP를 짜봐서 구현이슈가 좀 있었다...
시간 초과...
새로운 방에 불을 킬 때마다 그 방의 상하좌우를 탐색해서, 이미 방문한 지점이 있다면 새로운 방을 큐에 넣어준다.
예전에 재채점으로 틀렸던 문젠데 드디어 풀었다 ㅎㅎ
A+B가 짝수인 경우는 골드바흐의 추측(웬만큼 큰 정수까지에 대해서 증명됨)에 의해 나눌 수 있다.
A+B가 홀수인 경우, 두 소수를 더해서 홀수이려면 2 + p 꼴이여야 한다.
따라서 A+B-2가 소수인지 판정해야 하는데, 수의 범위가 크므로 소수 판정을 최적화해야 한다.
이는 sqrt(N)까지의 소수를 에테체로 구해놓은 후, 구한 소수들만을 가지고 나머지 판정을 함으로써 가능하다.
dp[i][[j]: i번 기업부터 j만원을 가지고 투자할 때 최대 이익이라고 정의하면,
간단한 탑다운 냅색으로 답을 구하고 역추적할 수 있다.
6213: Balanced Lineup(G1, Segment Tree, 10:33)
전형적인 G1 세그 날먹 문제.
19543: 던전 지도(P5, Two Pointers)
어쩌다보니 플레까지 오게 되었지만... 첫 문제는 바로 틀렸다.
N, M이 매우 크므로 효율적인 알고리즘을 생각해야 한다.
관찰을 통해 한 층에서 보스방에 도달할 수 있는 범위는 연속적으로 나타난다는 것을 알 수 있다.
또한, f(m)을 m번 인덱스 왼쪽부터 시작하여 최초로 도달하는 U의 인덱스라고 잡으면,
윗 층의 구간 [L, R]에서 보스방에 도달할 수 있을 때, 아랫층의 [f(L-1)+1, f(R)] 구간에서 보스방에 도달할 수 있다.
이를 모든 블록에 대해 전처리하고, 구간은 감소하기만 하므로 투 포인터로 계산할 수 있다.
1480: 보석 모으기(G1, Bit DP, 39:10)
dp[bit][m]을 현재 남은 보석의 상태가 bit일 때, m번 보석부터 훔칠 수 있는 최대 보석의 수라고 정의하면,
dp 상태 전이에 2^N번의 연산이 사용되므로, O(M*4^N)에 해결할 수 있다.
역시 오랜만에 비트마스킹을 써봐서 구현이슈가 있었다 ㅠㅠ
16440: 제이크와 케이크(P5, 수학, 26:51)
첫번째로 태그 안 보고 짠 플레 문제다!!
답의 최댓값이 2라는 것을 사잇값 정리와 비슷하게 증명할 수 있다.
s를 0, k를 1에 대응시키고, 처음 [0, n/2) 구간의 합을 a라 하자. 만약 a = n/4면 중간을 한 번 자르는게 답이 된다.
a < n/4라 하자. 구간의 양 끝 범위를 1씩 증가시키면 구간합의 변화량은 -1, 0, 1 중 하나이다.
그런데 구간이 [n/2, n)에 도달했을 때, 이 때 구간합은 n/2 - a로 n/4보다 크다.
따라서 범위를 증가시키는 동안 구간합이 정확히 n/4였던 적이 적어도 한 번 존재하게 된다. 그 순간은 prefix sum을 이용해 구할 수 있다.
다음엔 G1부터 시작해야겠다.
'PS > 공부' 카테고리의 다른 글
| 2024-03-19 PS 공부 (1) | 2024.03.19 |
|---|---|
| 2024-01-21 PS 공부 (1) | 2024.01.21 |
| 2023-12-13 PS 공부 (0) | 2023.12.13 |
| 2023-12-03 PS 공부 (0) | 2023.12.04 |
