[알고리즘] 2021 SCPC 후기 (Round 2)

> 2021 SCPC Round 1 후기 보기 <

2021.07.18 - [대회후기] - [알고리즘] 2021 SCPC 후기 (Round 1)

[알고리즘] 2021 SCPC 후기 (Round 1)

---

2021.08.07 일자로 2021 SCPC 2차 예선을 마쳤습니다.

어제 오후 5시부터 아침 8시까지 야간근무 후 돌아와 9시부터 사지방에서 12시간 동안 대회를 치뤘습니다. (허리 ㅠㅠ)

난이도는 1차에 비해 확연히 어려워진 것 같고, 애매한 점수에 실수를 잦아 많은 제출 횟수로 통과할 수 있을지는 모르겠네요..

제가 알기론 SCPC 2차 컷이 450~700점 정도에 100~200명 통과로 알고 있는데 확실히는 모르겠습니다.

이번에는 문제 당 100,200,300,400,500점으로 문제 번호가 높을 수록 편차가 심하였는데, 이번 5번 문제인 Hanoi Tower는 만점자가 0명인 상태로 끝났습니다. (풀어보신분들은 난이도를 아실겁니다..)

이번에도 코드없이 풀이만 남겨보도록 하겠습니다.

---

문제1. 원 안의 점 [100 / 100]

알고리즘 : 이분탐색

문제1 원 안의 점은 중점이 0,0인 원의 반지름이 r일 때 그 안에 속하는 정수 좌표 개수를 구하는 문제입니다.

처음에 규칙으로 풀어보려다 예외에 빠져 조금 고민하게 되었는데 r의 범위가 최대 200,000이므로 한 좌표계를 순회하면서

1 ~ 200,000 사이의 좌표 하나를 잡아 불가능 할 때까지 upper_bound로 이분탐색합니다. 중점과 x,y선 값만 처리해주고 방금 구한 값을 4배 해주면 네 분면의 좌표 개수를 구할 수 있습니다. 이를 활용하여 O(rlog r)에 해결합니다.

---

문제2. 직8각형 [200 / 200]

알고리즘 : 기하 / 경우의 수 / 구현

문제2 직8각형은 기하 문제입니다. 2차원 평면 문제는 손으로 그리기가 힘들어서 (1,2번 둘다..ㅎㅎ) 종이 많이 써먹었습니다. 처음 DFS를 돌려 주어진8점을 어떤 순번으로 각 모서리를 맡게할지 8!개의 경우를 구합니다. 그리고 구하기 쉽게 하기 위해 (10억,10억) 좌표에 직8각형을 만들어 각 경우에 대해 최소 움직임을 보장하는 경우를 구한 뒤, 5개 이상이 움직임이 양수일 경우를 처리하여 해결결하였습니다. 출력값에 Case 안 적어서 두어번 더 틀리고 해결하였습니다.

---

문제3. 산탄총 [154 / 300]

알고리즘 : Dynamic Programming / 부분합

문제3 산탄총은 부분 케이스 2까지 DP와 부분합을 이용하여 풀이하였습니다. 빈 사격지에도 쏠 수 있으므로 (3*N)^2*K라는 시간복잡도가 나왔습니다. K 범위를 쏘는 산탄총은 피격지로부터 마름모 모양으로 사격됩니다. 이를 이용하여 i,j를 사격할 때 left, right를 j로 두고 bottom과 ceil을 i + k - 1, i - k로 두어 부분합 DP를 응용하여 left -1, right +1, bottom + 1, ceil - 1을 반복하면 반복해서 더해지는 범위가 문제에서 원하는 곱범위와 같아집니다. (그리면서 생각하면 편합니다.) 이를 이용하여 아슬아슬하게 9 try에서 풀이했습니다.

---

문제4. 패턴 매칭 [81 / 400]

알고리즘 : ?

문제4 패턴 매칭은 문자열 문제입니다. 처음 보면 KMP가 떠올랐지만 문자열 알고리즘에 대한 숙련도가 부족하여 브루트포스로 부분 테스트 케이스를 얻었습니다. 초기 문자열과 패턴문자열을 확인하여 패턴 문자열 길이만큼 각 문자의 위치를 (str[i] - 'A')번째 배열에 저장한 뒤, 해당 패턴이 동일한 지를 확인하는 방식으로 결과 값을 도출해냈습니다.

---

문제5. Hanoi Tower [FAIL / 500]

알고리즘 : ?

문제5번 Hanoi Tower입니다. 우리가 아는 하노이탑과 다르게 중간에서만 뺄 수 있으며 중간에만 넣을 수 있는 극악의 조건을 가지고 있습니다. 중앙값 알고리즘(minHeap, maxHeap) 그리고 휴리스틱을 이용하여 부분 테스트 케이스만 챙기려고 했으나, 악조건에 갇히는 경우를 해결하지 못해 풀이하지 못했습니다. [ ( 1 ) ( 0 ) ( 2 3 ) 인 경우 ( 1 ) 을 ( 2 3 )옮기지 못함 ]

만점자는 끝내 나오지 않았고, n이 6이면 부분점수를 1점 주는데 비트마스킹 완전탐색으로 풀어볼걸 하는 아쉬움이 있습니다.

---

본선에 도달하면 휴가내서라도 나갈텐데 붙으면 좋겠습니다. 대회 참여하신 모든 분 좋은 결과 있기를 기원합니다.

2021.08.15
본선 탈락하였습니다. 본선컷이 680점 정도 된다고 하네요. ㅠㅠ

---

태그 : #2021 SCPC #2021 SCPC후기 #SCPC 풀이 #SCPC 합격컷 #SCPC 원안의점 #SCPC 직8각형 #SCPC 산탄총 #SCPC 패턴매칭 #SCPC Hanoi Tower #2021 SCPC 2차예선 #2021 SCPC 본선 #2021 SCPC 점수