Codeforces Round #734 (Div. 3)

A. Polycarp and Coins (00:38, +)

\(n\)을 3으로 나눈 후, 나머지가 1이라면 1원 동전을, 2라면 2원 동전을 하나씩 더 써주면 된다.

 

B. Wonderful Coloring (01:12, +1)

주어진 수들을 정렬한 후, 각 숫자의 갯수가 \(k\) 개 초과인 경우를 주의하며 색을 차례대로 부여하면 풀린다.

B1은 수를 문자열로 바꾸고, k를 2로 고정한 버전이다.

 

C. Interesting Story (01:25, +1)

과반수 이상 등장하는 알파벳이 a라 하자. 이는 각 문자열마다 "a의 등장 횟수 - 다른 알파벳의 등장 횟수" 를 계산하고, 이를 내림차순으로 정렬해 누적합이 양수인 조건을 만족하며 더해주면 최대 개수의 문자열을 선택할 수 있다.

이를 b, c, d, e에 대해서도 시행해주면 문제를 해결할 수 있다.

 

D. Domino (01:35, +)

D2는 D1의 로직을 단순 구현하는 것이기 때문에, D1의 해결이 우선되어야 한다.

주어지는 격자판은 세 가지로 나눌 수 있다:

1. n과 m 모두 짝수인 경우
2. n은 짝수, m은 홀수인 경우
3. n은 홀수, m은 짝수인 경우

그 전에 한 가지 관찰이 필요한데, \(k\) 개의 수평 도미노를 모두 깐 후에는 남은 영역의 높이가 모두 짝수여야 수직 도미노로 덮는 것이 가능하다. 

이를 만족하기 위해서, 1번과 2번 경우에는 도미노를 정사각형 모양으로 쌓아 배치하는 방법을 생각해 볼 수 있다. 이 경우에 각 세로줄이 두 칸씩 제외되므로 항상 조건을 만족하고, 따라서 1번과 2번 경우에는 \(k\) 가 짝수여야 함을 알 수 있다. 추가로, 2번 경우에는 도미노를 왼쪽부터 쌓았을 때 가장 오른쪽 줄은 수직 도미노로만 채울 수 있다. 따라서, \(k<=n(m-1)/2 \)여야 한다.

3번 경우에는, 가장 윗 줄을 수평 도미노로 채워준다면 1번과 똑같은 경우로 만들 수 있다는 것을 알 수 있다. 따라서, 

\(k>=m/2\) 이고 \( k-m/2 \)가 짝수여야 한다.

 

E. Fixed Point (00:15, +)

\( DP[i][j] \)를 \(i\) 번째까지의 원소들로 길이 \(j\)인 수열을 만들었을 때에 조건을 만족하는 원소의 최대 개수로 정의하자.

\( DP[i][j] \) 는 간단한 점화식을 통해 구할 수 있는데,

• 이번 수열에 \(A_i\)를 포함하지 않는 경우

이와 같은 경우에 \(DP[i][j]=DP[i][j-1]\)이다.

• 이번 수열에 \(A_i\)를 포함하는 경우

길이 \(j\)인 수열에 \(A_i\)를 포함하려면, \(j={A_i}\) 여야 한다. 따라서, 이 경우 \(DP[i][j]=DP[i-1][j-1]+1\)이다.

 

이를 DP로 구현하면서 모든 \(DP[i][j]>=k\) 를 만족하는 j의 최댓값을 구하고, 이를 수열의 길이에서 빼준 값이 답이다.