2025년 9월 둘째 주 PS 일지

9/8 월요일

Codeforces Round 1048 (Div. 1)

D도 풀고 2600 띄워서 개떡상할수있었는데언레래요ㅠ

 

9/9 화요일

15283 Archery Tournament: 교집합끼리는 겹치지 않고 최대 높이가 자신 이상인 원에서만 교집합이 생김을 이용해서 적당히 자구를 하면 됩니다.

 

9/10 수요일

31890 Turning Red: 적당히 그래프로 모델링 한 뒤 $3$가지 경우를 모두 해봅니다.

하아이날뭐했지??

 

9/11 목요일

31965 회의 장소: 중앙값 응애 누적합 응애

22341 사각형 면적

22342 계산 로봇

 

9/12 금요일

22343 괄호의 값 비교: 이진법 구현 응애

22344 그래프 균형 맞추기: 루트를 $x$라 하면 $x$의 값이 결정되거나 안 결정되는데, 안 결정될 때에는 중앙값을 잡으면 됩니다.

22346 일이 이어져야 좋다: 분할 정복

25407 외곽 순환 도로: 각 정점의 차수를 $3$ 이하로 해준 뒤 센트로이드 분할을 하면서 매번 $4$번의 다익스트라를 돌리면 됩니다.

 

9/13 토요일

2025 KUMOH ASK CONTEST (Open Contest)

 

M번을 퍼솔하고 다다스가 추천해서 K도 풀었어요.

 

2025 서울대학교 프로그래밍 경시대회 Open Contest

 

약간 뻘짓좀 많이 했는데 오픈컨 참가 적음 이슈 덕에 2등을 했습니다. E나 G를 못푼 것이 매우 아쉽습니다...

 

34116 직각이등변삼각형

25403 빨강파랑: 흔한 좌압 + 세그 + 스위핑 해줍니다.

25377 빵

25378 조약돌: 최적해의 꼴을 생각하면 dp가쉽게 나옵니다.

25379 피하자

28214 크림빵

28215 대피소

28217 두 정삼각형

28216 아이템 획득

32068 보물 찾기

32070 색깔 모으기: 그래프로 모델링하면 쉽게 나옵니다.

25015 아이싱: 결국 dfs tree 상에서 홀수 사이클을 모두 지나는 간선 $2$개 이하를 찾는 문제입니다. 집합 관리를 랜덤 + xor로 하면 쉽게 구할 수 있습니다.

19862 Koosaga's problem: 25105

 

KOI 2022 1차대회

KOI 2023 1차대회

KOI 2024 1차대회

 

1차대회 컷!

 

9/13 일요일

22347 공통 괄호 문자열 사전: sa lcp 이탐 쌀

22349 가장 긴 공통 괄호 문자열: 22347