Tags

29 pages

투포인터

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

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

[Algorithm] cpp 백준 13546번: 수열과 쿼리 4 - Mo+제곱근분할

구간 [L,R]에서 같은 값의 두 위치 간 최대 거리(max |x−y|, A[x]=A[y])를 묻는 질의를 Mo 알고리즘으로 처리합니다. 값별 위치 데크와 거리 빈도(√ 분할)를 유지해 추가/제거 O(1)로 갱신하고, 블록 카운팅으로 최대 거리를 즉시 찾습니다. 경계 이동 순서·인덱스 변환·거리 갱신 누락 실수를 방지하는 체크리스트까지 정리했습니다.
[Algorithm] cpp 백준 13546번: 수열과 쿼리 4 - Mo+제곱근분할