[Codeforces] Round #569 Div. 1

https://codeforces.com/contest/1179

 

A - Valeriy and Deque (Code)

일단 가장 큰 원소가 제일 앞으로 오고난 뒤에는 그 원소는 계속 제자리이고 나머지 원소들이 $N-1$을 주기로 돈다는 것을 알 수 있습니다. 그리고 가장 큰 원소는 적어도 $N$번 이내로는 맨 앞으로 올 것입니다. 그러니 $k$번째의 상황을 알고 싶으면 대충 $N+(k$를 $N-1$으로 나눈 나머지$)$ 번째의 모습이 어떠한지를 알면 됩니다.

 

B - Tolik and His Unkle (Code)

 

어떻게든 적절한 움직임을 찾기만 하면 됩니다. 만약 일차원이라고 한다면

 

1 3 5 7 9 8 6 4 2 와 같이 좌우로 와리가리를 치는 방법이 쉽게 떠오를텐데, 이제 이걸 이차원으로 확장하면 아래와 같이 해결이 가능합니다.

 

642

798

135

 

이런식으로 대각선 양쪽 끝에서 가운데로 모여가는 느낌으로 짜면 잘 동작합니다.

 

C - Serge and Dining Room (Code)

 

상황을 잘 생각해보면 1부터 100만까지의 인덱스를 가지는 배열 $x$에서 접시가 있는 곳은 -1, 각 사람이 가진 돈의 액수에 해당하는 곳은 +1을 하면 $x[k]+x[k+1]+ \dots + x[1000000]$이 음수가 되는 가장 큰 $k$가 곧 정답입니다.

 

저는 이를 lazy propagation + 이분탐색으로 $O(NlgNlg(1000000))$으로 해결했는데 정해는 $O(NlgN)$이고, 지금 생각해보니 구간의 min을 들고있으면서 어찌저찌 했으면 $O(NlgN)$에 가능했을 것 같습니다.