Codeforces Round #780 (Div. 3)

https://codeforces.com/contest/1660

Div.3 임을 고려하더라도 쉬운 편

 

A. Vasya and Coins

 

-> 1코인이 없다면 1원을 못 내며, 있다면 최대 금액까지 모두 지불 가능하다.

 

B. Vlad and Candies

 

-> 제일 많은 사탕이 두 번째로 많은 사탕보다 두 개 이상 더 많다면 불가능

 

C. Get an Even String

 

-> dp로 어떤 두 단어 사이를 날려버릴때 날려야 하는 수의 최소를 기록해놓으면 된다.

https://codeforces.com/contest/1660/submission/151528758

 

D. Maximum Product Strikes Back

 

-> 어차피 1과 2밖에 없지만 n이 2e5까지가므로 2의 지수와 부호를 기록하고 앞에서부터 해나가면 된다.

https://codeforces.com/contest/1660/submission/151542796

 

E. Matrix and Shifts

 

-> prefix sum으로 모든 대각선 방향 n개에 몇 개의 1이 있는지 알아내면 된다. O(n^2)

https://codeforces.com/contest/1660/submission/151551229

 

F. Promising String

 

naive : n^2으로 모든 쌍이 가능한지 확인해주면 된다. 이때 --를 +로 바꾸면 (+의 개수) - (-의 개수)가 3증가함에 유의.

밑의 풀이에서 prefix[j] = { j부터 i까지 +의 개수, j부터 i까지 --의 개수, 마지막 char}을 의미한다.

https://codeforces.com/contest/1660/submission/151557412

 

정해 : segtree에 psum을 기록해주면 된다.

-> 관찰하다보면 결국 최대로 조정하였을 때 무조건 (-의 개수) <= (+의 개수) + 1 임을 알 수 있다.

pf) 만일 아니라면 반드시 또 두 개의 -가 인접하고, 이들을 +로 바꾸어주는 과정을 반복하면 된다.

-> psum[i]을 (i까지의 +개수) - (i까지의 -개수)라 정의하자

-> i < j 일때 psum[i] >= psum[j] 이고 그 차이가 3의 배수임은 s(i, j)가 balance됨과 필요충분하다.

pf)

(->) 만일 그렇다면 psum[j] 와 psum[i] 사이에는 -가 +보다 많거나 수가 같다. 

     -> 첫 번째 관찰에 의해 이들 사이를 조정하면 -1 이상이 된다.

     -> 하지만, (+의 개수) - (-의 개수)가 3의 배수여야 하므로 -1이 되는 것은 불가능하고, 항상 0이 가능하다.

(<-) s(i, j)가 balance되어 있다면 당연히 -가 +이상이어야 하고 그 차이는 3의 배수가 되어야 한다.

https://codeforces.com/contest/1660/submission/151617492