NYPC 2024 본선 후기

개요

NYPC 2024 본선 대회를 가게 되었다.

중간고사가 화요일에 끝났고, 대회가 그 주 토요일이었기 때문에 준비할 시간이 거의 없었다.

화요일부터 금요일까지 기본적인 감만 회복해서 간 것 같다.

대회 전

밥을 먹고 넥슨을 갔다.

본선 진출자로서 간 건 5년째이고, 동반인으로서 간 것까지 포함하면 7년째이다.

분위기는 익숙했는데, 올해에는 아는 얼굴들이 많이 보여서 반가웠다.

대회가 시작하기 전에 친구들과 놀고 있는데 사진 찍어달래서 찍어줬다.

대회 중

1번(0:00~0:13)

1번 문제를 읽었다.

생각보다 어렵게 생겨서 당황했다.

$K \le 5$ 조건을 읽고 금방 DP 식을 떠올렸고, 이를 역추적하는 과정을 통해 답을 구할 수 있었다.

다행이 짜자마자 정답이 나왔다.

2번(0:13~0:24)

2번 문제를 읽었다.

1번 문제보다 아이디어를 요하는 문제 같았다.

그래프를 몇 개 그려서 경우를 따져보니 AA가 연결되는 경우와 ABA가 연결되는 경우만 견제하면 된다는 것을 알 수 있었다.

이 관찰을 하고 나면 구현은 매우 간단했고, 짜서 정답이 바로 나왔다.

3번(0:24~1:37)

3번 문제를 읽었다.

일단 기하라서 매우 당황했다.

컨벡스 헐 비슷하게 왼쪽 오른쪽 훑으면서 각 점을 커버할 수 있는 구간을 찾으면 될 것 같았다.

처음에는 long long 범위에서 해결이 될 줄 알았지만, 생각해보니 최대 10^36이 가능해서 __int128을 사용해야 했다.

다행히도 코드 블럭에서도 돌아갔고, 채점도 잘 됐다.

짰는데 몇 번 틀리고 바로 맞았던 것 같다.

4번(1:37~3:33)

4번 문제를 읽었다.

일단 k=0이라고 가정하면 정렬하고 차배열에서 거리 3 이상 떨어지게 고른 원소의 합의 최댓값을 구하는 문제로 환원이 가능했고, 이는 dp로 간단하게 해결이 가능했다.

k=1인 경우는 왼쪽부터 계산한 dp와 오른쪽부터 계산한 dp를 이용해서 간단하게 구할 수 있었다.

짰는데 계속 안 나와서 기분이 나빴다.

결국 66점 섭테가 나왔고, k=2인 경우를 고민하기 시작했다.

k=1인 경우와 다르게 k=2인 경우는 suffix와 prefix 뿐 아니라 구간에 대한 dp 값이 필요했다.

'구간에 대한 dp 값 --> 금광 세그'

3*3 배열을 변수로 관리하는 금광 세그가 떠올랐고, 바로 짜기 시작했다.

주어진 수와 원래 배열의 수의 대소 관계를 기준으로 6가지 경우가 나와서 이걸 짜다가 현타가 와서 접으려다 다시 생각을 했다.

사실 중간에 값을 끼워 넣는거라서 처음에 i번째 값을 3*i에 넣고, 중간에 값을 끼워 넣을 때 3*i-2, 3*i-1번에 넣으면 되는 것이었다.

이걸 짰는데 다행히도 바로 맞았다.

80점 테케에 걸리거나 당연히 안 나올 줄 알았는데 나와서 좋았다.

5번(3:33~4:00)

5번 문제를 읽었다.

감도 안왔다.

1번 테케라도 긁으려고 했지만, 2차원 세그 짜는 뻘짓 하다가 시간이 거의 다 갔다.

5분 전에 1차원 세그만 짜는 풀이가 떠올랐지만, 현타가 와서 안 짰다.

대회 후

대회가 끝났는데 풍선 4개인 사람이 나 말고 3명(jjang, mickeyjung, heeew) 밖에 없었다.

mickeyjung이랑 heeew가 414라길래 3등이기를 바랐다.

시상식

동상에서 내 이름을 불렀다.

시간차로 진 것 같다.

2년 연속 4등 동상이 슬펐다.

작년과 올해 모두 작은 시간 차이로 4등을 했다.

심지어 올해 5번 문제는 무지성으로 YES를 출력하면 14점이 나왔다고 했다.

;;

시상식 후

뒤풀이를 가기로 했지만, 피곤해서 집 가서 밥 먹고 놀다가 잤다.

ㅜㅜ

요약

1. 중간고사 이슈

2. 400 받음

3. 4등함 ㅜㅜ

 

ㅜㅜ