Codeforces Round #803 (Div. 2)

자다 깨서 비몽사몽했다..

 

 

A (00:02)

무지성 O(N^2)

 

B (00:21)

k > 1일때는, 어떻게 연산을 하더라도 too tall한 element의 개수가 변하지 않는다.

k = 1일때는, \(\lfloor{\frac{(N-1)}{2}}\rfloor\)이 답이다. 원하는대로 추가가 가능하기 때문

 

C (01:12)

인성 개터진 case work.

 

D (00:46)

A의 길이가 홀수인 구간 \([l, r]\)에서, \(l\leq x \leq r\)인 수가 홀수 개 존재한다면, 이 구간 안에 우리가 원하는 답이 존재한다.

위는 [3,4,5]의 3개, 아래는 [3]의 1개의 수가 존재한다.

이분 탐색을 통해 15(\(<lg10000\))번 이내의 쿼리로 답을 찾을 수 있다. 구간 [mid, hi]에서 하면 된다.

 

E (02:12)

작은 수(1)부터 진행하기 때문에, 이 수의 위치가 정해지면 이후에 위치가 바뀌지 않는다. 그러므로, i의 배치 가능한 위치의 개수를 ans에 곱해주면 된다.

 

 

 

5솔이지만 사실상 4솔에 가깝다. (E: *2000)

오렌지 퍼포가 무난하게(2분남기고E솔하긴했지만..) 나온다. 3번 정도 div.2 only에 참여해서 승급하는 희망이 보인다!