오늘의 PS (11) - 220616~17

화~수는 조별 과제 + 귀가 때문에 랜덤 디펜스를 하지 못했고, 어제는 문제를 뽑았더니 코포가 얼마 남지 않았길래 하나만 풀고 코포하러 갔다. 코포는 대차게 망했다. 전혀 틀린 점이 없는 코드들이 틀리길래 억울해 하던 중, 대회 시작 1시간 후 이런 걸 발견했다.

 

원래 long long으로 고정해 두는데, 백준 풀면서 바꾼걸 까먹었던 것이다. 이후 1시간동안 C를 푸려고 노력해보았으나 잘 되지 않았고, 그대로 퍼플로 향했다.

 

16~17일에 랜플디로 고른 문제들은 아래와 같다.

 

5480 - 전함

 

온라인으로 해결하는 것은 어려워 보이니, 오프라인으로 해결하는 방법을 떠올려보자. 2차원일 때와 1차원일 때의 풀이 방법이 크게 다르지 않으므로 1차원이라고 가정하자. 이 때, 한 가지 관찰이 필요하다.

: 나를 지우는 레이저는 내 구간에 포함된 레이저 중 가장 빨리 입력된 레이저이다.

이는 RMQ와 동일하고, 따라서 각 전함에 대해 나를 지우는 레이저의 번호를 \(O(logN)\)에 구할 수 있다.

이를 구했다면 각 레이저에 대해 가장 무거운 전함의 무게도 쉽게 구할 수 있을 것이다. 좌표 범위가 크기 때문에 좌표 압축을 해 주어야 한다.

 

12963 - 달리기

 

멋진 문제. 문제 자체는 최대 유량을 구하라는 것인데, 간선 용량의 제한이 모두 커 평범한 방법으로는 해결할 수 없다. 용량의 특징을 잘 관찰하면, 나보다 번호가 더 작은 간선들의 용량을 모두 합쳐도 내 용량보다 항상 작다. 이는, 플로우 그래프에서 차단 용량을 구할 때 최대 한 개의 간선만 차단 간선이 된다는 것을 의미한다. 따라서, 큰 번호의 간선부터 보며 이를 온전히 포함하는 경로가 있으면 이를 선택해주고 간선을 지우는 전략이 항상 최적이다. 시간 복잡도는 \(O(NM)\)에도 가능하고, Union-Find를 잘 구현하면 \(O(MlogN)\)에도 가능하다고 한다.

 

7424 - 숫자 쌍

 

백트래킹이나 완전탐색을 잘 돌리면 될 것 같은데, 이런 문제에 약해서 포기했다.

 

5670 - 휴대폰 자판

 

솔브 수가 많길래 보았더니 단계별로 풀어보기 트라이 단원에 있는 문제였다. 문제 자체는 트라이에 대한 이해가 있다면 쉽게 해결할 수 있을 것이다.

 

1093 - 스티커 수집

 

지문이 좀 이상하긴 한데, 다 이해하고 나면 그냥 전형적인 MITM 냅색 문제로 바뀐다. 

 

내일부터는 랜플디도 랜플디인데, 다이아 구간의 Hard 알고리즘 공부도 좀 해 보려고 한다. (Splay Tree, Offline Dynamic Connectivity, 선인장, 커넥션 프로파일 DP, General Matching, 세그 비츠.. 등등, 추천도 받아요) 이유는 여러 가지인데, 시간도 많고, 1솔 1솔이 중요한 대회에서는 많이 아는게 무조건 유리한 것 같기도 하고, 짬에 비해 너무 아는게 없기도 하고.. 내일은 코포랑 앳코더가 있다. 앳코더는 잘 치다 최근 라운드를 좀 망쳤고, 코포는 지금까지 친 모든 Div. 1에서 음수 레이팅을 받아서 침체기 상태이다. 우선 내일 오렌지부터 다시 가고 생각해야지..