2021 SCPC 예선 후기

[1차 예선]

후기는 쓰는 걸 까먹어서 없다. 문제 난이도는 전반적으로 어렵지 않았는데, 알고리즘 배치가 그리디 4개+Union-Find 1개인건 좀 그랬다..

 

[2차 예선]

이번엔 캡처를 까먹었다.. 내 점수는 1번+2번+3번+4-1번 = 681점이다.

 

[1번]

체감상 1차예선 1번보다도 쉬웠다. 원의 방정식을 알고 정수의 제곱근을 구할 수 있다면 어렵지 않게 해결할 수 있을 것이다.

 

[2번]

처음 봤을때는 잘 가늠이 가지 않았다. 그림을 조금 들여다보다 계산기에 \(8!\)을 넣었는데 40320이 나왔다. 굉장히 작다는 것을 깨닫고 풀이의 방향이 완전탐색임을 직감했다. 각 꼭짓점에 점들을 배정해준다면 거리는 간단한 관찰을 통해 구할 수 있다.

관찰 : 만약 직8각형을 일정 방향으로 밀었을 때 거리가 감소하는 점이 5개 이상이라면 무조건 미는게 이득이다.

이 관찰을 통해 거리가 감소하는 점이 4개 이하가 될 때까지 밀어줄 수 있고, 이를 x축과 y축 모두에 대해 진행해주면 된다.

 

[3번]

문제를 보고 가장 먼저 한 것은 주어진 모양에 대해 인접한 상태를 빼 보는 것이었다. 그렇게 한다면 \(K=2\)일때

    -1 1

-1 -1 1 1 

    -1 1

과 같은 모양이 나오게 된다. 이를 Prefix Sum을 통해 해결해준다면 2번 서브태스크인 \(O(N^3)\)풀이가 완성된다.

\(O(N^2)\)풀이에 도달하는 방법은 여러 가지가 있는 것 같다. 아래에는 내가 사용한 방법을 소개하겠다.

위에서 서술한 모양에 대해 한번 더 인접한 상태를 빼줄 수 있다. 그러면

   -1 2 -1

-1    2    -1

   -1 2 -1

과 같은 모양이 나온다. 이는 가운데 세로줄에 대한 누적합과 각 대각선에 대한 누적합을 계산해놓으면 모두 \(O(1)\)에 계산 가능하다. 따라서 전체 문제를 \(O(N^2)\)으로 해결할 수 있다.

 

[4번]

문자열 관련 공부를 거의 해놓지 않은 상태여서 전체 문제를 풀기는 힘들거라 생각했다.

Naive하게 해결되는 1번 서브태스크를 긁고 많은 생각을 해보았으나, 별다른 아이디어가 떠오르지 않았다.

 

[5번]

재밌는 문제 같다^^

 

점수 분포를 보니 본선 커트라인이 내 점수대 근처에서 형성될 것 같다.. 커팅을 열심히 해 4-2를 맞거나 5번에서 한자릿수 점수라도 긁었으면 지금보단 마음이 좀 편할 것 같다. 본선만 가게 해주세요..