Google Code jam Round 1C 2019 후기

안녕하세요. 

Round 1C 2019 후기 간단히 올려 봅니다. 추가 설명이 필요하시면 답변 부탁드립니다~

Round 2로 진출한 상황이어서 시험 종료 후에 풀어봤습니다.

문제는 세 문제였습니다. 

 

ㅁ 1번 (Robot Programming Strategy)

Greedy로 Test set 1 / 2 모두 해결 가능합니다.

나는 나를를 제외한 모든 Robot을 이겨야 합니다. (이유: 첫번째 tournament에서 나는 모든 Robot과 겨룰수 있으므로)

현재 위치를 p라고 합시다. (0부터 시작, 예를들어 Robot 1이 "RSP"이고 p=1이면 'S'를 나타냄. p=5이면 5%3(3=len("RSP") = 2이기 때문에 'P'를 나타냄)

p위치의 나를 제외한 모든 robot의 값은 다음과 같은 경우로 나뉩니다.

1) 하나의 값만 존재. 예를들어 모든 robot의 값이 'P'인 경우 나는 'S'를 내면 이깁니다. 즉, 내가 이기는 경우는 항상 있기때문에 내가 이기게 되고 현재까지의 값을 출력해 주면 됩니다.

2) 두개의 값이 존재. 예를들어 모든 robot의 값이 'R','P'인 경우 나는 'P'를 내면 되고 'R'인 robot은 지기 때문에 제외 하고 계속 진행하면 됩니다. 즉, 두개의 값중에서 이기는 경우를 나는 내면 되고, 지는 Robot을 제외한 채로 계속 진행하면 됩니다.

3) 세개의 값이 존재. 예를들어 모든 robot의 값이 'R','P','S'인 경우 나는 어떤값을 내더라도 나를 이기는 robot은 존재하기 때문에 나는 지게 됩니다. 즉, IMPOSSIBLE을 출력하면 됩니다.

Robot중에서 string길이가 가장 긴 길이만큼 실행해도 이기는 경우가 없을 경우 IMPOSSIBLE을 출력하면 됩니다.

 

ㅁ 2번 (Power Arrangers)

Interactive Problem입니다.

총 5개의 문자(A,B,C,D,E) 이고 5개의 문자를 나열하는 모든 경우중에 빠진 1가지만 찾는 문제입니다.

5개의 문자를 나열하는 경우의 수는 5!=120이고 1가지가 빠졌기 때문에 119가지가 존재합니다.

119*5개문자 = 595이기 때문에 문제에서 허용하는 F (475 / 150) 이내에 답을 찾을수 없다.

문제의 핵심은 첫번째 빠진 문자를 찾은후 두번째 문자를 찾을때에는 첫번째 문자중에 빠지지 않은 경우는 제외하면 search횟수를 많이 줄일수 있다. 예를들어서, 정답이 ABCDE인 경우 첫번째 119개 string중에 첫번째 문자의 갯수는 A=23, B~E=24가 된다. 두번째 문자 B를 찾을 경우 첫번째 문자가 B~E인 string은 제외 시키면 search횟수를 많이 줄일수 있다. 이런 방식을 할 경우 search 횟수는 첫번째 문자는 119번(5!-1), 두번째 문자는 23번(4!-1), 세번째 문자는 5번(3!-1), 네번째 문자는 1번(2!-1), 다섯번째 문자는 0번(네개의 문자를 알면 마지막 문자는 알수있음). 총 148번에 해결가능하기 때문에 Test Set 1 / 2 모두 해결가능하다

 

ㅁ 3번 Test Set 1 (Bacterial Tactics)

winning opening moves의 갯수를 구하는 문제입니다. 즉, Becca 가 이기는 첫번째 moves의 갯수를 구하면 됩니다.

전체 탐색으로 풀었습니다. 모든 opening move(2*(R+C)) 에 대해서 Becca가 이기는지 확인해 봅니다.

Becca가 이기는지 확인하는 방법도 전체 탐색으로 진행합니다. 즉, 현재 empty인 공간에 Bacteria를 설치합니다.(Horizontal / Vertical) 현재 선택 가능한 방법의 수는 (R+C) * 2 (2: Horizontal + Vertical)가 됩니다.

따라서, 시간복잡도는 O(2*(R+C) * (2*(R+C))!) = O(16*16!) 입니다. big O 시간 복잡도는 크지만 실제 시간복잡도는 크지 않은것 같습니다. (한번 play할때 선택되는 cell이 많고, radioactive material가 있어서 경우의 수가 줄어드는것 같습니다)

 

부족한글 읽어 주셔서 감사드립니다.

Code jam 참여자 여러분, 모두 화이팅 하세요!