2025년 5월 셋째 주 PS 일지

5/12 월요일

6292 Tracks in the Snow: 0-1 BFS. 대충 컴포넌트를 제거하는것으로 생각하면 최대 깊이 계산해주면 됨

 

5/13 화요일

32009 Magic Show: 중나정

14523 Switch Grass: MST 만들고 셋질

18796 이동하기 4: 루트에 체인 2개 달고 페이커 알고리즘 사용

24943 Sightseeing in Kyoto: 18796

6043 Cow Politics: 가장 깊은 노드만 보기(트리의 지름 느낌)

 

5/14 수요일

30095 GCD SUM: $i$를 고정시키면 서로 다른 $gcd([i, j])$ 값은 대충 로그개임을 이용한 누적합

33844 트리의 색깔과 쿼리: 3d mos + tree mos

 

5/15 목요일

17711 Sushi: 루트질. 구간을 루트개로 나눌때 끝에 애매한 부분에 대해서 레이지 처리

21179 Derangement Rotations: 수학

 

5/16 금요일

10848 팔렘방의 다리: [1, i]에서 중간값 찾기

 

5/17 토요일

APIO 2015를 응시했습니다.

 

15311 약 팔기: 1 1000개 1000 1000개

1199 오일러 회로: 오일러 경로와 오일러 회로를 배웠습니다.

18250 철도 여행: 오일러 회로

 

5/18 일요일

11603 Checkers: 더러운 오일러 회로

11647 Chckers: 11603

31928 Removing Verticles: dfs tree 위에서 그리디

23852 Ekoeko: 결국 최종 수열이 결정됐을때 인버젼 수가 횟수이므로 이를 최소화해야 합니다. 그리고 같은 문자 내에서 뒤의 절반에 해당하는 수들은 최종 수열에서 + N 인덱스가 추가되기 때문에 이 문자들만 따로 분리해서 봐도 됩니다. 결국 이 문제는 (a, b) N개를 배열해서 첫 번째 수들로만 이루어진 수열의 인버전 수와 두 번째 수로만 이루어진 수열의 인버전 수의 합 최소화가 됩니다. 잘 생각해 보면 둘 중 하나를 정렬시키는 것이 무조건 최소가 됨을 알 수 있습니다.