[Codeforces] Educational Codeforces Round 45

http://codeforces.com/contest/990

A,B,C,D,E를 1번만에 맞추고 또 전반적으로 빠르게 풀어서 시간 페널티에서 많은 이득을 봤습니다. F는 풀이를 알았는데 시간이 부족해 코드를 완성하지 못했습니다. 

A - Commentary Boxes

생소한 단어가 많아 조금 고생했습니다. n개의 box를 m의 배수가 되게끔 하고 싶은데, 1개를 없앨 때 드는 비용은 b이고 만드는데 드는 비용이 a일 때 최소 비용이 얼마인가 하는 문제입니다. n과 가까운 두 m의 배수를 생각하면 간단하게 해결했습니다.

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2045/A.cpp

B - Micro-World

일단 박테리아를 내림차순으로 정렬한 뒤, 각 i=1~N-1에 대해 a_j != a_i를 만족하는 가장 큰 j가 a_j <= a_i+K를 만족하는지 확인하면 됩니다. j는 i가 증가함에 따라 같이 증가함이 보장되므로 O(NlgN)에 해결할 수 있습니다.

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2045/B.cpp

C - Bracket Sequences Concatenation Problem

각 bracket string에서 value를 ( = +1, ) = -1으로 두었을 때의 값이라고 합시다. 일단 두 string S1, S2를 붙일 수 있는 필요조건은 S1의 value와 S2의 value의 합이 0이어야 합니다. 추가적으로, S1 >= 0, S2 <= 0을 만족하여야 하고, S1에서 중간에 value가 음수로 떨어지는 일이 없어야하고 S2 또한 중간에 value가 S2 전체의 value보다 작아지는 일이 없어야합니다. 예를 들어 S1 = (( 이고 S2 = )))( 일 경우 각각의 value는 2, -2이지만 S2에서 중간에 value가 -3이 되는 순간이 있으므로 불가능합니다.

이제 D[i].X에 value가 i이고 위의 조건을 만족하는 string의 갯수, D[i].Y에 value가 -i이고 위의 조건을 만족하는 string의 갯수를 저장한 뒤 D[i].X * D[i].Y의 합을 계산하면 됩니다.

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2045/C.cpp

D - Graph And Its Complement

잘 생각해보면 만약 Component가 2개 이상 있는 그래프였다면 Complement는 반드시 Component가 1개입니다. 그렇기 때문에 a, b 둘 다 2 이상이면 불가능합니다. 그리고 어느 하나만 1일 경우에는 trivial한 graph를 만들어냄으로서 쉽게 해결 가능합니다. 이제 a, b = 1인 경우를 생각해봐야하는데, N = 1이거나 N >= 4이면 가능합니다. 그냥 (1,2),(2,3),..,(N-1,N)을 연결하면 됩니다. 그리고 N=2, N=3일 때에는 불가능합니다.

Test data에 (2,1,1),(3,1,1)이 있어서 다행히 많은 사람들이 시스텟에서 나가지 않고 구제받았다고 합니다.

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2045/D.cpp

E - Post Lamps

만약 lamp를 설치할 수 없는 연속된 구간의 최대 길이가 L이라면,  power l 이하의 전등은 쓸 수가 없습니다. 또한 power i의 전등이 몇 개 필요한지는 적절한 전처리를 통해 O(N/i)에 구할 수 있습니다. 그러면 시간복잡도는 O(N*(1/1+1/2+1/3+...+1/N)) = O(NlgN)이 됩니다. 맨 처음에 이게 O(N^2)인줄 알고 딴 아이디어를 생각하느라 시간을 많이 날렸습니다.

https://github.com/blisstoner/Codeforces/blob/master/Educational%20Round%2045/E.cpp

F번은 짜지는 않았지만, 우선 각 component에서 s의 합이 0이 아니면 Impossible이고, 0이라면 그냥 임의의 spanning tree를 만들어서 DFS로 각 edge에서 보내야하는 수량을 정할 수 있습니다. 그닥 어렵지 않은데 E를 풀고 F의 풀이를 생각하고 나니 20분밖에 안남아서 짜지 못했네요. E번이 조금 아쉽긴 했지만, 그것 빼고는 정말 잘 치뤘던 대회였습니다. 이 정도 실력을 계속 유지할 수 있으면 좋겠습니다.