TopCoder SRM 726 Div.2

I. Introduction

이 포스트에서는 Topcoder.com 에서 진행된 Single Round Match 726 Div.2에 대해서 살펴봅니다.

  • 문제 수 : 3개
  • 진행 시간 : 1시간 15분
  • 레이팅 구간 : 레이팅 반영
  • 대회 링크 : https://community.topcoder.com/stat?c=round_overview&er=5&rd=17048

 

II. Solve

[Prob A] – StringHaving

문자열 s가 있다. 이 문자열에는 a-z의 소문자로 구성되어 있는데 이 문자열에 포함된 소문자는 반드시 2개 존재하거나 아예없다. 이제 문자열을 반으로 줄이려는 시행을 하는데 제한 조건은 동일한 소문자 2개 중 하나만 없앨 수 있다는 것이다. 즉, bbaa가 있다면 b와 a를 하나씩만 없앨 수 있다는 말이다. 이 시행을  거쳐 만들어지는 문자열의 맨 첫 번째 문자가 가장 작도록 하는 것이 이 문제의 목표이다.

 

문제 풀이

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

배열 L은 문자열 s에서 각 소문자가 처음으로 등장하는 인덱스다. 배열 R은 문자열 r에서 각 소문자가 처음으로 등장하는 인덱스다.

어떤 소문자 c가 s를 변형한 s2에서 가장 앞에 있기 위한 조건은 소문자 c의 첫 등장 위치가 len(s) / 2 보다 작아야하고, c 앞에 동일한 소문자가 2번 등장하면 안된다는 것이다. 즉, 다음과 같이 조건을 정리할 수 있다.

  • 문자가 문자열에 존재할 것 L[i] != -1
  • 문자의 첫 등장 앞에 다른 문자의 두 번째 등장이 없을 것 L[i] < Min(R only R[j] != -1)
  • 문자의 첫 등장 위치가 문자열의 중앙 기준으로 왼쪽일 때 L[i] < len(s) / 2

 

코드


 

[Prob B] – TurtleGame

1×1의 격자로 구성된 직사각형 게임판이 있다. 거북이를 게임판의 왼쪽 최상단에 놓아 오른쪽 최하단으로 움직이게 하려고 한다. 여기서 거북이는 오른쪽과 아래로의 이동만 가능하다. Hero와 Jack은 Hero를 선으로 시작해서 매 턴마다 보드에서 격자를 하나씩 제거한다. 격자를 제거한 후에도 왼쪽 최상단으로부터 오른쪽 최하단으로의 경로는 최소 하나가 존재해야하며, 이 시행을 할 수 없는 사람이 게임의 패자가 된다. 둘 다 최적으로 플레이 할 때 누가 승자가 되겠는가?

 

문제 풀이

O(NM)의 시간 복잡도로 해결할 수 있다. (N 가로, M은 세로)

둘 다 최적으로 플레이 한다는 가정에서는 마지막 남은 하나의 경로에 속한 격자를 건드리는 쪽이 패배한다. 거북이의 이동 제약 조건에 의해 모든 경로는 동일한 수의 격자 (N + M – 1)를 가지게 되는 것이 해결의 핵심이다.

초기 상태에서 이동 가능한 모든 격자의 수를 tileCnt라고 한다면 최적의 플레이에서 최종적으로 (N + M – 1)개의 격자만 남을 것이고 그 때까지 턴은 총 tileCnt – (N + M – 1)번 수행된다. 사실 어떤 식으로 플레이하든지 1개의 최종 경로만을 남기는 쪽으로 진행하면 이 턴의 수는 절대 변할 수 없다. 이 값이 홀수이면 선을 잡은 Hero가 승리하고 짝수라면 Jack이 승리하게 된다.

 

코드


 

[Prob C] – HeroicScheduled2

N개의 작업이 존재하며 두 개의 배열 start와 finish가 주어진다. start[i]는 작업 i에 착수할 수 있는 가장 빠른 날, finish[i]는 작업 i에 착수할 수 있는 가장 마지막 날이다. 모든 작업을 끝내는 데에는 하루가 소요되며, 하루에 하나의 작업만 수행할 수 있다.

작업과 날짜를 매칭한다고 할 때 가능한 모든 경우의 수를 구하는 것이 문제의 목표다. 작업과 날짜는 최적으로 매칭될 필요가 없으며, 아예 작업을 하나도 하지 않는 것 또한 경우의 수에 포함될 수 있다.

 

문제 풀이

문제의 데이터 크기가 힌트로 작용한다. N <= 50 이고 start와 finish의 값 M은 0 <= M <= 15 이다.

문제에서 구하는 것은 완료된 작업 집합 A를 원소로하는 집합 B의 크기로, 작업 순서는 경우의 수와 상관없다.

이 문제는 DP를 통로 DP[N][1 << max(M)]의 배열로 비트마스크를 사용한다.

점화식의 핵심은 다음과 같다. k = 1 << 작업 날짜라고 할 때.

  • DP[i][j] = DP[i – 1][j]
  • DP[i][j] += DP[i – 1][j ^ k] (j의 해당 날짜 비트가 1이며, 아직 DP[i – 1][j ^ k]가 참조되지 않은 경우)

 

DP[ i ][ j ]의 유지 조건은 중복된 작업 상태를 담지 않는다는 것이다. DP[ i + 1 ][ j ]를 구할 때 처음 가져오는 DP[ i ][ j ]는 i + 1을 세트에 포함하지 않는 경우이며, 그 후에 참조되는 DP[ i ][ j ]는 i + 1을 세트에 포함하는 D[ i ][ j || 2^k] 에 의해 참조되는 것으로 둘은 서로 다른 집합을 구성한다.

데이터는 finish의 오름차순으로 정렬시키는 것은 그 이유를 사실 잘 모르겠지만, 느낌으로는 하나의 세트가 여러가지 순서로 조합이 가능할 때 그 가능한 배치 중 각 작업이 최대한 빠르게 배치된 것만 센다면 순서 중복을 제거한 세트와 같으므로 이 조건을 준 것 같다. 중복이 되었다면 리턴 값이 더 커져야하는데 SRM 테스트 예제에서는 더 작게 나와서 이건 좀 더 생각을 해봐야할 것 같다.

 

코드

 

 

Leave a Reply

Next ArticleC++ STL next_permutation