티스토리 뷰
대학생이 된 올해 SCPC에 처음으로 참가하게 되었다. 후기를 좀 늦게나마 써본다,, (내일이 2차 예선..)
작년에 비해 난이도가 상승한 것 같다. 만점자가 <= 6명...
1. 괄호
스택을 이용해 괄호를 매칭시키면서 답을 갱신한다. 닫는 괄호가 매칭이 안되면 스택을 초기화하고 다시 매칭을 시작한다.
()()()처럼 올바른 괄호가 여러 개 이어져 있는 경우를 체크하지 못해 한 번 실수했던 문제다.
2. 주식거래
값이 증가하는 구간의 개수를 세면 된다. 여기서 증가하는 구간 [l, r]은 a[l - 1] > a[l], a[r] > a[r + 1], a[l] < a[r], a[i] <= a[i + 1] ( l <= i < r ) 을 만족함을 의미한다. (편의상 a[0] = INF, a[n + 1] = -INF 라고 하자.)
각 구간에서 제일 쌀 때 사고 제일 비쌀 때 판다고 생각하면 된다.
3. 전광판
처음에 문제를 이해하는데 시간이 좀 걸렸다. 우선 각 전구가 2개의 스위치와 연결된다는 점에서 2-SAT으로 풀릴 것 같았다.
그러나 도무지 2-CNF 식이 생각나지 않았다. 고작 1차 예선 3번 문제가 2-SAT일까 싶어 다른 풀이를 생각해봤다.
결론적으로 DFS / BFS로 풀린다는 걸 깨달았다. 스위치 하나의 상태를 고정하면 그와 연결된 전구의 다른 스위치들의 모든 상태가 결정되기 때문에 스위치들을 독립된 그룹으로 묶을 수 있다. (Disjoint Set을 구현해도 된다.)
제출했더니 시간초과가 났다. 어이없게도 setbuf(NULL); 때문이었다. 부분점수를 받으려면 setbuf를 써야한다는데 일단 출력 속도가 매우 느려진다. 없애니까 만점을 받을 수 있었다.
4. Monotone
오목한 지점의 각도 범위를 따져서 [0, pi) 범위를 모두 덮으면 NO, 아니면 YES를 출력한다.
5. Covernent
나만 못 푸는 것 같아 자괴감이 들었던 문제.. ㅠ
우선 O(2^N logN) 풀이를 생각할 수 있었다. 몇 시간 동안 계속 고민해봤지만 그 이상의 진전은 없었다.
너무 졸린 탓에 그냥 O(2^N logN) 풀이로 부분 점수를 받고 잤다. MCMF로 풀린다는 후문이 있다.