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

1+2라 생각보다 풀만 했다. 블루 수복 완료

 

A. Sum of 2050

문제에서 정의한 2050-number를 잘 관찰해 보면 a * 2050*10^b + c * 2050*10^d + ... 이고 여기서 2050을 묶어내면 2050 * (a*10^b + c*10^d + ...)이다. 즉, 2050에 임의의 자연수가 곱해진 모양이므로 주어진 수를 2050으로 나눠보면 된다.

 

B. Morning Jogging

체크포인트 사이 경로들의 최솟값을 관리해주면 된다. 일단 수열 b_i를 정렬하자. i번째 체크 포인트까지 잘 도착했다고 해보자. i+1번째 체크포인트에 가는 경로들 b_ij를 잘 배분해서 최소가 되게 만들어줘야 할 것이다. 현재까지 각 경로의 최솟값(i번째 체크포인트까지 왔을 때 각 runner의 tiredness)을 t_j라고 하면, t의 각 원소들을 가능한 최소로 만드는게 최적이다. 따라서 pair(t, j)를 내림차순으로 정렬하고, 가장 큰 t_j에 b_i+1중 가장 큰 원소를 매칭해주자. 이 과정을 2차원벡터 등에 잘 저장해서 trace해주면 된다.

C. Fillomino 2

주대각선에 있는 숫자만큼 계단 모양을 인접하게 색칠해야 한다. 일단 주대각선에 있는 숫자들이 permutation이고 합이 계단 모양에 있는 칸 수와 같으므로 다 칠할 수 있다고 합리적 의심을 해보자. 만약에 (i, i)에 있는 수로 (i-1, i-1)을 방해하려면 i-1줄 이상으로 올라가야 한다. 그런데 i+1줄까지 가장 많이 칠해진 경우는 N, N-1, N-2, ... 만큼 칠해진 경우일 것이며 i+1줄까지 계단 모양의 칸 수 또한 N, N-1, N-2, ... 으로 서로 같다. 즉, 항상 자신과 같은 줄이나 그 아래 줄만 사용해서 모두 색칠할 수 있다. 따라서 최대한 아래쪽으로 붙여서 칠해나가면 항상 색칠이 가능하다.

 

D. Explorer Space (업솔빙)

역시나 DP가 발목을 잡는다. 1시간반이나 붙잡고 있었는데 다익스트라를 사용한 풀이로 풀다가 망했다.
dichoy27의 풀이는 이러하다. 일단 갔다 와야되니까 K가 홀수일때는 항상 불가능하다. 그리고 오는 길 가는 길 똑같으니까 K/2번 가는 것만 생각하면 된다. dp[i][j][d] = (i, j)위치에서 d만큼 이동했을 때 최솟값이라 하면, dp[i][j][d] = min(dp[i][j][d], dp[i+dx[k]][j+dy[k]][d-1] + dist[i][j][k]). 즉, 직전 위치 (i+dx[k], j+dy[k])에서 상하좌우로 이동해 온 거리 dist[i][j][k]를 더한 값과 현재 값 중 최솟값을 계속 관리해준다.