Codeforces Round #796 (Div. 1)

https://codeforces.com/contest/1687

 

A에서 시간을 상당히 많이 버렸다. (25분)

 

A. The Enchanted Forest

 

최선의 방법은 연속으로 먹을  min(n, k)개를 고른 다음에 맨 첫 부분에서 맴돌다가 출발하는 것이다.

 

B. Railway System

 

우선 1000000, 0100000, 00100000 ... 으로 모든 간선의 가중치를 미리 구해둔다.

이후 11111111에서 제일 가중치가 큰 간선들부터 제거해 나간다.

-> 제거하였을 때, 간선의 가중치만큼 정확히 준다면 더 이상 연결이 되지 않는다는 의미이다.

-> 따라서 정확히 줄 경우에는 제거하지 않고, 그렇지 않을 경우에는 제거하면 된다.

 

이 과정의 역과정을 생각하면 크루스칼과 같기 유사하기 때문에 타당한 방법임을 알 수 있다.

 

C. Sanae and Giant Robot

 

제일 중요한 관찰은 paste하는 작업이 손해가 되지 않는다는 것이다.

-> 쉽고 단순한 관찰이 받아들이기 어려운 것은 구간 1을 paste하며 구간 2가 paste 불가가 될 수 있기 때문.

-> 만일 이렇게 구간1과 구간2가 충돌한다면 무엇을 먼저 쓰든 상관이 없다.

-> 구간 1을 paste할 때 구간 2가 불가하게 되면 구간 2를 paste해도 구간 1이 불가하게 된다.

-> 어차피 이 둘은 이미 충돌하기에 외부의 다른 구간 3로 정리해주어야 하기 때문에 이것은 크게 중요하지 않다.

이제 되는대로 paste를 하는 것을 구현해주면 된다.

 

sol1) 큐에 차례대로 넣고 전부 해버리기

https://codeforces.com/contest/1687/submission/159367127

https://codeforces.com/contest/1687/submission/159364840

sol2) DSU

https://codeforces.com/contest/1687/submission/159366644

 

D. Cute Number

 

해답을 보고 나면 왜 못풀었지 싶어지는 문제

결국 모든 수를 t * t <= a[i] + k < = t * t + t인 t가 존재하도록 하는 k의 최소를 구해주면 된다.

t0 * t0 <= a[0] + k <= t0 * t0 + t0라고 가정하자.

-> 그렇다면 나머지 a들에 대한 t값은 t0보다 무조건 커야 하며, t * t의 값은 2 * t0보다 빠른 속도로 커진다.

-> 나머지 a들에 대해서 t * t - k <= a[i] <= t * t + t - k가 되야 하므로 iterate하는 t의 개수는 a[n - 1] / (t0 * 2)개 정도이다.

-> 따라서 복잡도는 maxa * lg(maxa)  (maxa == a[n - 1])  

https://codeforces.com/contest/1687/submission/159605629