2025년 7월 둘째 주 PS 일지

7/10 목요일

 

나코더 시간에 realpsdoingdamyoo가 애드혹 강의를 했고 시간이 많이 남아서 애드혹 땅따먹기를 했어요!!

 

29768 팰린드롬 이름: 자명한 애드혹
20921 그렇고 그런 사이
7142 데이터 만들기 3: 정점 101개 있는 그래프 구성
32714 방벽 게임
12905 거짓말쟁이: 문제를 XOR 복원하는 문제로 환원시킨 뒤 처음값과 끝값을 고정해 1차원 DP가 가능합니다.
2278 그래프 복원: 최소 스패닝 트리 구성하듯이 작은 쌍부터 순서대로 필요한 간선을 추가해 주면 됩니다. 제한이 작아서 어떻게 구현하든 상관없습다.

 

7/11 금요일

28201 5: 구하는 값을 $(x, y)$ 위에 올리면 $(1, 1)$ 의 개수 조건 덕분에 대각선으로는 구간이 최대 $5$ 개만 나옵니다. 따라서 나이브하게 관리해 줍니다.

 

7/12 토요일

2109 순회강연: 자명한 그리디

 

UCPC 2025 예선 Open Contest

 

kuhyaku, realpsdoingdamyoo와 undertaker라는 계정으로 참여해서 9솔로 2등을 했습니다. 1등은 국가대표 팀이 했습니다.

제가 한 것만 쓰자면 I를 19분에 풀었고 H를 뻘짓좀 하다가 66분에 퍼솔을 했습니다. 

이후에 F가 DP를 세그먼트 트리로 최적화하는 문제인 것을 깨닫고 CDQ 알고리즘을 구현하다가 TLE를 만나고 뚫어보려고 커팅을 시도했습니다.

결국 실패하고 K를 잡았습니다. 센트로이드 분할과 롤백 CHT를 잘 쓰는 사풀이를 냈고 1시간동안 구현하다가 사풀임을 7000B를 짜고 깨달아 접었습니다.

남은 두 친구의 캐리로 9솔 2등, 본대회 기준 16등을 했습니다.

 

34059 해안선

34060 로봇 청소기

 

7/13 일요일

34057 시장조성하기: DP를 세그먼트 트리로 최적화하는데 $[SA_i, SB_i]$ 구간의 길이가 단조 증가함을 이용해 차원을 하나 줄이고 $O(NlogN)$ 스위핑으로 해결해 줄 수 있습니다.
20693 Writing Tasks: 삼각형을 정점으로 한 그래프를 구성하고 최대 독립 집합을 구합니다. 컴포넌트 크기가 8 초과면 무조건 각 정점의 차수가 2 이하가 되므로 $O(1)$에 처리해 주면 되고 나머지는 $O(2^V E)$로 처리해 주면 됩니다.