[버추얼 매일 돌리기 프로젝트 #7] Codeforces Round #538 (Div. 2)

Codeforces Round #538 (Div. 2)

Dashboard - Codeforces Round #538 (Div. 2) - Codeforces

결과.

왤논 dp 변형 덕에 퍼플 퍼포를 달성하였다! 와!

근데 저것만 해도 너무 벅차다고 생각했고, 아직 퍼플 가기엔 좀 길이 남았다고 생각한다.

그리고 버추얼만 하면 뇌절 엄첨하는 것 같더라...제발..

 

A. Got Any Grapes?

Problem - A - Codeforces

문제에서 고려할 점만 잘 고려해주면 풀린다.

5분 AC.

여기서 맨탈 터질 뻔했으나 잘 수습했다. 다행

코드

 

B. Yet Another Array Partitioning Task

Problem - B - Codeforces

B 치곤 난이도가 좀 그랬던(?) 것 같다.

걍 그리디인데, 배열에서 큰 순서대로 m*k개의 정수를 뽑는다.

그렇다면 일단 첫번째 출력은 이 m*k개의 수들의 합일 것이고,

두번째 출력은 이 숫자들의 순서를 저장한 다음, 정렬해서 m*k번째 수를 제외한 m의 배수의 순서의 있는 순서들을 출력하면 된다. 

13분 AC.

코드

 

C. Trailing Loves (or L'oeufs?)

Problem - C - Codeforces

왤논 정수론 문제이다.
백준의 <팩토리얼 0의 갯수 (https://www.acmicpc.net/problem/1676)>문제에서 10진법을 n진법으로 바꿔버린 문제였다.

우리는 2와 5 대신 b의 각 소인수를 구하고, 각 n!에서 나오는 b의 각 소인수 갯수에 b의 각 소인수의 거듭제곱만큼 나누면 b를 이루는 갯수는 그 중에서 최소인 것이 된다.

설명하기가 너무 힘든 문제이다. 코드를 잘 참고해보시길...ㅠㅠ (+ 뇌절이 아주 심했던 문제.)

58분 AC.

코드

 

D. Flood Fill

Problem - D - Codeforces

이것도 KOI <전구 (https://www.acmicpc.net/problem/2449)> 문제의 변형 문제이다.

그러나 KOI 전구문제처럼 O(N^3)처럼 풀기 힘듦을 알 것이다.

그래서 dp배열의 정의는 비슷하게 하되, 약간 바꾸어서 O(N^2)으로 풀 수 있게 할 것이다.

dp[i][j][k] = i~j까지 모두 합치고, 마지막으로 범위를 넓힌 방향이 k일때(k=0은 왼쪽, k=1은 오른쪽), 쓰이는 최소의 비용

dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][k]+(a[k ? j : i+1]!=a[i])

dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][k]+(a[k ? j-1 : i]!=a[j])

이렇게 되면 2*N^2번의 계산을 하게 되어 O(N^2)만에 풀 수 있게 된다.

1시간 36분 AC.

코드

 

생각보다 재밌는 라운드였다.