Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)

오랜만에 퍼포먼스 2000찍고 다시 학교 2등 탈환하나 했는데 헛된 망상이었다...(매우 기뻐하는 현 학교 2등)

숫자가 중복되어서 나타날 수도 있다는걸 망각했다.

A. Sum of 2050

우선 2050으로 나누어 떨어지지 않으면 -1

가능한 2050-number 들 중 큰 순서대로 최대한 많이 집어넣으면 되므로

n을 2050으로 나눈 수의 각 자릿수의 합이 답이 된다.

B. Morning Jogging

입력으로 들어오는 모든 수들 중 가장 작은 m개의 수를 각 m명의 선수들에게 항상 줄 수 있다. 따라서 정답이 되는 n * m 행렬을 만들었을 때, 숫자들을 잘 정렬해서 m개의 수들이 m개의 열에 각각 오도록 하면 된다.

C. Fillomino 2

주대각선의 가장 왼쪽부터 차례로 숫자들을 채워나가면 된다.

(i, i)위치에 하나 채웠다고 생각하고 그 다음부터 constructive하게 채워나갈 건데 이때, 채워나가는 우선순위는 위->왼->아래->오른 순으로 채우면 된다. (최대한 왼쪽-위 방향으로 뭉쳐있도록)

D. Explorer Space

일단 갔다가 다시 제자리로 와야 하니까 k가 홀수일때는 전부 -1을 출력하고 끝내면 된다.

가는 길이 최소라면 오는길이 같아야 똑같이 최소이므로 k/2 만큼 가는경우만 생각하면 된다.

dp[i][j][d] = (i, j)위치에서 d만큼 이동했을때 최솟값이라 하면

dp[i][j][d] = min(dp[i][j][d], dp[i+dx[a]][j+dy[a]][d-1] + dist[i][j][a]) (a : 상하좌우, dist[i][j][a] : (i, j)위치에서 a 방향으로 이동할때의 거리)

마지막으로 각 (i, j)위치에서 dp[i][j][k/2] * 2를 출력하면 된다.