2024 01 12 ps 노트

몇일동안 푼 문제들 풀이 메모용으로 작성한다. 

 

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

18508번: Delete the Points

개인적으로 굉장히 어렵다고 생각하는 문제다. 처음 봤을 때는 골드2 였지만, 현재는 플레5가 되었다. 아는 분의 도움을 받아 풀이를 알게 된 문제다. 

문제는 간단하다. 이차원 평면에 $N \leq2000$개의 점들이 있다. 이때 임의의 정사각형 하나를 잡아서 포함되는 점의 개수가 정확히 두개라면 포함되는 두 점을 지울 수 있다. 모든 점을 지우는 방법을 아무거나 하나 출력하는 문제다.

 

어차피 2개의 점들만 지워지기에, $\binom{N}{2}$개의 모든 쌍들을 생각해보자. 적당한 거리 함수 하나를 잡아서, 거리를 기준으로 오름차순 정렬 후 두 점의 중점을 중심으로 하는 정사각형을 만들어주면 된다. 이때 유클리드 거리를 사용하면, 작은 거리부터 봤을 때 두 점으로 이루어지는 정사각형 내부에 다른 점이 존재할 수 없음을 증명할 수 있다고 한다.

 

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

1700번: 멀티탭 스케줄링

대충 될 것 같은 그리디를 짜면 맞는 유형의 문제이다. 엄밀한 증명은 잘 모르겠으나 직관적으로 생각해보면 다시 사용되기까지의 시간이 가장 긴 플러그를 빼는 것이 이득일 것 같았다. 만약 더 짧은 플러그를 빼는 것이 이득이라면, 뽑고 꼽고 또 뽑거나 다른걸 뽑거나 해야하니..? 

 

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

11046번: 팰린드롬??

최근에 동아리 수업에서 해싱을 배워서 해싱으로 풀었다. M어쩌구를 짜도 풀 수 있지만 해싱으로는 무려 업데이트가 있어도 풀 수 있다? 업데이트가 없기에 구간합으로 $O(N + Q)$에 풀 수 있다.

 

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

18318번: Springboards

전형적인? dp 전이를 세그트리로 최적화하는 유형 같다. 유요한 점들은 $2N$개들의 보드들만 있으니, 이러한 점들에 대해서 dp를 하면 된다. 점화식은 $dp(i) = \max_{x_j < x_i, \, y_j < y_i} dp(j) + |x_i - x_j| + |y_i - y_j|$ 가 되고, $x$를 기준으로 정렬 시켜 스위핑을 하고 세그먼트 트리의 $y_i$번째 노드에 $dp(i) - x_i - y_j$를 저장해준다면, $dp(i) = x_i + y_i + \max_{j < i, \, y_j < y_i} dp(j)$ 가 된다. $O(P \log P)$에 풀 수 있다.

 

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

18785번: Clock Tree

풀 때는 $O(N^2)$에 풀었지만, $O(N)$풀이가 존재하는 문제였다. 전형적인 맞추기는 쉽지만 증명은 어려운 문제라고 생각한다. 

공식 해설 : http://usaco.org/current/data/sol_clocktree_silver_feb20.html 을 참고하였다.

 

$O(N^2)$풀이는 다음과 같다. 어떤 정점을 루트(시작점)으로 잡자. 이제 이 트리에서의 임의의 서브트리는 그 서브트리의 루트를 제외한 모든 정점들을 12로 맞추어 줄 수 있다. dfs를 할건데, 자신의 자식이 12가 아니라면 왔다 갔다 하면서 12로 맞추어주고 다시 현재 정점으로 올라오는 것을 반복해주면 된다. 그럼 최종적으로는 전체 트리의 루트를 제외하고 12로 맞추어진 상태이고 bessie는 현재 루트에 텐데, 이때 루트가 12 또는 1인 것이 필요충분조건이다. 1인 경우에는 자식에서 올라오는 것을 멈추면 되기 때문이다. 이가 필요충분조건인 이유는 일단 원본 트리에서 정답이 존재하였으면 현재 트리에서도 답이 존재할 것이고, 루트를 12로 맞추어 주려면 다른 정점과 왔다 갔다 해야하는데 이를 반복하면 12가 아닌 정점이 존재할 수 밖에 없다.

 

위의 증명을 조금 보완해서 선형인 경우를 생각해보자.

우선 $N = 2$인 경우를 생각해보자. 두 정점을 방문한 횟수는 최대 1만큼 차이가 날 수 있다. 트리는 이분그래프임을 생각해보며 이를 일반화해보자. 이분그래프로 색칠한 정점 그룹을 그룹1, 그룹2라 하자. 그룹1을 방문한 횟수와 그룹2를 방문한 횟수의 차이는 1 초과로 날 수 없을 것이다. 

 

임의의 시작 위치를 하나 잡고, 그 위치와 같은 그룹에 있는 정점들을 그룹1, 나머지를 그룹2라 하자. 만약 각 그룹의 초깃값들을 다 더한 값 $S_1, S_2$ 의 차이가 1 초과라면, 답은 존재할 수 없을 것이다. 만약 1 이하라면 답은 항상 존재하는데, 귀납법으로 보일 수 있다. $N = 2$인 경우에는 자명하게 참이다. $N$이 2가 아니라면, 임의의 리프를 하나 잡고 부모 정점과 왔다 갔다 하며 리프를 12로 맞춰주고, 그 리프를 지워주면 된다. 이때 차이가 0이라면 최종적으로 루트로 올라오면 되고, 1이라면 자식에서 끝내면 된다.

 

이제 그룹을 나눠주고, 각 그룹에서의 합을 구해준다. 한 그룹에서 어떠한 정점으로 시작하는 답이 존재한다면, 그 그룹에서 아무 정점이나 뽑아도 답은 존재한다.

 

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

15825번: System Call

$\sum_i (T+K) \left \lceil \dfrac{F_i}{K} \right \rceil$ 를 최소화하는 문제이다. 이떄 $(T + K)$는 시그마 밖으로 빼줄 수 있고, $ \left \lceil \dfrac{F_i}{K} \right \rceil $의 유니크한 값은 $O(\sqrt F_i)$ 개 밖에 없음이 알려져 있다. $K$가 $\sqrt F$ 이하라면 가능한 값은 최대 $\sqrt F$개 있을 것이고 (전부 다르다 해도 $K$가 $\sqrt F$ 이하이니), $K$가 $\sqrt F$ 이상이라면 가능한 값은 $\frac{F}{K}$이 $\sqrt F$ 이하일 것이니 또 $\sqrt F$개 이하이다. 이때 모든 $F_i$에 대해 값이 바뀌는 최소의 $K$를 다 구해준다 (https://ahgus89.github.io/algorithm/Harmonic-Lemma/ 참고). 스위핑을 해주면서 값이 바뀌는 $F_i$에 대해 갱신해주면 된다. $O(N \sqrt F)$ 에 풀리고, 시간 제한 내에는 아슬아슬하게 돈다.