1/27 월요일
27511 야유회: 이런 건 어떻게 생각하고 어떻게 출제하는지 모르겠습니다.
1/28 화요일
33318 입자 가속기: 선발고사 문제 업솔빙을 했습니다.
1/29 수요일
11469 Distribution in Metagonia
32592 Intelligence Exploration
pk661, kuhyaku와 함께 플랜디를 했습니다. 좋은 문제만 고르기 위해서 숏코딩이 짧은 문제들만 선별했다가 플하위로만 구성된 셋이 됐습니다.
17474 수열과 쿼리 26: 세그먼트 트리 비츠를 배웠습니다.
19455 Bitwise Queries: 제 첫 루비 자력솔(?) 입니다. 사실 기본 난이도가 다1인 알고리즘이라 루비 자력솔이라고 하기도 애매하지만..
commonnick과 루비5 먼저 도달하기 대결했습니다. 루비5까지 26 레이팅이 남았을 때 위와 같이 랭작을 밤새 하여서 먼저 루비에 도달했습니다.
이제부턴 정당하게 레이팅을 올리도록 하겠습니다. ㅋㅋ
1/30 목요일
17738 Voltage: DFS Spanning Tree에서 누적 합을 활용하여 효율적으로 계산할 수 있습니다. 문제에서 구해야 하는 것은 모든 홀수 사이클에는 포함되면서, 어떠한 짝수 사이클에도 속하지 않는 간선의 개수입니다. 이때 Back Edge는 홀수 사이클을 생성할 수 있지만, 홀수 사이클이 2개 이상 존재하는 경우, 모든 홀수 사이클에 공통으로 속하는 Back Edge는 존재할 수 없음을 증명할 수 있습니다. 따라서, Tree Edge만 잘 따져주면 됩니다.
방법은 다음과 같습니다. Back Edge가 사이클을 생성할 때, 해당 경로에 사이클 크기의 기우성에 따라 1을 경로에 더해줍니다. 마지막에 각 간선이 어떠한 짝수 사이클도 지나지 않고, 모든 홀수 사이클을 지나는지 확인하면 됩니다. 이를 누적 합을 이용하면 $O(M)$의 시간복잡도 안에 해결할 수 있습니다. 제 코드입니다.
kuhyaku, realpsdoingdamyoo와 JOI 2013/2014 JOISC Day 3 셋을 돌았습니다. B, C는 업솔빙했습니다.
2/1 토요일
F를 별해로 뚫고 G도 이상한 DP 식을 세우다가 멸망했습니다. 어서 옐로 가고 싶은데 앳코더는 델타가 너무 짜네요. ㅠㅠ. 엉엉 울어야지
2/2 일요일
어차피 언레라서 A 풀고 E1으로 갔습니다. mj1000j orz. 막 주변 사람들이 누텔라 퍼포를 받네요.
'PS' 카테고리의 다른 글
| 2025년 2월 둘째 주 PS 일지 (4) | 2025.02.17 |
|---|---|
| 2025년 2월 첫째 주 PS 일지 (0) | 2025.02.10 |
| 2025년 1월 넷째 주 PS 일지 (2) | 2025.01.20 |
| 2025년 1월 셋째 주 PS 일지 (2) | 2025.01.20 |
| 2025년 1월 둘째 주 PS 일지 (0) | 2025.01.13 |
