Tags

5 pages

단조성

[Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

IOI 2014 Holiday(휴가) 최적 풀이. 선형 도시에서 하루에 이동 또는 방문만 가능한 제약에서 방문 관광지 수를 최대화한다. 이동은 한 번의 방향 전환만 해도 충분하다는 관찰 아래 [l,r] 구간을 잡고 체류 가능일 g(l,r)을 계산한다. 분할정복+세그먼트 트리로 상위 k 합을 빠르게 질의하여 O(N log^2 N)로 해결한다. 경계·중복·음수 k 처리와 좌우 반전까지 구현 체크리스트 포함.
[Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

[Algorithm] cpp 백준 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 - PBS+세그트리

히스토그램의 구간 [l,r]에서 너비 w가 고정일 때 최대 넓이는 길이 w 윈도우의 최솟값을 최대화하는 문제입니다. 높이 좌표압축과 임계값 단조성을 이용해 병렬 이분탐색을 수행하고, 세그먼트 트리(연속 1의 최댓값)로 검증하여 각 쿼리를 빠르게 해결합니다. 엣지 케이스와 실수 포인트까지 점검합니다.
[Algorithm] cpp 백준 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 - PBS+세그트리