티스토리 뷰
저번주 토요일(15일)에 SCPC 2차 예선이 있었는데 733점으로 본선에 가게 되었다. 개인적으로 2번 문제가 빡셌던 것 같다. 삼성전자 수학 경진대회인줄;;
1. Hanoi
제일 큰 원판부터 올바른 위치에 있는지 판단한다. 탑을 옮기는 시작 위치와 도착 위치에 따라 경우를 나눠서 판단했다. 1->2, 2->3, 3->1처럼 바로 오른쪽으로 옮기는 경우와 1->3, 2->1, 3->2처럼 한 칸 건너뛰는 경우로 나눠서 생각해보면 재귀적으로 해결할 수 있다.
2. 오래달리기
연립 합동식을 푸는 문제로 생각할 수 있다. 바로 중국인의 나머지 정리를 적용하고 싶었지만 mod가 쌍마다 서로소가 아니어서 애를 먹었다. 각각의 mod를 소인수로 분해함으로써 중국인의 나머지 정리를 적용할 수 있었다. 또한 계수의 역원이 존재하지 않는 경우에는 해가 여러 개 나올 수 있어서 백트래킹을 돌렸다. 그냥 돌리면 연산량이 100^5가 되어서 해가 존재하지 않는 경우(모순인 경우)를 가지치기해줬다. 정확한 시간복잡도를 계산하기가 어려워서 부분점수만 받으려고 제출했는데 두 번만에 만점을 받았다.
3. Divisor
사실 풀었다고 하기에도 민망한 문제다;; 1부터 1000000까지 각각 vector 배열을 만들어서 해당 수를 약수로 가지는 인덱스 번호를 오름차순으로 저장했다. 그리고 [l, r] 사이에 인덱스가 하나라도 존재하는지 여부를 lower_bound를 통해 찾는다. 부분점수부터 받을 목적으로 제출했는데 만점을 받았다;; (제한시간이 10초인데 5초 걸렸다.) 테케가 약한건지..? TLE가 떴으면 아마 쿼리 정렬 등의 아이디어를 더 생각해봤을거다.
4. 중심
그리디하게 풀었다. 처음엔 I집합에 모든 n개의 정점을 넣고, 리프들 중 가중치가 작은 것부터 n - q개의 노드를 없앴다. 우선순위 큐를 이용해서 nlogn에 구현할 수 있다. 1번이랑 비슷하게 빨리 풀었다.
5. 자석
DP로 풀어보려고 했는데 생각이 안났다. 일단 너무 피곤해서 집중도 잘 안됬고 그냥 부분점수 받고 포기했다.