Codeforces Round 751 (Div. 1)

Div. 1을 돌자는 menborong님의 의견이 있어서 Div. 1을 돌았다. 어차피 C까지는 Div. 2에도 다 있어서 상관 없었던 것 같다.

 

A. Array Elimination (0:03, +)

\(k\)는 비트별로 봤을 때 1의 개수의 공통 약수여야 한다. gcd를 구해 주면 된다. 모두 0일때만 조심하자.

 

B. Frog Traveler (0:52, +3)

이 테크닉을 박으면 풀리는 형태라 박았다. 루트 버전으로 짜고 MLE를 3번 받은 후에야 세그트리 모양으로 갈아타서 맞았다. 정해가 쉬운데 조금 더 생각을 하는게 옳은 방향이었던 것 같다.

 

C. Optimal Insertion (1:48, +2)

B의 원소들을 넣어야 하는 최적의 위치를 찾아주자. B의 원소를 오름차순으로 보면서, 각 위치에 대해 해당 위치에 원소를 넣었을 때 생기는 inversion의 개수를 구해주어야 한다. 이는 레이지 세그를 잘 이용하면 구할 수 있다. 정해는 B의 두 원소에 대해 \(i<j\)일 때 최적의 위치가 \(opt(i)<opt(j)\)라는 것을 이용한 DnC 최적화였다. 이것도 구현을 좀 절었다.

 

D랑 E도 C와 점수 차이가 얼마 나지 않는다. 업솔빙 예정