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/
웰노운이었던 문제
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] 고속 푸리에 변환(Fast Fourier Transform) part. 1 (0) | 2022.06.03 |
---|---|
[알고리즘] Codeforces Round #784 (Div. 4) (0) | 2022.04.22 |
[알고리즘] Codeforces Round #774 (Div. 2) (0) | 2022.03.05 |
[알고리즘] 순열 사이클 분할 (0) | 2022.03.03 |
[알고리즘] Codeforces Round #772 (Div. 2) (0) | 2022.02.21 |