2025년 9월 첫째 주 PS 일지

9/1 월요일

34195 물고기와 쿼리: 세그 쓰면 됩니다. 근데 안 써도 됩니다.

 

9/2 화요일

34223 하노이 여행하기: ㅗ

34228 턴제 전략 XOR 게임: 적당히 관찰해주면 xor min을 트라이로 찾는 문제가 됩니다.

34226 그래프와 연결성 쿼리: mos를 해주면 됩니다.

 

9/4 목요일

한번 2019년도 이후의 정올 문제들을 올솔해보려고 합니다!

 

34229 극대 찾기: 삼분 탐색을 피보나치 수를 이용해서 적은 쿼리 수로 해줄 수 있습니다.

17612 쇼핑몰: pq와 set으로 문제 상황을 구현

17614 369

17615 볼 모으기

17616 등수 찾기: dfs

17618 신기한 수

17619 개구리 점프: 유니온 파인드

 

대성호 팀의 월파 메달 수상을 축하드립니다!!

 

9/5 금요일

17622 타일 교체: 브루트포스 + bfs

17623 괄호: $O(N^3)$ 처럼 보이는 DP를 해주면 됩니다. 왜 되는진 잘 모르겠으나 아마 답이 로그 스케일이라서 그런 게 아닐까 싶습니다.

34097 망각의 최장 경로: 작은 정점부터 컴포넌트로 추가하면서 디피를 해주면 됩니다.

17625 고압선: 꽤 까다로운 불도저 트릭

23863: 17625

17621 물 채우기: 땅에 붙은 것과 안 붙은 것 분리해서 구해주고 교집합을 빼줍니다.

 

KOI 2019 1차대회

KOI 2019 2차대회

2019년도의 KOI 문제들을 모두 풀었어용!

 

9/6 토요일

19941 햄버거 분배

19942 다이어트

20186 수 고르기

20187 종이접기

20191 줄임말

20194 경계 로봇: 최적해의 꼴이 쉽게 나옵니다. 가능한 경우가 $O(N)$이므로 모두 해줍니다. 왜 다2나 되는지는 ㅁㄹ?

21757 나누기

21759 두 개의 팀: 귀찮은 트리DP

21760 야구 시즌

21762 공통 부분 수열 확장: prefix, suffix 그리디 매칭을 해주고 누적합을 해줍니다.

 

참고로 골드 이하는 간단한 노트 생략할수도있어용~

 

KOI 2020 1차대회

KOI 2020 2차대회

KOI 2021 1차대회

3개의 시즌을 밀었습니당~

 

LGCPC 2025 예선 Open Contest

 

3번 개어렵네요

 

9/7 일요일

Lemon Cup이 열렸습니당. 많은 관심 감사해요!

 

C, D를 출제했어요.

C는 페이커 알고리즘 딸깍입니다. 저퀄문제 죄송합니다.

D는 살짝 괜찮은데 관찰 몇개를 하면 1차원 DP 문제로 치환돼요. 이걸 행렬 세그 + 화성 지도 세그로 최적화하면 됩니당

 

34278 Hack!

34280 Rotating Lines

아마 풀이는 여기 있을거에용.