2024년 10월 넷째 주 PS 일지

10/21 월요일

3955 캔디 분배

 

10/23 수요일

27557 Moo Route

 

10/25 금요일

4002 닌자 배치

 

10/26 토요일

NYPC 본선에 갔습니다.

1. 라운드 기록 복원하기

R을 $+1$, B를 $-1$로 생각했을 때 누적합은 최대 10가지가 존재하므로 $dp[N][K]$: $N$ 번째까지 보았을때 누적합이 $K$인 것이 가능하나? 로 상태 정의를 해서 DP를 이용해 풀었습니다. 처음에 가능 여부가 아닌 경우의 수를 저장했더니 오버플로우로 틀리는 경우가 발생했었습니다. 40분 정도 소요했습니다.

2. 던전 디자인

문제를 보자마자 간선으로 이어진 두 보상 상자 방이나 보상 상자 - 몬스터 - 보상 상자와 같은 구조 2개만 보면 된다는 것을 생각해 구현했고 10분 정도 걸려서 AC를 받았습니다. 

3. 붐힐 마을 경비 활동

지점마다 관찰이 가능한 경비대원의 범위를 구해주고 이들을 그리디하게 스위핑으로 관리해 주면서 최소 경비대원 수를 구해줄 수 있음은 바로 알았습니다. 이후 조금만 고민해 보니 스택을 이용해서 점들이 볼록하게 유지되고 접선을 바로 찾아줄 수 있음을 깨달아 구현해 줬습니다. 40분 정도 걸려서 발상과 올바른 구현을 모두 해냈지만 계속 WA가 떴습니다.

결국 방식을 수정해 가며 이 문제에 2시간가량 더 소모했으나 AC를 받을 수 없었습니다. 나중에 맞은 사람들의 풀이를 들어보니 실수 오차 때문에 float128이나 int128을 이용하거나 분수 구조체를 직접 만들어 실수 오차를 줄여야 맞는다는 사실을 듣고 너무 아쉬웠습니다.

4. 훈련 프로그램 II

실력을 기준으로 정렬한 다음에 길이 3 이상의 여러 구간으로 나눠서 $2 * (\text{구간의 최댓값} - \text{구간의 최솟값})$ 들의 합을 최소화해야 한다는 문제라는 것은 찾아냈습니다. 이때 길이가 6 이상이면 더 작은 구간들로 나누는 게 더 유리하다는 것을 생각해 내지 못해서 매 쿼리마다 구간 DP를 짰고 $O(QN^3)$의 알고리즘을 짜 섭테 1 21점을 긁었습니다. 남은 섭테는 3번에 미련을 버리지 못해 잡고 있다가 긁지 못했습니다.

5. 타일 마스터의 시련

읽어보지도 못했습니다. ㅠㅠ.

 

결과 및 후기

221점을 받았습니다. 한 20~30등 했을 것입니다. 3번이 다들 풀이는 찾았지만, 실수 오차로 AC를 받지 못했던 문제인데 실수 오차임을 한 번이라도 의심해 보고 다른 방법으로 구현해 보면 어땠을까 후회가 남습니다. 내년에는 꼭 노트북을 타고 싶습니다.
끝나고는 동상을 받은 Kawaii2DIdolOfGSHS, 15631164, jalapen0p1ckle, lupin0000과 뒷풀이를 했습니다.

 

10/27 일요일

27539 Cat Exercise