[Codeforces] Mail.Ru Cup 2018 Round 3

http://codeforces.com/contest/1056

 

A- Determine Line (Code)

 

그냥 배열에 등장횟수를 세던가, 제 코드처럼 등장하지 않은 원소의 스위치를 꺼버린다거나 하는 식으로 구하면 됩니다.

 

B - Divide Candies (Code)

 

1~N까지의 수들에 대해 $1^2, 2^2, 3^2, ... $ 에 대해 M으로 나눈 나머지가 1인게 몇 개인지, 2인게 몇 개인지 ,.. 를 구하고 나면 답을 알 수 있는데 N이 크고 M이 작기 때문에 1~N까지의 수 중에서 M으로 나눈 나머지가 0인 수의 갯수, 1인 수의 갯수, ... 를 구해서 M으로 나눈 각 나머지의 갯수를 알 수 있습니다.

 

C - Pick Heroes (Code)

 

직관적으로 생각해보면 선수/후수 여부에 관계없이 최대한 pair인 hero를 잡는게 좋습니다. 그러니 상대가 pair인 hero를 집어 나의 선택이 강제되는 경우에는 그냥 조건대로 처리하고, 그렇지 않을 때에는 pair가 남아있으면 pair간 차가 큰 hero를, pair가 남아있지 않으면 남은 hero중 가장 p가 큰 hero를 잡으면 됩니다. 코딩이 살짝 까다로웠습니다. D를 먼저 풀걸 그랬네요.

 

D - Decorate Apple Tree (Code)

 

맨 처음에 leaf에만 light가 달린다는 조건을 놓쳐서 예제가 이해가 안갔습니다. 각 node에 대해 subtree에 있는 leaf의 갯수를 구하고 이를 정렬하면 그게 바로 답입니다. 엄밀한 증명은 생각하지 않았는데 귀납법으로 보일 수 있을 것 같네요.

 

E - Check Transcription (Code)

 

0의 갯수를 a개, 1의 갯수를 b개, 0에 대응되는 문자열의 길이를 len0, 1에 대응되는 문자열의 길이를 len1이라고 할 때 $a*len0+b*len1=len(t)$이 성립되어야 하고 해당 식을 만족하는 정수 $(len0,len1)$ 쌍은 많아봐야 $len(t)/max(a,b)$개입니다. 이제 해당 쌍들에 대해 직접 t를 만들어나갈 수 있는지 라빈 카프 알고리즘을 이용해 $O(a+b)$에 확인할 수 있으니 $O(len(t))$에 갯수를 구할 수 있습니다. 풀이를 떠올리고 나서 해당 풀이의 시간복잡도가 $O(len(t))$임을 알아차리는데 시간이 조금 걸렸네요.