Educational Codeforces Round 125 (Rated for Div. 2)

대회중 과정과는 상관 없이, 에듀만 치면 결과가 귀신같이 좋다.

 

A. Integer Moves (00:01, +)

주어진 점이 원점이면 0, 원점과의 거리가 정수면 1, 아니면 2이다.

 

B. XY Sequence (00:03, +)

그리디하게 해주면 된다.

 

C. Bracket Sequence Deletion (00:18, +)

괄호 문자열에서 팰린드롬을 생각해본건 처음이라 뇌절이 와 지문을 좀 느리게 읽었다.

만약 앞 두 글자가 ((이나 ))인 경우 팰린드롬이라 지울 수 있고, ()인 경우 올바른 괄호 문자열이라 지울 수 있다.

남은 경우는 )(인데, 이 경우 )(((..(()가 팰린드롬이므로 )가 다시 나올때까지 확인해주면 된다.

 

D. For Gamers. By Gamers. (01:11, +7)

핵심 아이디어는, 같은 cost를 가진 유닛 중에서 가장 좋은 유닛만 보아도 된다는 점이다. 이를 상당히 빨리 캐치했고 \(O(ClogC)\)에 돌아간다고 생각한 풀이를 냈으나, Test 33에서 TLE가 나길래 상수차이인줄 알고 별 짓을 다했다. 내 풀이가 알고보니 \(O(CM)\)이라는 점을 깨닫는 데에 40분이 걸렸고, 깨달은 후에는 약간의 최적화를 통해 시간 복잡도를 \(O(ClogClogM)\)으로 줄여 맞을 수 있었다.

 

E. Star MST (01:39, +)

주어진 조건을 다시 해석하면, 1이 아닌 두 정점 \(u, v\)를 잇는 간선의 가중치는 \(1, u\) 간선의 가중치와 \(1, v\) 간선의 가중치보다 커야 한다. 따라서, 1과 이어진 간선의 가중치를 오름차순으로 \(a_2, ... a_n\)이라 했을 때 경우의 수는 \((n-a_k+1)^{k-2}\)를 모두 곱한 꼴이다. \(DP[n][k]\)를 \(n\)개의 가중치를 배정해야 하고, \(k\) 보다 큰 가중치만 배정하는 경우의 수로 정의하면 점화식이 나오며 문제를 \(O(N^3)\) 정도에 해결할 수 있다.