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와 직접적으로 연결될 수 없다.

CodeChef November Challenge 2017 (1)

I. Introduction

이 포스트에서는 CodeChef.com 에서 진행된 November Challenge에 대해서 살펴봅니다.

여기에서는 앞선 5개의 문제를 살펴보고 추후 포스팅에서 나머지 5개의 문제를 다를 예정입니다.

  • 문제 수 : 10개
  • 진행 시간 : 10일
  • 레이팅 구간 : 전체
  • 대회 링크 : https://www.codechef.com/NOV17

 

II. Solve

[Prob A] – Villages and Tribes (VILTRIBE)

문제 링크 : https://www.codechef.com/NOV17/problems/VILTRIBE

n개의 마을이 있다. 여기에는 A와 B의 두 부족이 있는데, 마을은 비어있거나 이 두 부족 중 하나에게 점령되어 있다. 비어있는 마을은 A 부족에게 좌우로 둘러싸여져 있다면 A 부족의 지배를 받고, B부족에게 좌우로 둘러싸여져 있다면 B부족의 지배를 받는다.

A와 B 부족에게 점령당하거나 지배를 받는 마을의 수를 각각 구하여라.

 

문제 풀이

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

Prev라는 변수는 가장 최근에 지나친 점령된 마을을 지배하는 부족이라고 하자. 새로운 점령된 마을을 발견했을 때 Prev와 동일한 부족이라면 Prev와 현재 사이의 모든 마을은 해당 부족에게 점령당했다고 볼 수 있다. 이 방식은 부족이 A와 B가 아닌 여럿일 경우에도 동일하게 사용될 수 있다.

 

사용 알고리즘

  • 없음

 

코드


 

[Prob B] – Chef goes Left Right Left (CLRL)

문제 링크 : https://www.codechef.com/NOV17/problems/CLRL

Chef는 현재 Reziba를 추적하려고 한다. 하지만 그가 알고 있는 것은 사람들의 각기 다른 CodeXP rating 뿐이다. Reziba는 현재 Expo에 있으므로 Chef는 Reziba의 rating을 통해 Expo에 있는 사람들로부터 Reziba를 찾아내려고 한다.

하지만 Chef는 Reziba의 rating을 모른다. 대신 Expo에 있는 나머지 모든 사람들이 Reziba의 rating을 알고 있다. 따라서 Chef는 다음과 같은 방법으로 Reziba를 찾아내기로 한다.

Expo의 사람들은 현재 rating의 오름차순으로 일렬로 정렬되어 있다. 맨 처음 Chef는 임의의 어떤 사람에게 질문을 하고, 그는 자신의 rating이 Reziba보다 높고 작음에 따라 Reziba가 자신을 기준으로 왼쪽에 있거나 오른쪽에 있다고 응답한다. 그러면 Chef는 응답받은 방향으로 어느 정도 이동한 후 다시 멈춰서 그 자리에 있는 사람에게 질문을 계속해나간다. 여기서 제약이 존재한다. Chef는 이동 시에 동일한 지점을 두 번 방문할 수 없다. 최종적으로 Chef는 Reziba의 앞에서 이동을 종료한다.

이 수색 과정에서 Chef는 자신에게 응답한 사람들의 rating을 응답 순서대로 기록했다. 이 기록의 마지막은 Reziba의 것이다. Chef는 기록이 틀리지 않았는지 알고 싶어한다. 이를 출력하여라.

 

문제 풀이

상한과 하한을 계속해서 낮춰가면서 범위를 좁히는 탐색이다. 입력에서는 Reziba의 rating이 주어졌으므로 기록을 통해 사람들이 left, right 중 무엇으로 답했는지 알 수 있다.

(l, r)의 rating 사이에 Reziba가 존재한다고 가정하자. 초기의 l과 r은 각각 0과 infinite이다. rating이 R_i 인 사람이 right라고 답했으면 l = R_i 이 된다. 반대로 left라고 말했으면 r = R_i 이다. 응답자들은 모두 현재의 범위 내의 rating을 가지고 있어야 한다. 그렇지 않다는 것은 Chef가 l 또는 r의 값을 가진 사람을 두 번 지나쳤다는 것이기 때문이다.

따라서 과정은 매우 간단하다.

  • 현재 응답자가 (l, r)의 범위 내에 있는지 판별한다.
  • 범위 내에 있으면 Reziba의 rating과 비교하여 응답을 알아낸 후 응답에 따라 l 또는 r을 응답자의 rating으로 패치한다.

 

사용 알고리즘

  • 상한 하한

 

코드


 

[Prob C] – Periodic Palindrome Construction (PERPALIN)

문제 링크 : https://www.codechef.com/NOV17/problems/PERPALIN

Chef는 최근 문자열의 주기성에 대해 배웠다. 길이 N인 문자열은 P \mid N 인 P가 존재하며, 길이 P인 문자열이 N / P 번 반복되는 문자를 말한다. 예를 들어 문자열 “abab”는 2와 4의 주기를 갖는다.

Chef는 펠린드롬이면서 동시에 P의 주기를 갖는 문자열을 만들고 싶어한다. 문자열은 ‘a’와 ‘b’로만 구성된다. 단, Chef는 둘 중 하나의 문자로만 구성된 문자는 싫어한다. N이 반드시 P의 배수로 주어진다고 할 때 그러한 펠린드롬 문자열을 구할 수 있다면 예시를 하나 출력하고, 그렇지 않으면 ‘impossible’을 출력하라.

 

문제 풀이

우선 P가 1인 경우를 살펴보면 Chef가 싫어하는 문자열이다.

P가 2인 경우를 살펴보면 가능한 문자열이 ‘ab’나 ‘ba’ 연속인데 펠린드롬을 만들 수가 없다.

P가 3이 이상인 경우를 살펴보면 ‘aba’나 ‘abba’와 같은 P를 만들 수 있다. P가 그 자체로 펠린드롬이므로 P를 몇 개를 이어 붙이더라도 펠린드롬이 된다.

따라서 P가 1 또는 2인 경우에는 ‘impossible’이며, 이외의 경우에는 길이 P의 abbb….bbba를 (N / P)개 출력하면 된다.

 

사용 알고리즘

  • 펠린드롬의 성질

 

코드


 

[Prob D] – Chef Hates Palindromes (CHEFHPAL)

문제 링크 : https://www.codechef.com/NOV17/problems/CHEFHPAL

Fehc는 Chef에게 길이 N인 문자열을 선물로 주려고 한다.

Chef가 펠린드롬을 싫어하기 때문에 Fehc는 문자열에서 뽑을 수 있는 펠린드롬을 이루는 부분문자열의 최대길이가 가능한 짧기를 바란다. 문자열은 A개의 문자만 사용할 수 있다. 예를 들어 A = 3이면 ‘a’,’b’,’c’만 문자로 사용가능하다. 만들어야 할 문자열의 길이 N과 사용 가능한 문자의 수 A가 주어질 때 만들 수 있는 문자를 출력하여라.

문제 풀이

이 문제는 생각이 아닌 관찰로 푸는 문제다. 브루트포싱으로 풀기 때문이다.

A의 크기에 따라 경우를 나누어본다.

  • A = 1인 경우 단순히 N의 길이의 ‘aaaa….aaaa’를 출력하면 된다.
  • A > 2인 경우 단순히 ‘abcabcabc…’ 형태로 N의 길이만큼 출력하면 된다.
  • A = 2인 경우만 해결하면 되는데 이걸 좀 심각하게 생각해야 한다.

N = 15 길이로 만들 수 있는 모든 문자들을 최대 펠린드롬 길이로 정렬해보면 패턴을 찾을 수 있다.

일단 최대 펠린드롬의 길이가 N = 8부터는 4로 유지된다는 점과, ‘aabb abaa bbab’가 반복되는 문자열이 존재한다는 것이다. 즉, 이것만 반복시키면 최대 펠린드롬의 길이는 4이상으로 늘어나지 않는다. N이 8이하인 경우까지는 문자의 길이가 매우 작기 때문에 단순히 모든 경우를 발생시켜 조사한 후 최소를 출력해도 된다. 내 경우에는 다른 방식으로 풀던 코드가 쓸모없게 되면서 그냥 재활용 차원에서 남겨두었는데 가장 깔끔한 방식은 그냥 배열에 1 <= N <= 8인 경우까지는 예시를 미리 저장했다가 출력하는 것이다.

문제가 안 풀릴때는 N의 크기를 줄이면서 관찰하는 것이 필요하다는 것을 알려주는 것 같지만 매우 짜증난다.

 

사용 알고리즘

  • 브루트포스

코드


 

[Prob E] – Chef and Intersection Line (CHEFNIL)

문제 링크 : https://www.codechef.com/problems/CHEFNIL

Chef는 A[M][N][N]의 3차원 행렬을 가지고 M초 동안 게임을 진행한다. 1 <= k <= M 에 해당하는 각 k초마다 Chef는 (i, j)의 쌍을 하나 골라 A[k][i][j]의 점수를 얻는다.

또한 그녀는 2차원 평면을 가지고 있는데, k = 2일 때부터 그녀는 평면에 k-1초에 골랐던 (i, j)와 k초에 고른 (i, j)를 잇는 선분을 그린다. 게임의 룰은 이 선분이 교차하지 않으면서 최대의 점수를 얻는 것이다. 물론 그녀가 선분을 그리는 방식에 의해서 직전에 그렸던 선분과 현재 그린 선분이 가지는 하나의 교점은 교차로 취급하지 않는다.

k = 1초부터 그녀가 선택한 (i, j)쌍을 한 줄씩 출력하여라.

그녀가 꼭 M초동안 게임을 진행할 필요는 없다. 게임 도중에 그만두고 싶으면 -1 -1을 출력한다.

 

문제 풀이

이 풀이는 1.0점 만점에서 0.61점을 받았기 때문에 61% 정도의 답안의 역할만 한다.

M의 크기 제한이 500, N이 50으로 주어지기 때문에 탐색 자체만으로도 계산량이 적지 않은 수준이다.

게임에서는 반드시 축과 수평하게 이동할 필요가 없기 때문에 어떤 선분이라도 두 점을 이을 수만 있고, 교차하지 않는다면 그릴 수 있다. 하지만 그것까지 고려할 방법은 생각하지 못했기 때문에 나는 진행경로를 DP를 쓰기에 가장 좋은 방식으로 설정하고, 정해진 경로에서 최적의 해를 구하는 방식을 쓰기로 했다.

설정한 경로은 (1,1)을 행렬의 최상단, 좌측으로 잡고 행이 홀수일 때는 오른쪽으로 이동하고, 짝수일 때는 왼쪽으로 이동하는 아래 그림과 같은 방식이다.

즉, D[k][i][j]는 그 이전 단계로 가능한 D[k-1][i][j] 중에서 가장 최적인 것을 골라 자신의 해에 추가한다.

아래로의 이동을 위해서는 반드시 행의 좌우측 끝을 선택해야만 하기 때문에 주어진 경로를 완전히 자유롭게 사용할 수 없다. 이것을 약간 보완하기 위해서 행의 좌우측에서는 직전 행에서만 값을 가져오는 것이 아니라 앞선 모든 행에서 가장 최적인 것을 가져오는 방식을 선택했다.

알고리즘은 다음과 같이 동작한다.

  • D[0][i][j]는 입력된 값 A[0][i][j]로 우선 채운다. (해당 지점에서 시작하는 경우)
  • i는 1부터 M – 1까지 반복
    • j는 모든 행을 순차적으로 방문한다.
      • i가 홀수 행이면 진행방향이 오른쪽이므로 자신의 왼쪽에 있는 것 중 최적해를 찾고 그 위치를 기록
      • i가 짝수 행이면 진행방향이 왼쪽이므로 자신의 오른쪽에 있는 것 중 최적해를 찾고 그 위치를 기록
      • 행의 양 끝에서는 위 작업에 추가해서 같은 열의 이전 행들 중에서 최적해를 찾고 그 위치를 기록
    • 현재 D[i][j][k] 중에서 가장 큰 값을 찾아서 i와 j와 k를 기록한다.
  • 반복문 종료 후 최대 i와 j와 k로부터 역추적으로 지나온 경로를 저장하여, 순차적으로 출력한다.
  • 최대 i가 M-1이 아니면 중간에 그만 둔 것이므로 -1, -1을 출력한다.

 

사용 알고리즘

  • 다이나믹 프로그래밍

코드


 

Atcoder Regular Contest 085

I. Introduction

이 포스트에서는 Atcoder.jp 에서 진행된 Regular Contest 085에 대해서 살펴봅니다.

 

II. Solve

[Prob C] – HSI

Takahashi는 현재 프로그래밍 대회에 참가 중이다. 그는 N개의 문제 중에서 M개의 문제를 각각 1900초 만에 1/2의 확률로 해결할 수 있고, 나머지 (N-M)개의 문제를 각각 100초만에 완전히 해결할 수 있다.

그가 대회를 진행하는 과정은 코드를 제출하고, 모든 테스트 케이스를 통과하지 못하면 통과할 때까지 다시 코드를 제출하는 것이다.  N과 M이 주어질 때 Takahashi가 이 문제를 통과하기 위해 걸리는 시간의 기대값을 구하여라.

 

문제 풀이

기본적인 무한 급수 문제이다. 문제의 수가 M개일 때 이 문제를 모두 맞출 수 있는 확률은 {( {1\over 2} )}^M 이다. 이 확률을 r 이라고 한다면, 총 시간의 기댓값

S = \sum_{k=1}^{\infty} {k * (M * 1900 + (N - M) + 100) * (1 - r)^{ k-1 } * r}

= r * (M * 1800 + 100 * N) * \sum_{k=1}^{\infty} {k * (1-r)^{ k-1 }} 이다.

 

S - (1 - r)S =  r * (M * 1800 + 100 * N) * \sum_{k=1}^{\infty} {(1-r)^{ k-1 }}

rS = r * (M * 1800 + 100 * N) * {1 \over {1 - (1 - r)}} 이므로

S = (M * 1800 + 100 * N) * {1 \over r}

을 출력하면 된다.

 

사용 알고리즘

  • 무한 급수

 

코드

 

[Prob D] – HSI

N개의 카드로 이루어진 덱이 있다. 각각의 카드에는 양의 정수 값이 적혀 있다.

두 명의 사람 X와 Y는 이 카드를 가지고 플레이한다. 가장 처음에 X와 Y는 하나의 카드를 들고 게임을 시작하며 각각 들고 있는 숫자는 Z와 W이다. 매 턴마다 플레이어는 현재 들고 있는 카드를 버리고 덱에서 최소 1장에서 원하는 숫자만큼의 카드를 위에서부터 뽑아 가장 마지막으로 뽑은 카드를 손에 쥔다.

모든 카드가 소진되면 게임은 종료되며 이 때 두 플레이어가 들고 있는 카드의 숫자 차이의 절댓값이 게임의 스코어가 된다. X의 목표는 스코어를 최대화하는 것이고, Y의 목표는 스코어를 최소화하는 것이다. 두 플레이어가 최적의 방식을 따른다고 할 때 게임의 스코어를 구하여라.

 

문제 풀이

선을 쥐고 있는 것이 X이므로 X의 입장에서 생각해보자.

  • X가 첫 턴에서 모든 카드를 다 뽑아버린다면 게임 스코어는 | D_n - W | 이다.
  • X가 첫 턴에서 하나의 카드만 남겨버린다면 게임 스코어는 | D_{n-1} - D_n | 이다.
  • X가 첫 턴에서 하나 이상의 카드를 남긴다면 위의 두 경우보다 큰 차이를 낼 수 있기 때문이다. 이 경우 Y는 이런 시나리오를 피하기 위해서 하나의 카드만 남겨버릴 수 있다. 이 경우 게임 스코어는 두 번째 경우와 동일한 | D_{n-1} - D_n | 이다.

따라서 게임은 X의 선택에 따라서 결정되는 것과 같으며 두 값 중 최댓값을 출력하면 끝이다.

 

사용 알고리즘

  • 게임이론