2025년 6월 첫째 주 PS 일지

6/2 월요일

34026 창하의 수열 뒤집기 이야기: 연산을 취하는 구간이 이진 트리 속 서브 트리라는 점을 이용해서 이진 트리에서 금광 세그를 하듯이 해주면 됩니다.

 

6/3 화요일

16745 What Goes Up Must Come Down: 작은 수부터 보면서 각 수마다 왼쪽으로 갈지 오른쪽으로 갈지 그리디하게 결정해 주면 됩니다.

17730 Growing Vegetables is Fun: 16745

2519 막대기: 적당히 2-SAT 모델링을 해주면 됩니다.

 

6/4 수요일

11191 Xor Maximization: 배타적 논리합 기저 (gf(2))를 사용합니다.

 

6/8 일요일

10076 휴가: $[s-x, s-y]$ 구간에서 가장 큰 $d-2y-x$개의 숫자의 합의 최댓값을 구하는 문제로 치환해 줄 수 있습니다. 이때 $x$값과 $y$값의 단조성이 성립해 dnc opt + pst를 적당히 잘 활용해 주면 됩니다. 

25440 송신탑: $[L, R]$ 구간에서 인접한 원소 간 차이가 $D$ 이상인 최대 길이 바이토닉 수열을 구해주면 됩니다. 이는 적당한 그리디 + 셋질로 해줄 수 있고 쿼리를 온라인으로 처리해야 하므로 pst와 많조분을 적당히 이용해 줍니다.

16998 It’s a Mod, Mod, Mod, Mod World: 유리 등차수열의 내림 합을 배웠습니다.

18448 Best Subsequence: 파라메트릭 서치 + 그리디를 이용합니다. 상한을 $x$로 고정했을때 $\frac{x}{2}$ 이하의 원소를 모두 사용하는 최적해가 존재하므로 그 사이에 적당히 끼워 넣어주면 됩니다.