[210717] SCPC 2021 1차 예선 후기

PS를 좋아하는 사람이라면 누구나 알고 있을 듯한 대회,

삼성 대학생 프로그래밍 경진대회(SCPC) 2021에 참여하였다.

첫 응시인 만큼 본선 진출을 노린다기보단, 경험 및 실력증진을 위해 참가하였고, 목표는 1차 예선 통과이다.

369점으로 1차 예선을 마무리하였다.

2차 예선에 진출할 수 있을지는 미지수...

 

간단하게 아래에 문제를 풀면서 들었던 생각을 써보겠다.

---

1. 친구들 [80점 / 80점]

첫 번째 문제조차 풀지 못할까봐 긴장 반 설렘 반으로 문제를 살펴보았는데, 생각보다 할만했다.

나는 유니온파인드로 over kill 한 느낌이 있는데, 간단한 구현만으로 처리가 가능할 듯하다.

만점자 수가 굉장히 많은만큼 배점도 상당히 낮다. 1번 문제의 배점이 100점이 아닌 80점인 경우는 처음 보는 듯.

 

2. 이친수 [150점 / 150점]

A로 가능한 수를 찾는 문제. 조금 어려워지기 시작하는 부분이다.

A의 앞 t자리와 뒤 t자리는 B로부터 이미 결정돼버리기 때문에 고정이다.

그리고 나머지 자릿수는 B[i]=0인 경우는 A[i-t]=A[i+t]가 반드시 0이기 때문에 B[i]=0인 경우를 먼저 파악하고,

이제 나머지 B[i]=1인 경우에 따라 A[i+t]가 1이 가능하면 1이 되도록, 불가능하면 A[i-t]가 1이 되도록 해준다.

이 때, A[i-t], A[i+t]가 변경 가능한 숫자인지 파악해주는 것 또한 중요하다.

이렇게 해주면 O(N) 풀이로 150점을 받는다.

 

3. No Cycle [0점 / 180점]

K개의 간선의 방향성에 따라 사이클이 생기는지 판단하는 문제.

사이클 판별 여부는 dfs, bfs 또는 유니온파인드로 O(N+E)에 파악할 수 있기 때문에 크게 개의치 않았는데,

문제는 간선의 개수 K였다. K<=2,000 이었는데, 간선의 방향을 모두 따져서 사이클을 판단하려면 K에 따른 백트래킹을 해야 되겠단 생각을 갖고 있었다가 K 범위를 보고 놀랐다. 풀이가 정말 궁금한 문제...

처음 봤을 땐, SCC를 떠올렸는데 내가 SCC에 약한건지, 아니면 올바른 알고리즘이 아닌건지 제대로 풀리지 않았다.

따라서 백트래킹을 시도해봤는데, 웬만한 테케는 맞는 듯한데 왜 41점을 못 얻었는지 아직도 의문. 정말 슬프다.

 

4. 예약 시스템 [88점 / 190점]

4번부터는 문제가 정말 읽기 싫게 생겼다. 문제를 이해하는 데에만 10분은 걸린 듯하다.

37점 풀이와 51점 풀이는 생각보다 쉽다. 모든 L이 짝수 / 모든 L이 홀수인 경우는 간단한 그리디적 사고로 쉽게 해결할 수 있다. 정렬해서 가장 작은 원소 4개 / 5개를 답에 더한 후, 마지막 순간에 겹치지 않는 순간을 빼줘야 하므로 가장 큰 값들 일부를 빼주면 된다.

근데 만점짜리 풀이를 도저히 모르겠다. 만점짜리 풀이는 L이 짝수, 홀수 모두 나올 수 있는 경우인데, 이것 또한 그리디적으로 사고해서 제출하였으나, 계속 88점이 뜨는 현상 발생... 그래도 1번보다 배점을 크게 주는 혜자스러운 문제이다.

 

5. 차이 [51점 / 200점]

이 문제 또한 정말 읽기 싫게 생겼다. 대략 읽고 생각난 것은 쿼리에 따라 처리하는 것이기 때문에 세그먼트 트리.

그러나 31점 그룹, 20점 그룹이 간단한 유니온 파인드로 처리가 가능해서 일단 51점을 빠르게 긁을 수 있었다.

만점짜리 풀이는 이 문제의 응용 버전이 아닐까? 하고 코드를 열심히 짜보고 추가하였는데, 

https://www.acmicpc.net/problem/3830

3830번: 교수님은 기다리지 않는다

글쎄... 아무리 제출해도 나오는 결과는 51점 뿐. 생각보다 쉬운 문제인데 내가 실수를 한건지, 아니면 진짜 어려운 문제인데 내가 넘 쉽게 해결하려 한건지 잘 모르겠다.

---

총합: 369점 / 800점

일단 만점자 수를 보아하니 2차 예선 커트라인이 210점은 넘기지 않을까 싶다.

410점 이상일 수도 있겠다는 생각도 든다.

난 2차 예선을 갈 수 있을까? 갈 수 있을 것 같기도 한데, 다른 문제들 만점자수가 꽤 많은 편이라 감이 잘 안온다.

 

그리고 SCC, segment tree, Graph 쪽 공부를 열심히 해야겠다는 생각이 든다.

또한, 어려운 문제와 알고리즘에도 도전해보고 공부해보는 습관을 길러봐야겠다.

 

+) SCPC 접수 선착순 700명 안에 들어 스타벅스 아이스 아메리카노 기프티콘을 받았다~

얻은 게 생각보다 많다ㅎㅎ

내년 SCPC 2022에는 보다 더 나은 성적을 거둘 수 있길

---

(21.07.23 추가)

SCPC 1차를 통과하였다.

2차 경험도 해볼 수 있을 듯하다~