[알고리즘] Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics)

C까지 30~40분 안에 풀면 블루 갈 수 있을거 같다. (최대한 틀리지 않고)

D부터는 너무 벽이 느껴진다..

블루 가즈아

A - Game [Solved!]

1인 땅은 밟을 수 있고 0인 땅은 밟을 수 없다. 인접한 땅은 무료로 여러번 이동할 수 있고 그렇지 않은 경우 1회에 한해 $x$코인을 소비하여 $x$만큼 건너 뛸 수 있다. 이때 처음부터 끝까지 가는데 드는 코인의 최솟값을 구하는 문제이다.

 

0이 없으면 0원, 아니면 가장 왼쪽에서 처음나오는 0의 위치를 가장 오른쪽에서 처음 나오는 0의 위치에서 빼고 1을 더한값이 답이된다. (여론이 안좋은 문제)

 

B - Game of Ball Passing [Solved!]

$a_i$를 $i$번째 선수가 패스를 하는 횟수라고 할 때 모든 선수가 패스를 하려면 몇번의 경기를 하는지 구하는 문제이다.

 

모두 0이면 답은 0일 것이다.

결론부터 말하면 가장 큰 수를 제외한 수들의 합을 $s$라고 하고 가장 큰 수를 $m$이라고 하면 $s \ge m$이면 $1$이고 아니면 $m-s$이다.

예를들어 $1,1,1,1,7$이라고 하면 $5 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 5 \rightarrow 1 \rightarrow 5 \rightarrow 1$이 되어 $0,0,0,0,2$가 남고 답은 3이 된다.

반면 $1,2,3,4,7$이면 어떻게든 한번에 끝내는 경우가 생긴다.

 

C - Weird Sum [Solved!]

$S(x) = \{(i,j) | a_{i,j} = x\}$라고 하자. 가능한 모든 집합 $S$에 대해 집합내 모든 쌍의 택시거리를 합한 값을 구하는 문제이다.

 

https://www.geeksforgeeks.org/sum-manhattan-distances-pairs-points/

Sum of Manhattan distances between all pairs of points - GeeksforGeeks

웰노운이었던 문제