Codeforces educational round 32

I. Introduction

이 포스트에서는 codeforces.com 에서 진행된 Educational Round 32에 대해서 살펴봅니다.

 

II. Solve

[Prob A] – Local Extrema

배열 a가 있다. 이 배열의 원소 a_i 은 자신의 양 옆의 값보다 작으면 (a_i < a_{i-1} \; and \;   a_i  < a_{i+1}) local minimum이라 불린다. 또한 자신의 양 옆의 값보다 크면 local maximum이라 불린다. local minimum이거나 local maximum인 원소를 local extremum이라 한다. local extremum의 원소의 수를 구하여라.

 

문제 풀이

O(n)의 시간 복잡도로 해결할 수 있다.

( 2 <= i <= n-1 ) 의 반복문을 수행하며 양 옆의 원소와 비교해 조건에 해당하는 것을 카운팅하면 끝이다.

 

코드


 

[Prob B] – Buggy Robot

Ivan은 무한한 평면 그리드에 놓인 로봇을 가지고 있다. 초기 로봇의 위치는 (0,0)이고 다음과 같은 명령에 따라 움직인다.

  • U – (x, y)에서 (x, y + 1)로 이동
  • D – (x, y)에서 (x, y – 1)로 이동
  • L – (x, y)에서 (x – 1, y)로 이동
  • R – (x, y)에서 (x + 1, y)로 이동

Ivan은 n개의 command를 연속으로 입력했고 로봇은 이에 따라 움직여 최종적으로 (0, 0)에서 멈추었다. Ivan은 입력한 command가 정확한지 궁금했다. 그는 어떤 command를 로봇이 무시했다고 생각했다. 로봇에 버그가 존재하는지 알기 위해, 그는 제대로 동작한 command의 최대 갯수를 알고 싶어한다. 이 수를 구하여라.

 

문제 풀이

O(n)의 시간 복잡도로 해결할 수 있다.

(0, 0)에서 (0, 0)으로 다시 돌아오기 위한 command 쌍의 가장 간단한 형태는 L + R 또는 U + D이다. 이들의 순서는 상관없기 때문에 command를 하나씩 살피면서 갯수를 합쳐 준 다음에 최종 커맨드 수에서 이 쌍의 수만 골라내면 올바른 command의 최대 수를 알 수 있다.

 

코드


 

[Prob C] – K-Dominant Character

알파벳 소문자로 이루어진 문자열 s가 있다. 문자 c는 문자열 s의 부분 문자열 중 최소 k의 길이가 되는 것 중 c를 포함하는 부분 문자열이 존재할 때 k-dominant라고 한다. 예를 들어서 abacaba에서는 k = 2로 설정하면 어떤 경우에도 항상 a는 포함되는 것을 알 수 있다.

최소한 하나의 k-dominant가 존재하는 최소의 k를 출력하여라.

 

문제 풀이

O(n)의 시간 복잡도로 해결할 수 있다.

어떤 문자 c가 등장하고 그 다음으로 문자 c가 등장하기까지의 간격 중 최대의 간격을 배열에 저장한다. 예를 들어 위의 abacaba에서는 A[‘a’] = 2, A[‘b’] = 4, A[‘c’] = infinite 이다. 문자의 첫 등장은 이전 등장이 없고 마지막 등장은 다음 등장이 없기 때문에 각각 문자열의 시작과 끝을 기준으로 최대 간격을 비교해주어야 한다.

이 배열의 값 중 최소의 값과 (문자열의 길이 / 2) + 1 중 작은 것이 답이다. 모든 문자가 하나씩만 등장하는 경우에는 문자열의 중앙에 있는 문자가 항상 포함되는 부분문자열의 길이를 k로 택하면 되는데 이것이 (문자열의 길이 / 2) + 1이기 때문이다.

 

코드


 

[Prob D] – Almost Identity Permutations

크기 n을 갖는 순열 p는 1부터 n까지의 수가 한 번씩만 등장하는 배열이다.

이 순열 중에서 p_i = i 인 원소가 최소한 n-k개 존재한다면 이것을 almost identity permutation이라 부른다.

n과 k가 주어질 때 almost permutation의 수를 구하시오.

 

문제 풀이

주어진 문제에서 ( 1 <= k <= 4 ) 이므로, 문제를 약간 변형해서 p_i \ne i 인 원소가 최대 k개인 경우를 찾으면 된다.

임의의 m개의 원소가 p_i \ne i 일 때 이들은 서로의 자리를 교환하여 조건을 만족한다. 이외의 n-m개의 원소들은 모두 자신의 자리에 그대로 있기 때문이다. 이 경우의 수를 f(m)이라고 하면, f(0) = 1, f(1) = 0, f(2) = 1,  f(3) = 2, f(4) = 9이다.

정답은 \sum_{m=0}^k {f(k) * {n \choose k}} 이다.

 

코드


 

[Prob E] – Maximum Subsequence

n개의 정수로 이루어진 수열 a가 있다. m이 주어질 때, 임의의 인덱스 수열 b를 (1 \le b_1 \le b_2 \le ... \le b_k \le n ) 을 만족하게 구성하였을 때 \sum_{i = 1}^k{ a_{b_i} mod m } 의 가능한 최댓값을 구하여라.

(1 \le n \le 35 , 1 \le m \le 10^9 ) 이다.

 

문제 풀이

문제에서 주어진 n의 크기에서 힌트를 얻어야 한다. n은 최대가 35이므로, 절반으로 나누면 18, 17이 된다.

즉, 이 절반들에 대해서 각각 가능한 모든 조합을 수행하여 나머지 값을 구한다. 앞의 절반을 배열 A, 나머지를 B에 담는다고 할 때 두 배열을 모두 정렬시키고 모든 A값에 대해서 가장 최대의 Mod M을 만들 수 있는 B를 이분검색을 통해 찾아낼 수 있다.

2^18 = 262,144 이므로 시간이 그렇게 많이 걸리지도 않는다.

배열 A의 각 원소에 대해서 알맞은 B를 찾기 위한 탐색을 시작한다. 가능한 나머지의 최댓값은 M – 1이므로, 정렬되어 있는 B에서 찾아야 할 것은 A[i]에 대해 M – 1 – A[i]와 같거나 작은 것 중 최대 값의 인덱스다.

이 인덱스를 j라고 할 때 A[i] + B[j] 또는 A[i] + B[len(B) – 1] 중 가장 큰 것이 A[i]에 속한 원소들을 택했을 때 가능한 최대의 결과다. 모든 i에 대해 반복문을 수행하여 그 중 최대를 가지는 것을 출력하면 된다. 시간복잡도는 O(n * 2^(n/2 – 1))이다.

 

코드


 

[Prob F] – Connecting Vertics

평면에 n개의 점이 있으며, 이들은 정다각형을 이루고 있다. 여기에서 당신은 n-1개의 선분을 그릴 수 있는데, 각각은 두 개의 정점을 잇는다. 이러한 방법으로 이 점들은 모든 쌍이 직접적으로 연결되거나 간적접으로 연결된다.

그러나 여기에 제한사항이 주어진다. 첫 째로 어떤 점들은 직접적으로 연결될 수 없으며 오로지 간적접으로만 이어져야한다. 둘째로, 당신이 그리는 선분은 정점을 제외하고는 어떤 교차점도 서로 가질 수 없다. n-1개의 선분으로 정점을 모두 연결하는 경우의 수를 구하여라. 수가 클 경우에는 10^9 + 7 로 나눈 나머지를 출력하여라.

입력으로는 정점의 수와 행렬정보가 주어진다.

정점의 수 N은 ( 3 \le N \le 500 ) 이며, 행렬 a_{i, j} = 1 이면 두 점은 직접적으로 연결될 수 있다.

 

문제 풀이

다이나믹 프로그래밍으로 해결하는 문제다.

DP[i][j]를 i와 j가 이미 연결되어 있을 때 i와 j 사이에 존재하는 정점들을 i 또는 j에 연결하는 경우의 수라고 하자. 이렇게 DP를 설정하면 i와 j 사이의 정점이 (i, j) 구간 바깥의 점에 연결된 경우를 없앨 수 있다.

DP[i][j]를 구하는 방법에 대하여 알아보자. 만약 i-번째 정점을 x번째 정점에 연결하려 한다고 하자. (i, j)구간의 정점을 모두 연결상태로 만들기 위해서는 (i, j) 사이에 존재하는 모든 점들은 i 또는 x에 연결되어 있어야 한다. (x, j)구간의 정점들은 어떠한가. 이 점들은 x, j 또는 i와 연결되어 있어야 한다. 여기서 (x, j)구간의 점들과 i의 연결을 다루기 힘들다.

이것을 간단히 하기 위해서 x를 i와 직접적으로 연결한 모든 점 중 가장 인덱스가 큰 것으로 고르고, 반대로 어떤 것을 j와 연결할 때는 직접적으로 연결한 모든 점 중 가장 인덱스가 작은 것으로 고른다. 이렇게 되면 이 인덱스를 기점으로 i에 가까운 것은 j와 직접적으로 연결될 수 없고, j에 가까운 것은 i와 직접적으로 연결될 수 없다.