Codeforces Global Round 15

A. Subsequence Permutation (00:03, +)

문자열을 sort한 문자열과 기존 문자열이 얼마나 일치하는지 세주면 된다.

 

C. Maximize the Intersections (01:19, +)

연결되지 않은 정점을 \( 2a \)개라 할 때, 1번째와 \(1+a\)번째를 잇는 식으로 진행해주면 된다. B로 인해 멘탈이 나가있었던 상태기 때문에, 정당성은 증명하지 않았다.

 

D. Array Differentiation (01:01, +)

주어지는 \(n\) 개의 값중 \(n-1\) 개는 \(B_1-B_k\) 꼴로 만들 수 있다. 이후에는 남은 하나의 값을 \(n-1\)개로 만들 수 있는지 판별하면 된다. 남을 하나의 값을 정하는 데에 \(O(N)\), 완전탐색에 \(3^N\)이 소요되므로 \( O(N3^N) \)에 문제를 해결할 수 있다.