CodeForces Round #731 A~F (Div.3)

https://codeforces.com/contest/1547

Dashboard - Codeforces Round #731 (Div. 3) - Codeforces

 

푼 순서대로.

 

A (00:04)

A, B가 같은 선상에 있으면 거리 + 2

그러니까 이런경우..

 

B (00:08)

거꾸로 가면 된다. 마지막 알파벳부터 a까지, 가장자리부터 투포인터 조지면 된다.

 

 

D (00:18)

이게 끝이다. 처음 값은 무조건 0이고, 쭉 밀면 된다.

 

 

C (00:28)

본문이 엄청 길다. 그냥 얘도 투포인터(a에 하나 b에 하나)로 왼쪽부터 채우되, a b 둘다 채우는게 불가능하다면 -1이고 아니면 답 출력.

 

 

E (00:59)

개 귀찮은 문제였다. 그리디하게 최소를 가지는 에어컨들만 골라내고 답 구하면 끝

 

 

이러고 F 못풀고 끝났다. 너무 졸렸음

 

F

마지막 값은 배열 A의 모든 수의 gcd이다. 그리고 배열 복사(?)를 k번 반복하면 \(a_{i}\)는 \(gcd(a_{i}, ... , a_{i+k})\)가 된다.

이 \(a_{i}\)들의 값이 모두 같게 하는 k를 찾는 것이니 sparse table, segment tree 등을 사용해서 k번 반복했을때의 \(a_{i}\)를 빠르게 찾을수있다. 그리고 이 k는 이분탐색으로 구하면 된다.

 

무지성 세그트리를 못 떠올렸다..

 

블루가 코 앞이다