2026년 1월 셋째 주 PS 일지

1/12 월요일

ABC | 우주정거장 2 | No Cycle | 장난감 | 패턴 매칭 로 이루어진 셋을 돌았습니다. 우주정거장 2를 제외하고 다 풀어서 400점을 획득했습니다.

 

SCPC 2022 2차 예선 ABC: 재귀 DP를 해줍니다. 무한 처리가 좀 까다롭습니다.

SCPC 2018 본선 우주정거장 2: 최대한 삼각형을 제거해준 뒤 단절점에서 가능한 경우를 모두 곱해줍니다.

SCPC 2021 1차 예선 No Cycle: 그리디하게 방향을 배정해줘도 문제가 되지 않습니다.

SCPC 2023 1차 예선 장난감: 일단 최대한 퍼뜨린 뒤 Z 알고리즘으로 주기를 찾습니다.

SCPC 2021 2차 예선 패턴 매칭: 비교 가능하게 문자열을 바꾼 뒤 해싱을 잘 써줍니다.

 

25008 문자열 찾기: 패턴 매칭

31736 Island Hopping: 자기와 거리가 1인 노드들에 대해서 부모를 설정해주거나 부모로 설정해줍니다.

31977 Minequake: 적당히 식 정리후 전방향 트리DP를 해주면 됩니다.

 

1/13 화요일

지우개 | 돌 무더기 게임 | 딱 맞게 | MST | 팀 구성 | 편집 거리로 이루어진 셋을 돌았습니다. 편집 거리 빼고 다 맞았어요.

 

SCPC 2022 1차 예선 지우개: 반대로 생각하면 양옆의 연속한 문자 제거 후 kmp와 누적합을 이용하는 풀이가 쉽게 나옵니다.

SCPC 2022 본선 돌 무더기 게임: 쉬운 $O(N^3)$ DP를 유도한 뒤 적당한 전처리 + 이분 탐색으로 $O(N^2log N)$으로 풀면 됩니다.

SCPC 2024 1차 예선 딱 맞게: 파라를 할 때 최대가 되는 쌍을 고정하면 나머지는 쌍이 결정되기에 이를 세그로 잘 계산해줍니다.

SCPC 2025 1차 예선 MST: MST를 만든 뒤 간선 끼워넣기를 해줍니다.

SCPC 2025 2차 예선 팀 구성: 거리가 $K_1$ 초과인 경우 $K_2$를 가진 정점들은 반대 쌍이 고정돼있기에 자료구조 + 스위핑을 열심히 하면 됩니다.

NYPC 2025 본선 편집 거리: 악몽이 있는 문젠데요ㅠㅠ 그냥 적당히 DP하면 $O(NMK)$로 20점을 긁을 수 있어요. 만점 풀이

 

1/14 수요일

겨학 마지막 날이지만 휴텍 발표를 다녀오느라 참석을 안했어요!

 

13188 Kangroo: 커넥티드 컴포넌트 DP를 배웠습니다. 증명은 넘어가고 느낌만 알아갔는데 다다수가 데카르트 트리랑 일대일대응 시키면 된다고 해가지고 유레카!! 했습니다.

 

1/16 금요일

3419 Racing Car Trail: 이분 그래프에서 최대 매칭 가지고 열심히 따지면 됩니다.

31753 Clever Cell Choices: 3419

8472 Vacation: 재밋는 MCMF 모델링

 

18586 Salty Fish: 민컷 모델링 후 스몰투 라지 셋질 그리디를 하면 됩니다.

네트워크 플로우 4

 

31734 Tower: 점프 게임 상위호환인줄 알았는데 세그 안쓰는 매우 괜찮은 중국인 풀이가 있어요.

 

1/17 토요일

2025 고려대학교 프로그래밍 경시대회 (KCPC) - Div. 1

 

온사이트 대회 가서 2등했어요!!

덕분에 많은 상품을 받았어요 ㅎㅎ

 

Codeforces Round 1073 (Div. 2)

 

아제발밴안당해라아제발밴안당해라아제발밴안당해라

딥1 참가할걸 그랬어요!

 

1/18 일요일

Codeforces Round 1062 (Div. 4)

 

밤에 있는 딥4를 칠까말까 고민돼서 버추얼로 최근 딥4를 쳐봣어요.

하지만 밴당할것같아서 밤에있는 딥4는 안쳤어요 ㅋㅋ.

 

35171 Two Sets: 체커를 꼼꼼하게 만듭시다..

14510 Blazing New Trails: aliens trick