SCPC 2021 2라운드 풀기

1라운드 컷은 아마 2문제 조금 안되는 선이었던 것 같다.

SCPC 1라운드를 통과하면 2라운드를 치고, 2라운드까지 통과하면 키보드와 장패드(중요) 를 받을 수 있다.

그리고 그 2라운드는 8월 7일 토요일, 9시부터 21시까지 열렸다.

 

대충 문제는 이렇게 건드려서 이렇게 풀렸다.

3번 "산탄총"의 벽을 끝내 넘지 못하고 장패드로의 여정은 여기서 저지당했다.

2번이 생각보다 빨리 풀려서 기분이 좋았었는데 점심 먹은 이후에 집중력이 후달렸나...

2번까지 풀고 기쁜 마음에 찍어보았다

 

자 그럼 1번부터 한번 풀어보자.

---

1번. 원 안의 점.

반지름 R이 주어졌을 때, 그 원 내부에 있는 정수 좌표의 개수는?

 

1번인 만큼 매우 간단해서 출석체크용 문제이다. 

그냥 세면 된다. 주의할 점은 원 위에 있는 점은 빼야 한다는 것인데, 친절하게 테케에 있었다.

나는 두 번 제출 해서 맞았는데 아마 정답을 long long이 아니라 int로 저장해서 처음에 틀렸던 것 같다.

 

2번. 직8각형.

한 변의 길이가 K인 정사각형 5개를 열 십자 모양으로 배치하면 가장자리에 꼭지점 8개가 생긴다. 이 꼭지점을 이은 도형을 직8각형이라고 부르자. K와 임의의 좌표 8개가 주어졌을 때, 주어진 좌표를 가장 적은 비용으로 옮겨서 직8각형을 만드려면 얼마만큼의 비용이 필요한가? 비용은 L1 거리이다.

발로 그렸지만 그림으로 보면 직8각형은 대충 이렇다.

뭔가 최적화 문제같기도 하고 처음보는 문제 같았기 때문에 문제를 보고 당황했다. 침착하고 1차원으로 내려서 생각하면 아래 그림과 같다.

기본적으로 아래 파란색과 같은 머리빗이 나오며, 이 빗을 잘 움직여서 원하는 지점에 가장 가깝게 가져다 대면 된다. 빗의 빗살 하나마다 점은 2개씩 들어가며 간격은 모두 같다.

대충 생각해봤을 때 극값은 항상 경계 케이스에 있으므로, 타겟으로 하는 점들이 빨간색 X표와 같이 분포한다고 가정하면 저 빗살선을 모든 빨간 X 바로 위에 오는 경우를 모두 체크해보면 된다.  4 X 8 해서 32번만 돌리면 정답을 알 수 있다.

 

그런데 문제는 이게 1차원이 아니라 2차원이라는 점이다. 타겟으로 하는 좌표들이 어느 지점에 해당하는 지 알 수가 없다. 좌표대로 정렬해서 훑으면서 경계를 매칭하면 1차원은 그냥 해결되지만, 2차원은 아니다. 이 타겟 좌표들이 직8각형의 어느 부분에 해당하는지 알 수가 없다. 

 

그런데 좌표가 8개 밖에 안되므로 8! = 40320 정도 수준으로 가벼우니, 그냥 next_permuation을 돌려주면 된다. permutation을 돌려서 target 좌표가 어느 위치에 있든간에 직8각형의 모든 좌표에 한번씩 겹쳐지면서 거리를 체크하게 된다. 

 

3번. 산탄총

격자 표적지에 점수가 적혀 있다. 마름모 모양으로 퍼지는 산탄총을 쏠 때, 얻을 수 있는 최대 점수는? 단, 중앙에 맞은 표적일수록 xK 배를 하며, 가장 가장자리에는 X1배를 한다. 표적 밖에도 쏠 수 있다.

풀이는 부분합을 덕지덕지 붙이면 된다. 

구체적으로는 대각선 부분합과 직선 부분합을 전부 구해뒀다고 생각하고, 마름모를 오른쪽으로 한 칸 옮길 때 어떻게 차이를 메꿔줄 수 있을지 생각해보면 금방 나온다.

 

지금 보니 쉬워 보이지만, 당시에는 한참 헤맸다. 모양이 너무 이상하고 배수가 들어가다 보니까 뭔가 다른 방법이 있을 줄 알았는데 부분합이라는 방법도 3시간 남겨두고 겨우 생각이 났던 것 같다. 마감 직전에 그냥 브루트포스로 짜서 부분점수를 받았다.

 

4번은 아호-코라식이라고 하는 오토마타 같은 문자열 매칭 알고리즘으로 풀면 만점이 나온다고 하고, KMP도 부분점수가 후하게 나왔다는 것 같다. 나는 시간복잡도 계산을 잘못해서 KMP도 시도하지 못했다.

극악의 5번은 위-아래 원반을 삭제시켜도 중앙값에는 영향이 없다는 성질을 이용해 sub-problem으로 나누면 된다고 한다...

---

 

3번까지는 그래도 누구나 아는 알고리즘이라 풀 수 있었던 것 같은데 수행이 부족하다.

앞으로 4트 정도 남은 것 같은데 장패드 받고 싶다.