Codeforces Round #809 (Div. 2)

https://codeforces.com/contest/1706

Dashboard - Codeforces Round #809 (Div. 2) - Codeforces

나는 미국 세터를 진짜 싫어한다. 문제들에서 유사코 맛이 난다...

 

 

A  (00:05)

 그리디하게 무조건 앞쪽부터 A로 바꾸면 된다.

 

B (00:16)

 타워의 높이를 늘리는 조건은, 그 다음 수의 인덱스가 홀수만큼 떨어져 있는 것이다.

 

C (00:29)

 N이 홀수일 때는 그냥 구하면 된다. N이 짝수일 때는, 단 한 곳에서만 2칸의 간격이 생기게 된다. 왼쪽 끝에서 1칸씩 띄고 누적 합을 만들고, 오른쪽 끝에서도 똑같이 해주자. \(L_{i} + R_{i + 3}\)의 최솟값이 답이다.

 

D1 (01:10)

 \(x\)가 max-min으로 가능한 값이라면, \(x\)보다 큰 값들 또한 가능하다. 이분 탐색을 하자. 각 \(x\)에 대해 min 값을 정해주면 max는 min + x가 될 것이다. p_i를 1부터 시작해서, \(A_i / P_i > max\)라면 p_i를 계속 1씩 올려주자. \(A_i / P_i < min\)인 순간이 존재한다면 해당 min값에 대해서는 불가능한 경우이다. \(O(N^2lgN)\)

 

D2 (--:--)

\(O(N\sqrt{N}lgN)\)으로 풀면 될 것 같다. \(A_i / p\)와 \(p\)는 \(sqrt(A_i)\)를 중심으로 대칭임을 이용하여, 답에 영향을 주는 p만 확인하면 될 것 같다.. 이게 맞는지는 잘 ㅁ?ㄹ

 

E (--:--)

 크루스칼의 공과 같은 문제다. 출제자가 문제 낼 게 없어서 그냥 아무거나 가져온 것으로밖에 안 보인다... 세그를 사용해도 되고(djs100201's solution), 매번 유파를 초기화해도 된다.