2025년 8월 셋째 주 PS 일지

8/19 화요일

17104 골드바흐 파티션 2: FFT를 배웠어요!

20176 Needle: ez

34117 허수아비: pq

 

8/20 수요일

나코더에서 반년대회를 했어요!!

 

대충 5등으로 좃망했어요! 피접 ㅂㅂ

스프라그그런디인지뭔지개열심히공부할게요

 

8/22 금요일

34201 거울: 이거 브1인듯

 

반년 대회 업솔빙을 좀 했어요!

34148 $2^K$-Flip: 대충 쿼리가 한 번이라도 됐다면 $2^{K-1}$만큼 기여하고 아니면 $2^K$만큼 기여함을 알 수 있습니다. 따라서 imos법 잘 박으면 됩니다.
34149 거짓말쟁이: 비트로 집합 잘 나눈 뒤 교집합을 찾아서 영차영차 하면 신기하게도 됩니다. 
34151 (Relatively) Prime: 걍 단순한 수학 문제
34152 순열과 순열: 미친 포함과 배제를 하면 사이클에 대한 식이 나오고 이를 잘 convolution 하면 됩니다.
34153 Unravel the Graph: https://koosaga.com/72
34154 팰린팰린드롬: 그리디하게 매칭시키는 걸 해싱으로 최적화
34155 수열과 수열 2: 걍 브론즈
34156 테토와 바게트: 걍 그리디
34157 Split the SSHS 5: 걍 ETT + 트리DP
34159 감그레이: 섹시한 인터랙티브같습니다. 흰색 한 놈을 찾으면 해결되므로 최대 한 놈을 탈락시켜 흰색을 찾는 전략을 생각하면 어떤 친구를 정해 그 친구가 흰색인지 모두에게 물어보면 됩니다. 이때 흰색이라고 답변한 놈을 처형해서 나쁠 게 없습니다.
34160 순열과 순열 (Hard): 쉬운 버전에서 NTT를 첨가하면 됩니다.

 

8/23 토요일

NYPC Round 2B를 했어요! 아마 2A에서 합격했을 텐데 그냥 다들 보길래 저도 쳤습니다!

 

3번까지는 1시간 컷내고 4번은 무슨 흉측한 선형대수학 문제처럼 생겨서 넘겼습니다.

 

레몬컵 세팅을 엄청 열심히 했어요!!! 다들 많관부~

 

8/24 일요일

제가 치지 않은 2025 KOI 2차 문제들을 풀어봤어요~

 

34200 장애물: 단순 DP

34202 점프: 인접한 수의 차가 무조건 ${-2, 0, 2}$에 속함을 이용하고 관찰을 몇 개 더하면 깔끔하게 됩니다.

34203 통행료: 뒤에서부터 보면서 유니온 파인드와 플로이드 워샬을 잘해주면 됩니다.

34204 가방: 투포인터 그리디

34205 새로운 인연: 트리로 바꿔주고 경우의 수에 대한 관찰 하고 포배 해주면 됩니다.
34206 로봇: 그냥 스파스를 해주면 됩니다.

34207 상자 보관: 딜워스 정리덕분에 교집합 최대 크기를 구하면 되기 때문에 느갱섹을 써줍니다.

34208 수열과 쿼리 46: 금광을 볼록 껍질로 나타내고 분할 정복을 해줍니다.

 

34158 Game with Segment Tree: 그런디 수는 $i\&(-i)$니깐 잘 해주면 됩니다.