코드포스 - Codeforces Round #634 (Div. 3)

오랜만에 코드포스를 했다.

 

6솔 할 수 있었는데 생각하지도 못한 부분 때문에 TLE가 떠서 5솔 밖에 하지 못했다...

 

A. Candies and Two Sisters

Problem - A - Codeforces

a > 0, b > 0이고 a > b를 만족하는 a + b = n의 개수를 찾는 문제이다.

 

n > 2 일때 b는 1부터 (n - 1) / 2까지 가능하고 n <= 2 일땐 0이다.

근데 결국 n >= 1일땐 (n - 1) / 2로 계산 가능하므로 그냥 n을 받으면 (n-1)/2를 출력하는 소스를 짜면 된다.

 

 

 

B. Construct the String 

Problem - B - Codeforces

각 케이스 마다 n, a, b가 주어지는데 n은 문자열의 길이, a는 부분 문자열의 길이, b는 부분 문자열에서 단어의 종류를 뜻한다.

즉 문자열 n을 만들어야하는데 길이가 a인 부분 문자열 중에서 단어가 b개가 나오도록 만들어야 한다.

 

처음 'a'을 시작으로 최대 'a' + b - 1까지 문자열 출력하면서 반복하면 된다.

 

 

C. Two Teams Composing

Problem - C - Codeforces

수열이 주어지는데 이를 조건에 잘 맞게 나누면 되는 문제이다. 조건은 아래와 같다.

수열 두개로 나눴을때 각각 A, B라 하자.

1. A의 크기(원소 개수)와 B의 크기(원소 개수)가 같아야 한다. 

2. A의 수열에서는 중복되는 수가 있으면 안되고  B에서는 모든 수가 같아야 한다.

 

위 조건을 만족하게 나눴을때 가장 크게 만들 수 있는 부분 수열의 크기를 구하면 된다.

난 숫자의 종류(S)를 파악하는 것과 하나의 숫자가 가장 많은 것(T)을 가지고 판단을 하였다.

1. S == T 일 경우는 T - 1
2. S != T 일 경우는 min(S, T)

 

D. Anti-Sudoku

Problem - D - Codeforces

문제를 대충 보자마자 든 생각은 1을 2로 바꾸면 되지 않을까라는 생각을 했지만 그 당시에는 확신을 가지지 못해서 안전한 코딩(구현)을 통해 맞추긴 했지만 맞추고 보니 처음에 생각한 풀이가 맞았다.

 

일반적인 스도쿠는 3x3 공간과 각 행과 열에 중복되는 수가 하나도 없다. 근데 anti 스도쿠는 그 해당하는 공간에 중복하는 수가 단 한 종류만 있어야 한다. 예를 들어 한 라인을 본다면 가능한 것은 (1 2 3 4 5 6 7 8 8) 이고 불가능한 것은 (1 2 3 4 5 6 8 8 8)이다.

 

스도쿠에서 겹치지 않게 수를 잡고 다른 수로 변경하면 된다. 근데 스도쿠에서는 하나의 숫자를 잡으면 겹치지 않기 때문에 하나의 숫자를 다른 숫자로 변경하면 끝나는 문제이다. 

 

E1. Three Blocks Palindrome (easy version) 

Problem - E1 - Codeforces

E2. Three Blocks Palindrome (hard version) 

Problem - E2 - Codeforces

하나의 수열에서 부분 수열 중 XYX형식 팰린드롬을 뽑고 그 중 가장 긴 것을 찾는 문제이다. X와 Y의 길이는 0이상이고 X와 Y를 구성하는 원소는 같다. E2를 풀면 E1은 그대로 풀 수 있어서 E2를 기준으로 풀었다.

 

입력되는 수열의 크기는 2 * 10^5 이고 원소는 1이상 200이하인 수가 들어온다.

어떤 수 k를 기준으로 l r을 이용해서 구간을 나눠보자. 0 ~ l에서 k의 숫자 개수와 r ~ n - 1에서 k의 숫자 개수(C)가 같도록 잡고 l와 r 사이에 1부터 200 사이의 수 중 가장 많은 것을 계산해서 (C * 2 + 1 ~ 200의 개수 중 l ~ r에 구간에서 가장 많은 것) 들 중의 최대값을 구하면 된다.

 

l와 r을 잡을 때 빠르게 O(1)만에 선택할 수 있도록 전처리를 하였다.

l <= r을 잡고 그 사이에 숫자의 개수가 가장 많은 것을 찾기 위해 이분탐색을 이용하여 log n만에 찾을 수 있게 하였다.

 

내가 짠 소스코드의 시간복잡도를 한번 구해보자.

TestCase에 대해선 신경 쓰지 말고 계산하자. (문제의 조건에 의해서 T가 1일때 가정하고 시간복잡도를 계산하면 된다.)

최악의 상황을 가정한다면 하나의 1이 n ( = 2 * 10 ^ 5) 개가 있다고 가정을 하자. 

대충 시간복잡도를 계산해보면 T( n/2*200 * log n)으로 O(nlogn)으로 돈다는 것을 확인 할 수 있다. n이 2*10^5이고 상수가 100으로 대충 계산을 해보면 4 * 10^8 정도로 돈다는 것을 확인할 수 있다.(이게 TLE 날 줄 알았는데 통과되니깐 놀랬다...) 사실 전처리를 잘 하면 log n을 없앨 수 있다. log n을 없애면 시간복잡도는 O(200N)이 되고 더 빠른 알고리즘으로 통과할 수 있다. 그 방법은 바로 prefix를 이용하면 된다.

 

 

F. Robots on a Grid

Problem - F - Codeforces

 

이 문제는 읽지는 못했지만 끝나고 다른 사람들 풀이를 듣고 보고 했을때 갓디디님의 풀이가 간단하고 신기해서 써본다. 

 

 

다음번에 공부해야할 부분은 memset(E1, E2 memset으로 그냥 했다가 TLE 떠서 뒤통수 맞았...)와  functional graph에 대해 공부해보려한다.