[Codeforces] Manthan, Codefest 19

https://codeforces.com/contest/1208

 

A - XORinacci (Code)

 

주기가 3인게 자명합니다.

 

B - Uniqueness (Code)

 

모든 l, r에 대해 다 해보면 되는데 l을 고정하고 r을 오른쪽으로 늘려가면서 누적시키는 방법으로 해야 $O(N^2)$에 해결할 수 있습니다.

 

C - Magic Grid (Code)

 

그다지 엄밀한 증명 없이 그냥 4*4 단위 칸을 쓰면 되겠다고 생각헀고 실제로 맞았습니다. 왜 맞는지는 아직도 잘 모르겠네요ㅎㅎ..

 

D - Restore Permutation (Code)

 

Segment Tree를 이용해 뒤에서부터 현재 x라는 수가 왔을 때 $s_i$가 일치하는 x를 이진탐색으로 찾으면 됩니다.

 

E - Let Them Slide (Code)

 

segment tree를 하나 들고다니면서 각 가로에 대해 최댓값이 움직일 수 있는 부분은 그냥 업데이트 시키고, 나머지 부분은 따로 처리를 해주고 뭐 그런식으로 경우를 잘 나눠서 해결하면 됩니다. 구현에서 실수를 하기 쉬웠습니다.