SCPC 2023 (삼성 대학생 프로그래밍 경진대회) 예선 1차 후기

인증을 하고 싶지만 안타깝게도 스샷을 남기지 못함

아 여기서 볼 수 있었구나

 

 올솔...을 하지 못하고 5번 문제에서 180점을 날렸다. 1234는 만점을 받았다.

 대회는 24시간이었는데 당연히 24시간을 다 쏟아붓지는 않고 6시간 정도는 박은 것 같다. 1234 푸는 데 4시간, 5번 왜 억까당하는지 체크하는 데 2시간... 이상한 실수를 많이 했는데, 3번에서 64비트 정수를 안 써서 틀린다든지 하는 짓을 많이 했다. 1 -> 2 -> 3 -> 5 -> 4 순으로 구현했는데 3번 64비트 정수를 안 써서 억까당하고 5번 오답 떴을 때 '아 내 실력이 고작 이 정도인가'하고 멘탈 나가는 줄 알았다. (사실 1, 2번만 풀어도 2차는 진출한다는 얘기가 있으므로 그럴 필요가 전혀 없었다.)

 

 1. 증강현실 배달 안경 (예측 S5-S3)

 브루트포스를 한다.

 

 2. 딸기 수확 로봇 (예측 G4-G3)

 가능한 경우의 수가 3가지다.

 1) 무지성으로 오른쪽으로 간다.

 2) 무지성으로 왼쪽으로 간다.

 3) 한 방향으로 갔다가 특정 지점에서 유턴한다.

 1번과 2번을 구현해보면 알겠지만 어느 지점에서 멈추게 되는지는 binary search로 쉽게 알 수 있다. 정렬을 해 준 다음에 std::lower_bound, upper_bound 함수를 사용하면 된다. 따라서 3번을 구현할 때 도달할 수 있는 모든 지점에 대해 그 지점을 유턴 지점으로 하면 최댓값이 나오는지만 확인해 봐도 시간복잡도가 O(nlogn) 수준밖에 나오지 않는다.

 

 3. 장난감 (예측 P3)

 예제를 보면 알 수 있듯이, sum이 n 이상이면 답은 항상 1이다. sum이 n 미만이면, 최종 수열은 항상 0과 1로만 구성되어 있을 것이라는 사실을 쉽게 알 수 있다.

 이 최종 수열을 O(n) 안에 구하는 것이 첫 번째 난관이다. 관찰해보면, 1개의 구슬을 시계 방향으로 옮기는 것은 1개의 구슬만 제외하고 전부 시계 반대 방향으로 옮기는 것과 같다. 만약 이 전략을 사용한다면, 하나의 칸에 구슬이 차 있다면 그 칸에는 끝까지 구슬이 차 있을 것이다. 그런데 사실 우리가 궁금한 것은

• 마지막에 각 칸에 구슬이 몇 개 있느냐가 궁금한 것이 아니다. 있느냐 없느냐가 궁금한 것이다. (왜냐하면 마지막에 구슬의 수는 항상 1개니까)
• 마지막에 구슬의 절대적 위치가 아니라 상대적 위치만 궁금하다.

 따라서, 원래 구현에서는 모든 칸에 있는 구슬을 동시에 옮겨야 했지만 그 순서를 무시하고 그냥 아무 칸이나 골라서 그 칸의 모든 구슬을 하나 빼고 시계 반대 방향으로 옮긴다고 생각해 보자. 그러면 그래도 된다(...)는 사실을 알 수 있다. 왜냐하면 어차피 채워질 수 없는 칸은 무슨 짓을 하더라도 구슬이 채워지지 않기 때문이다. 따라서 원을 시계 반대 방향으로 2바퀴 돌면서, 걸리는 것마다 모든 구슬을 1개 빼고 시계 반대 방향으로 옮겨준다. (난 그냥 std::reverse 돌린 뒤 시계 방향으로 돌았다.)

 여기까지 했다면 그 다음은 KMP로 대충 해결해주면 된다. 사실 나이브 돌아도 된다는 사실은 잘 알려져 있지 않다. 근데 반응 살펴보면 KMP가 없었어도 최소 P4는 받았을 것 같다.

 

 4. 최적의 프로세스 수행 순서 (예측 P3-P2)

 s = ababaabaabc, pattern = abaabc로 놓고 생각해보면 감이 잘 온다. (아닐 수도 있다. 내가 이 문자열을 썼기 때문에 넣은 것이지...) 이 예제에서 최적은 ab/aba/abaabc인데, 여기서 알 수 있는 사실은

 1. 단순 그리디는 안 먹힌다. (단순 그리디라면 aba 한 다음에 b에서 막히거나, ab/abaab/a/ab 한 다음에 c에서 막히거나 하는 일이 일어났을 것이다)

 2. DP가 있을 수 있다. a에서 끊는 경우/ab에서 끊는 경우/aba에서 끊는 경우로 케이스를 나누면 된다.

 따라서 DP의 전이 그래프를 생각해주자. 각 문자들을 그래프의 노드로 보고 갈 수 있는 곳까지 간선을 이어준다. 문제는 간선의 개수가 O(MN)개까지 있을 수 있다는 것이다. 관찰을 통해 문제를 쉽게 만들어보자. 현재 i번째 문자열까지 보았고 i+1번째 문자열부터 i+k번째 문자열까지 끊을 수 있다면, i+k-1번째 문자열까지 끊는 것도 가능하고, i+k-2번째 문자열까지 끊는 것도 가능하고... 이것이 성립힌다. 따라서 이것들을 하나의 interval로 본다고 생각해보자. 그러면 놀랍게도 문제가 interval graph의 양끝 사이의 최단경로를 찾는 문제로 바뀐다. 이것은 DP가 아닌 스위핑 + 그리디로 처리가 가능하다.

 따라서 이제 interval graph를 구성해주기만 하면 끝난다. 이것도 그다지 쉬운 문제는 아니다. 모든 문자에 대해서 오른쪽으로 어디까지 갈 수 있는지를 계산해주어야 하는데 문자는 N개만큼 있고 interval의 길이는 O(M)일 수도 있다. (s = ababababab, pattern = ababab를 생각해보면...) 이걸 어떻게든지 O(N) 안으로 넣어야 한다. 다시 관찰을 해 보면, 사실 N개의 모든 interval을 구해줄 필요가 없다. 왜냐하면 다른 interval 사이에 완전히 포함되는 interval은 굳이 고려해줄 필요가 없기 때문이다. 따라서, 패턴 문자열의 접두사를 빠르게 찾아줄 수 있는 KMP 알고리즘을 생각하게 된다. 우리의 전략은

• pattern 문자열로 KMP 오토마타를 만들어 그 오토마타로 s를 읽는다.
• 오토마타의 state 번호가 늘어난다면 오토마타가 s를 잘 읽고 있다는 뜻이다. s를 잘 읽고 있다면, 현재 보고 있는 interval의 길이를 1 늘려준다.
• 오토마타의 state 번호가 줄어든다면 실패가 발생했다는 뜻이고, 다시 말해 현재 보고 있는 interval의 오른쪽 끝을 넘어섰다는 뜻이다. 따라서 새로운 interval을 구해줄 필요가 있다. 새로운 interval의 왼쪽 경계는, 오토마타의 state 번호가 t일 때 (idx-t)이다.

이렇게 하면 다른 interval 사이에 포함되는 interval은 무시되고 그렇지 않은 interval은 모두 고려된다. 증명은 그냥 interval graph에서 다른 interval 사이에 포함되는 interval 모두 지우는 알고리즘이랑 저 알고리즘이 똑같다는 걸 쓰면 된다. 저 알고리즘은 단지 KMP를 곁들였을 뿐. 아무튼 시간복잡도는 KMP의 복잡도를 따라간다.

 

 여담으로 이 문제의 난이도가 진짜 P2라면 이 문제는 내가 실전에서 풀이에 성공한 첫 번째 P2 문제다.

 

 5. 타이젠 (예측 D5)

 CHT를 무지성으로 구현하면 되는 문제 같은데 잘 모르겠다. 128비트 정수를 써야 구현이 되거나, 64비트 정수로는 구현이 꽤 까다롭다는 말을 들었다. 난 그 사실을 깨닫지 못해서 틀렸다. CHT 무지성 문제라서 원래 P2가 돼야 하는 게 맞는데, 예측이 D5인 이유는 몬가...몬가 백준에 있는 leftmost segment라는 문제가 실수오차를 곁들인 CHT 문제 같은데(확실히는 모름 안풀어봤음) D5라서 이것도 D5로 예측하기로 했다.