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을 출력한다.

 

사용 알고리즘

  • 다이나믹 프로그래밍

코드


 

Leave a Reply

Next Article2017년 11월 27일 월요일 [D - 4]