8월 6일에 진행된 SCPC 2차 예선후기입니다.
총 5개의 문제 중 1번을 제외한 나머지 전부 틀렸습니다.
공부하면서도 어려움을 많이 겪어서 본선가기는 어렵겠다 생각은 했지만, 아쉽기는 합니다.
1번 [수열연산] 100/100
투포인터로 돌렸습니다.
2번 [반 협동게임] 67/150
같은 반에서 서로 먼 순서로 pair 로 묶고, 너비를 미리 합쳐 계산해두었습니다.
이제 순서에 따라 중간에 비는 자리가 생길 것이고 그 부분의 값을 감소시키면 됩니다.
처음에는 너비 순서로 정렬 해보았으나, 그냥 오름차순으로 하더라도 같은 결과라는 사실을 뒤늦게 깨달았습니다.
매 순간 pair.second 만을 새로운 배열에 포함시키고, 그 배열에서 pair.first 와 pair.second 사이에 위치한 점의 갯수를 세주었습니다.
그 과정에서 나름 최적화라고 upper_bound 로 이진탐색을 시도했으나 시간초과가 나왔습니다.
pair.second 를 새로운 배열에 정렬된 상태로 추가해 나가는 과정 때문에 시간 초과가 나왔다고 생각합니다.
내부의 점의 갯수를 세는 DP 적인 해결방법이 있을 것 같은데 생각이 나진 않았습니다.
(2023-01-08 수정)
세그먼트 트리를 응용하여 교차점을 확인하는 방법을 이용해야했습니다.
3번 [ABC] 34/200
DFS로 K=0 부분점수만 받고 그 이상 해결하지 못했습니다.
4번 [직사각형] 62/250
정해는 어려울것 같아서 처음부터 부분점수만 받을 생각으로 접근했습니다.
접근방식은 부분의 합을 갯수로 나누어 나머지를 살펴보면 1/n 수준으로 걸러낼 수 있지 않을까였습니다.
(0,0) 에서부터 (x,y) 까지의 사각형의 합을 미리 테이블에 저장해두었고,
sum(r2, c2) - sum(r1, c2) - sum(r2, c1) + sum(r1, c1)
이런 식으로 부분의 합을 계산했습니다.
개수가 홀수일 때 합의 나머지는 0, 짝수일 때는 나머지가 sum/n 이면 됩니다.
그렇게 부분점수를 받는 목적은 달성했습니다.
그 외에도 홀수 짝수의 갯수를 비교하여 경우의 수를 줄여보려는 시도를 했지만, 의미는 없었습니다.
5번 [황금카드] 0/300
끝나기 30분전에 문제를 처음 읽기 시작했는데, 생각만하다가 대회가 종료되었습니다.
시간이 더 있어도 풀지는 못했을 것 같습니다.
대충 400점은 되어야 본선 가능성이 있어보이는데 점수가 많이 낮아 기대하기는 어렵겠습니다.
