오늘의 PS (25) - 230719 (제7회 천하제일 코딩대회 Open Contest)

적당한 시간대에 오픈컨이 있길래 가서 쳤다. 처음엔 사람들 닉네임이 무서워서 쫄았는데, 문제들이 어렵지 않아서 결과가 나름 괜찮게 나왔다. 따라서 후기를 써 보려 한다. 카테고리는 적절한 곳이 없어서 거의 1년 만에 오늘의 PS를 부활시켰다. 다음 글이 언제가 될진 잘 모르겠다..

 

셋: https://www.acmicpc.net/category/detail/3626

 

A. 10! (0:01, +) *B4

구현해주면 된다. 0분대 솔브도 가능했을 것 같은데 똑똑한 방법을 찾지 못하고 계산기로 10!/6을 계산하느라 조금 늦었다.

 

B. 고양이 카페 (0:06, +1) *S3

비슷한 문제를 굉장히 많이 봐서 바로 짰다. 제일 작은 원소부터 가능한 원소와 매칭시켜 주면 된다. upper를 lower로 잘못 써서 한 번 틀렸다.

 

E. 부정행위 멈춰! (0:10, +) *S3

이후로는 스코어보드를 따라갔다. 2*2 단위로 나누어 1 2 3 4 를 하나씩 적어 주면 된다. \(N=1\)이거나 \(M=1\)인 경우에만 유의하자.

 

G. 생일 맞추기 (0:16, +) *B1

그냥 짜면 되는 브루트포스 문제이다. 그냥 짜서 맞았다.

 

H. 수열의 가치 (0:24, +) *G4

중복 원소는 처리하기 귀찮으니 묶어서 생각하자. 모든 원소가 다 다르다면 당연히 하나만 두 수열에 모두 포함될 수 있다. 따라서 묶어서 생각한 후, 원소의 값과 등장 횟수의 곱이 최대인 것만 2번 더해주면 된다. constructive는 그냥 정렬해서 출력해도 된다.

 

F. 사탕 나눠주기 (0:28, +) *S2

파라메트릭 기본 문제이다. 그냥 짰다.

 

I. 양동이 게임 (0:38, +) *G5

DAG에서 DP를 조건 그대로 돌려주면 된다.

 

J. 크리스마스 (0:46, +) *G4

기본적인 전략은 2칸 앞->1칸 뒤->2칸 앞이다. 이러면 3칸씩 갈 수 있으므로 \(N\)을 3으로 나눈 나머지에 따라 앞 뒤에 처리를 조금만 해주면 된다.

 

D. 무한 수열 (1:20, +) *P5

고른 구간이 첫 반복을 넘어가지 않는 경우는 DP로 처리해주자. 이제 넘어가는 경우는 \(i\)번째 위치에서 시작해 중간에 크기 \(N\) 단위의 구간을 \(k\)개 포함한 후, \(j\)번째 위치에서 끝나는 경우이다. 이를 수식으로 표현하면 \(k\)에 대한 이차식이 되고, 미분을 하면 최적인 \(k\)를 구할 수 있다. 그리고 식이 변수 분리가 되는 형태이므로 끝 위치에 대한 식과 시작 위치에 대한 식에 대해 최적인 값을 찾아 계산해주었다. 식 정리가 상당히 더러웠는데 다행히 정해는 좀 깔끔해 보였다.

 

C. 링크 컷 토마토 (1:36, +) *P5

이름이랑 입력 형태가 상당히 무서워 보이지만, 읽고 나니 별로 어렵지는 않았다. ODC의 아이디어처럼 각 간선의 lifetime을 구한 후 다익스트라를 잘 돌려주면 된다.

 

퍼솔도 없고, 평소보다 속도가 그리 빠르지 않았는데 D를 더럽게 푼 덕분에 한 번에 맞아 준우승을 차지할 수 있었다. 오픈컨 준우승은 3번째인데 다음에는 우승을 해 봤으면 좋겠다.