2025년 6월 셋째 주 PS 일지

6/17 화요일

10094 Computer Network: BFS 트리 응용으로 최단 경로 찾기

13482 Java2016: 1, 2를 만드는 방법으로 2의 거듭제곱 모두 만들고 이진법

6291 Brunhilda’s Birthday: 매번 최대한 줄이는게 이득임을 이용한 DP를 합니다. 매번 최대한 줄이는 양을 전처리 하기 까다로웠는데 모듈러의 특성을 이용해서 imos법 처럼 하면 됩니다.

15403 Escape Room: 가장 큰 수부터 보면 permutation이 하나로 정해짐

 

6/19 목요일

19028 Link Cut Digraph: Solar Lamps와 비슷한 분할 정복 + SCC 구하기

31557 Cowlendar: 4개의 수를 볼 때 6개의 차 중 $L$의 배수가 존재 해야 하므로 $L$의 후보를 유의미하게 줄일 수 있습니다. 이후에는 브루트포스를 합니다.

26012 Breeding Bugs: 콰닉의 정리 + 홀짝성을 이용한 이분 그래프 모델링 + 이분 매칭

 

6/21 토요일

10068 구슬이 서말이라도 꿰어야 보배: 조건 분석 후 트리 DP. 조건 분석이 까다롭습니다..ㅠㅠ

30963 인형 뽑기: 간단한 기댓값 DP

 

EJOI 2023 Day 2

31203 Square Grid Puzzle

31204 Tree Infection

 

kuhyaku, realpsdoingdamyoo와 같은 셋을 돌았습니다.

 

간단하게 쓰자면 1번을 읽고 10분 정도 생각하다가 풀이가 떴고요 permutation을 구하는 부분을 여러 그리디를 시도해 봤지만 모두 틀려서 고생했습니다.

근데 백트래킹을 하니깐 바로 맞더라고요.

 

그다음 2번을 읽었는데 이는 1번보다 쉬웠고 25분 정도 걸려서 AC를 받았습니다.

 

3번을 읽고 문제가 결국 매번 $\sum\limits_{i=1}^n S_i \times (N-i)(i-1)$의 최댓값을 구하는 문제임을 빠르게 찾았습니다.

이를 검증하는 나이브 서브테스크를 맞아 검증도 했습니다.

이를 $\sqrt{N}$개의 버킷으로 나누면 잘 풀릴 것 같아서 힘들게 구현해 줬으나 홀짝성을 고려하지 않은 바보 같은 구현을 했고 다다스가 루트질이 아닌 세그 풀이를 스포해서 슬퍼져 푸는 것을 그만했습니다.

최종 점수는 251점이었습니다.

 

6/22 일요일

33609 멋진 구간: 조건 분석을 열심히 하고 세그먼트 트리로 잘해주면 결국 선분 $O(N)$개가 나오고 직사각형 내의 점의 개수를 처리하는 쿼리 문제로 바뀝니다. 이는 섹시한 느리게 갱신되는 세그먼트 트리로 처리해 줍니다.