[Codeforces] Avito Cool Challenge 2018

https://codeforces.com/contests/1081

 

문제는 그럭저럭 괜찮았습니다.

 

A - Definite Game (Code)

 

$n$과 $n-1$은 서로소이므로 $n-1$을 빼서 1을 만들면 됩니다. 그러나 n=2일때에 한해 답이 2입니다. 처음으로 1분대에 문제를 맞아본 것 같네요.

 

B - Farewell Party (Code)

 

편의상 나와 동일한 모자를 쓴 사람의 수를 생각합시다.($n-a[i]$를 계산하기만 하면 됨) 나와 동일한 모자를 쓴 사람의 수를 $t[i]$라고 할 때, 모든 $i = 1 to n$에 대해 $t[i]$는 $i$의 배수여야 합니다. 그리고 조금만 생각해보면 이것이 필요충분조건임을 알 수 있습니다.

 

C - Colorful Bricks (Code)

 

$D[i][j]$를 현재 $i$개의 블럭에 색칠을 완료했고 left와 색이 다른 블럭이 $j$개 있는 경우의 수라고 해봅시다. 그러면 $D[i][j] = (m-1)D[i-1][j-1] + D[i-1][j]$로 계산이 가능합니다.

 

D - Maximum Distance (Code)

 

이 문제에서 시간을 정말 많이 뺏기고 special에서 special로 가야한다는 조건을 놓쳐서 hack까지 한 번 당했습니다ㅠ_ㅠ 문제 설명에 max min max이 주구장창 나와서 굉장히 헷갈리는데, 결론적으로 $dist(u,v) = t$라는 의미는 u에서 v까지 가는 모든 경로에서 t 이상의 간선이 반드시 등장한다는 의미입니다. 그러므로 크루스칼 알고리즘으로 MST를 만드는 과정처럼 간선을 크기가 작은 것 부터 연결을 해나가면서 special이 모두 연결된 순간의 간선의 크기가 모든 special 점들에 대한 답입니다.

 

E - Missing Numbers (Code)

 

제곱수들간의 차는 3, 5, 7, 9, ... 입니다. 그리고 $x[2], x[3], x[4], ... $는 두 제곱수의 차를 의미합니다. 이제 $a[i] = \sqrt{x[1]+x[2]+x[3]+...+x[i]}$ 이라고 할 때 $x[k]$는 $(2a[k-1]+1) + (2a[k-1]+3) + ... + (2a[k]-1)$로 표현이 가능하고 이 수열의 합에서 수열의 시작점은 계속 증가해야 합니다.

 

이제 첫 번째 예시로 설명을 하겠습니다. 5 11 44는

 

3 5 7 9 11 13 15 17 19 21 23 25 ...  로 구성이 되고 시작점인 $2^2=4$는 $x[1]$, 중간의 (7, 9), (13, 15, 17, 19)는 각각 $x[3]=16,x[5]=64$를 맡게 됩니다.

 

직관적으로 생각해보면 주어진 $x[2k]$를 홀수들의 합으로 나타낼 때 가능한 왼쪽에 있는 것들을 먼저 활용하는 것이 좋습니다. 그렇게 해야 이 다음의 원소가 더 많은 가능성을 가질테니까요. 이제 이 홀수들의 합 수열을 구하기 위해 미리 수들의 약수를 구해놓아야 합니다.

 

D에서 다들 엄청 터져서 생각만큼 많이 깎이진 않았지만 D에서 너무 헤맨게 아쉽네요. 레드 가고싶드아아악