AtCoder Beginner Contest 212

A, B는 복기하지 않겠다.

 

C. Min Difference (00:05, +) *246

\( min \left| a_i-b_j \right| \) 를 구하는 문제이다. a의 모든 원소를 b에 대해 이진탐색 해주면 가장 가까운 원소 후보 2개를 \(O(logN)\)에 구할 수 있다.

 

D. Querying Multiset (00:16, +) *775

지금까지 더한 가중치를 저장한 후, 새로 들어오는 원소는 그 만큼을 빼준 후 pq, set 등의 자료구조에 넣는 것으로 해결할 수 있다.

 

E. Safety Journey (01:05, +4) *1410

\(DP[i][j]\)를 \(i\)로 끝나는 길이 \(j\)의 여행으로 정의하자. 이렇게 정의하면 점화식을 다음과 같이 세울 수 있다.

\(i\)와 연결된 노드 \(k\) 에 대해 \(DP[i][j]= \sum_{k} DP[k][j-1] \)

이를 그대로 구현하면 \(O(KN^2)\)의 시간복잡도가 걸린다. 하지만 본 문제의 제한 중에는 \(M<=5000\)이 존재하고,

이를 이용해 DP를 연결된 노드가 아닌 연결되지 않은 노드에 대해 빼주는 식으로 갱신한다면 \(O((N+M)K)\) 에 문제를 해결할 수 있다.