2026 KOI 2C - 곡예
문제요약 대충 유담이가 C보다 왼쪽, 다다스가 D보다 오른쪽에 갈 수 있는가?를 구하면 됩니다. 일단 각 점 $i$에서 간선을 타고 이동할 수 있는 가장 왼쪽 점 $L[i]$ 와 가장 오른쪽 점 $R[i]$ 를 Min/Max 세그로 구합니다.$[L[i], i]$와 $[i, R[i]]$는 각각 laminar set을 이룹니다. 이를 이용해 $[L[i], i]$ 구간들로 구성된 L-트리, $[i, R[i]]$ 구간들로 구성된 R-트리를 만들어줍니다. 쿼리 $[A, B]$가 주어지면 세그로 1차적으로 구간을 확장합니다.$$[A, B] \longrightarrow [\min_{i \in [A, B)} L[i], \max_{i \in (A, B]} R[i]]$$$L[i]$가 최소가 되는 인덱스를 $X$, $R[i..
2026. 7. 22.
BOJ 15842 - Koala Game
풀이와 증명을 이해해볼겸 이 글에 문제의 풀이를 정리하겠습니다. 문제 요약입니다 ㅎㅎ 서브테스크 1 (4점, 최솟값 찾기, $C_{max}\le 2$)$0$번째 값에 $1$만큼 배팅합니다. 코알라는 어떻게 해도 $99$개의 값만 먹을 수 있기에 최솟값을 제외하고 모두 먹을 것 입니다.따라서 $R_i=0$인 $i$가 답이 됩니다.int minValue(int N, int W) { int B[N], R[N]; fill(B, B + N, 0), B[0] = 1, playRound(B, R); for (int i = 0; i 서브테스크 2 (15점, 최댓값 찾기, $C_{max}\le 4$)다음 과정을 반복해서 풀 수 있습니다.1. 최댓값 후보 $S$가 있다고 하자. 이 집합에 속한 인덱스에..
2026. 2. 1.
