2026년 1월 둘째 주 PS 일지

1/5 월요일

26867 Easily Distinguishable Triangles: 행/열 분리

18473 Fast Spanning Tree: 알람 보내기 테크닉

 

1/6 화요일

오늘부터 겨울학교해요!!

 

이 날에는 IOI 2020 Day 2를 돌았습니다!

19938은 이미 푼 문제였고 나머지 2개는 처음 본 상태에서 (2번째 문제가 루비급이라는건 알고 있었습니다) 100 80.3 100을 받았습니다. ㄱㅆㅅㅌㅊ

 

19936 Pasking Biscuits: 식정리를 한 뒤에 시복이 보장되는 DP

19937 Counting Mushrooms: sqrt decomposition + Eㅓ러운 최적화

 

15767 Circle Selection: 좌표평면을 잘 분할해주기

 

1/7 수요일

18275 32834 20042 30852로 이루어진 셋을 돌았습니다. 마지막 문제는 매우 최근에 푼 문제였고 올솔을 했습니다.

 

18275 Sob: 분할 정복을 잘 해준다

32834 Pair Sorting: 믿음을 가지고 그리디를 해준다

20042 Hotspots: 한 컴포넌트에서 적어도 한 친구는 $0$이여야 하기 때문에 그 친구를 고정시킨 뒤 남은 점들의 길이를 고정시키면 state가 $O(N^2)$개 나옵니다.

 

20172 Electric Vehicle: 추가문제로 나왔는데 얘도 몇가지 관찰을 한 뒤 잘 생각해주면 state가 $O(N^2)$개 나옵니다. 재밌어용!

 

1/8 목요일

우범 지역 20039 23575 25952로 이루어진 셋을 돌았습니다. 마지막 문제는 매우 최근에 푼 문제였고 100 100 0 100을 받았습니다.

 

SCPC 2020 1차 예선 우범 지역: $(A, B)$를 중심으로 하는 극좌표계에 올린 뒤 볼록 껍질이 $(A, B)$를 포함시키지 않는 필요충분 조건을 생각하면 선택한 점들이 $[x,x+\pi)$ 세그먼트에 소속되게 하는 $x$가 존재함임을 알 수 있습니다. 따라서 적당히 슬라이딩 윈도우 + 곱셈 세그먼트 트리를 이용해줍니다.

20039 Coronavirus Trend: 그냥 DP를 세그로 풀기

23575 Squid Game: $Y$를 $Y mod X$로 바꿔주기

 

31069 순열 그래프: 추가문제로 나왔고 적당히 BCC로 나눈 뒤 좀 섹시한 dfs tree 구성법을 이용하면 됩니다.

19932 Painting Squares: 1616

 

 

솔브닥 마스터를 갔어요! 28002 풀고 가려고 하긴 했는데 착한 친구들이 1 남았다고 올려줬네요 ㅎㅎ^^

랭작?을의도로 한건 아니고 친구들이 푼 재밌는 문제들 북마크해놨다가 겨울방학이 돼서 밀기 시작했는데 그 문제들이 모두 다 고티어라 레이팅이 빠르게 올랐네용.

마스터가 너무 많아지는 것 같은데 빨리 솔브닥은 다다스의 의견을 받아 중국 티어를 도입하면 좋을것 같아요 ㅎㅎ

 

1/9 금요일

1등 단어 | 수열 연산 | 타이젠 윷놀이 로 이루어진 셋을 돌았습니다. 문제가 모두 쉬워서 올솔을 했습니다..

 

SCPC 2021 본선 1등 단어: SA 배열을 만든 뒤 앞에서부터 그리디하게 잘라줍니다.

SCPC 2022 2차 예선 수열 연산: 최소 횟수는 자명하고 합은 좌압을 해준 뒤 범위를 최소한으로 키워주기를 반복하면 됩니다.

SCPC 2023 2차 예선 타이젠 윷놀이: ㅗ 적당히 처리를 해주고 functional graph를 만들어준 뒤 잘 처리해줍니다 ㅗ.

 

15689 Catch the Plane: 그냥 적당히 스위핑하면서 DP를 합니다.

15699 Wireless is the New Fiber: 디그리 깎기를 그리디하게 해주고 트리도 그리디하게 해서 만들어줍니다.

 

28002 Security Guard: 진짜 레전드 문제에요... 약간 지금까지 ps하면서 본 문제 중 가장 아름다운 문제같아요.

 

1/10 토요일

모의고사를 봤어요!

대충 55 100 100 45를 받았고요 2등을 햇어요!! 1등 변재우 죽어라

25737 ARC 183 E 24438 34581 로 구성된 셋이에요! (ARC 183 E 풀이)

ㅅㅅ

 

1/11 일요일

IOI 2017 Day 1을 돌았습니다.

Wiring에 3시간 가까이 박았는데 풀이가 터져서 망했고요 Nowruz에서 급하게 87점가량을 긁고 Toy train에서 5점을 긁었어용.

이후 Wiring은 풀이를 안듣고 업솔빙에 성공했어요 ㅎㅎ.

 

20076 Nowruz: 만점은 못받고 휴리스틱 + dfs + bfs를 잘 결합해 92.67을 받았습니다.

20077 Wiring: 최적해의 꼴을 열심히 따진 뒤에 각 컴포넌트의 대표 간선을 정한다고 생각하면 DP가 됩니다!

20078 Toy Train: 매번 의미 없는 충전소를 제거해줍니다.

1628 수: 20077

1659 수(Hard): 20077

1144 싼 비용: 커넥션 프로파일 DP를 배웠어요.