2025년 9월 셋째 주 PS 일지

25404 주차 타워: dp의 극소점 좌표만 set으로 관리해줍니다.

스플레이 트리를 공부했어요!

32074 점수 경주: 쉬운데 뜨어어어어어어엉

8496 Godzilla: Incremental SCC

15870 Nordic Camping: DP를 잘 해주고 정사각형이므로 log 단위로 쪼개서 잘 전파가 가능합니다.

22350 맛집 추천: 트리 DP를 센트로이드 트리로 최적화합니다. 갓문제

B, D에서 개뇌절했지만 C, E를 나쁘지 않게 풀어서 적당히 -15정도로 타협했습니다... 레드가고싶어요

그리고 미친 다다스 IGM축하해!

34209 축제: 트리DP가 볼록함을 이용합니다. 높이가 $\frac{K}{2}$ 이상일 땐 $O(KlogK)$, 이하일 땐 적당히 해서 높이 스투라 트리DP로 $NlogK$에 풀립니다.

2019년도 이후 KOI 문제들을 모두 풀었습니다! ㅅㅅ

30708 업&다운: 한 홀짝성 내에서 가장 작은 수를 첫 번째로 하는 전략이 유효합니다.

34341 LIS 하나 빼기: 각 prefix, suffix의 dp를 금광으로 섹시하게 결합해줍니다.

34344 공연 준비: $i$ 이하의 수들만 본다고 하면 $N^2$의 상태가 나오고 결국 DP를 잘 해주면 됩니다.

17699 Long Mansion: 빠져나올수 없는 구간을 구한다고 하면 세그+스위핑을 이용해 쉽게 됩니다.

34262 트리 위의 표식: 결국 어떤 두 정점 사이의 거리도 $2L$ 이하인 서브트리 개수를 구하는 문제가 됩니다. 임의의 루트로 dfs를 한 뒤 깊이 순 정렬해서 $2L$ 이내의 정점들의 개수를 세주고 영차영차하면 됩니다.

woohyunjng 님의 블로그