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

어제 scpc 2차 예선을 봤다.

1번 문제 읽고 이건 나중에 풀어야겠다 싶어서 2번을 읽었다.

열심히 오래 달리는 문제였는데 마침 이번 주에 확장된 유클리드 호제법 문제를 풀면서 디오판토스 방정식을 푸는 걸 정리해둬서 그걸 이용해서 풀었다.

그리고 3번을 읽고 흐음 서브테케는 할 수 있을 듯 해서 다시 1번을 돌아가 1번을 제대로 읽고 점화식을 조금 적어보니까 6가지 상태에서 (A->B, A->C, B->C, B->A, C->B, C->A) 마지막 단어에 대한 정의가 내려지기에 그걸 이용해 풀었다.

다시 3번을 대충 O(240(n+m)logn) 복잡도에 풀어서 냈는데 아무래도 해쉬맵을 이용하고 복잡도 자체가 너무 크기에 불가능한 방법이었던 것 같다. 47점을 긁고 10번 제출이 끝날 때까지 이런저런 최적화를 해서 내보았는데 통과하지 못했다.

3번을 10번내고 현타가 잠깐 와서 멍때리다가 4,5번을 읽고 4번은 섭테는 트리디피 5번은 섭테 완탐, dp로 보였고 다른사람들 점수 현황을 보니 1,2번 만점에 부분 몇개만 긁으면 본선에 갈수 있을것 같았다. 5번 그냥 완탐으로 섭테1번을 긁고 4번 정해를 생각해 보다가 트리의 중심에서 가장 가중치가 높은쪽의 서브트리의 정점을 뽑는 방식으로 하면 가능할 것 같아서 코드를 짜다가 대회가 끝났당

결과는 위와 같고 아쉬움이 조금 남는 대회였다.

3번을 애매한 복잡도로 오래 붙잡고 있던 게 아쉬웠고 4번을 먼저 봤다면 오히려 좋은 결과가 있지 않았을까 싶다.

끝나고 다른 해법들을 들어봤는데 3번 같은 경우에는 쿼리의 right를 기준으로 정렬하고 해당 right당 약수가 존재하는 가장 오른쪽 인덱스를 관리하는 방식으로 풀 수 있다고 한다.

4번은 위 해법이 맞고 오히려 서브테케를 푸는 방식이 더 어렵지 않나싶다.

5번은 섭테1은 완전탐색으로 쉽게 풀리고

섭테2는 커버되는 영역을 잘 상태로 표현하면 dp로 할 수 있다고 하는데 잘 모르겠다.

정해는 위상태를 세그먼트트리로 해결가능하다고 한다.

scpc 2017 본선 갈수 있었으면 좋겠다.

남은 한 달도 열공!