Codeforces Round 827 (Div. 4)

Dashboard - Codeforces Round 827 (Div. 4) - Codeforces

 

E

배열 a의 누적합 배열 b, prefix max array c를 생각하자
bi = a1 + a2 + ... + ai
ci = max(a1, a2, ... , ai)

다리길이가 ci 이상이라면 적어도 높이 bi만큼은 올라 갈 수 있다. 하지만 다리 길이가 ci 미만이면 높이 bi만큼 올라가지 못한다. 따라서 다리길이가 k이면 올라갈 수 있는 최대 높이를 구하려면 k이하인 cj 중 가장 오른쪽에 있는 cj의 index인 j를 찾으면 된다. 답은 bj

 

F

문자열 s와 t를 각각 재배열하여 s < t 를 만족하도록 할 수 있는지를 묻고 있다. 그리디하게 s는 오름차순으로, t는 내림차순으로 정렬하여 생각해보자.

s와 t는 문자 'a'를 갖고 있으므로 t가 'a'가 아닌 다른 알파벳을 갖고있으면 s < t 가능.
한편, t가 문자 'a' 밖에 갖고 있지 않다고 하자. s가 'a'가 아닌 다른 알파벳을 갖고있으면 s < t 불가능.
이제 남은 경우의 수는 s와 t 모두 'a'만 갖고 있는 경우이다. (s의 'a'개수) < (t의 'a'개수) iff s < t 가능

 

G

배열 b를 관찰해보자. 배열 b의 각 원소는 왼쪽 원소의 비트 몇 개를 pop up(0에서 1로 바꿈)하는 방식으로 구성된다.
이때 배열 b의 최대값은 111...11(1이 30개) 이므로 배열 b의 원소가 증가하는 부분은 많아야 30번이다. 따라서 brute force 방식으로 답을 찾을 수 있다.