[Codeforces] Round #474 (Div.1 + Div.2)

보라로 올라간 이후 처음으로 치룬 라운드입니다. 그리고 파랑색으로 강등됐습니다 ㅠ_ㅠ A < B < C <<< D = E = F << G 인 느낌이었습니다.

 

A - Check the string

 

시킨대로 짜면 됩니다. a -> b -> c 순이어야 한다는 조건에 주의해야합니다. 다른 사람들의 코드를 보니 정렬을 이용해서 순서가 맞는지를 확인하는 코드가 있었는데 괜찮은 방법인 것 같습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20474/A.cpp

 

B - Minimize the error

 

Greedy하게 에러가 가장 큰 것을 찾아 에러를 줄이는 방식으로 해결하면 됩니다. Priority Queue를 이용하면 O(NlgN)에 풀 수 있고 N이 작아 저는 그냥 정렬을 이용한 O(N^2lgN)짜리 풀이로 해결했습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20474/B.cpp

 

C - Subsequence Counting

 

$i$개의 같은 수가 있으면 $2^i - 1$개의 subsequence를 얻을 수 있으므로 그냥 Greedy하게 선택하면 끝입니다. 그런데 수열의 수가 같아도 되는걸 lock을 한 후에 깨달아서 C를 그대로 날려먹었습니다ㅠㅠ

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20474/C.cpp

 

C를 날려먹음으로 인해 깔끔하게 조졌습니다. 또 D / E/ F 중에 어느 한 문제도 풀어내지 못한 것도 아쉽습니다. F를 붙잡았는데 잘 안떠올라서ㅠㅠ 이틀 뒤에 있는 라운드에서 다시 퍼플로 올라서야겠습니다ㅠㅠ 그래도 A, B를 나름대로 빠른 시간에 풀어낸 것은 만족스럽습니다.