Google Code Jam: Qualification Round 2020

코드잼이 돌아왔다는 뜻은 나의 CP 커리어가 만 1년이 되었다는 뜻이다 ㅎㅎ

QF 라운드 링크이다.

---

1. Vestigium

구현 문제이다.

---

2. Nesting Depth

구현 문제까지는 아니지만 거의 시키는대로 괄호를 열고 닫고 하면 끝난다. $O(n)$ 풀이.

---

3. Parenting Partnering Returns

Worker 2명 스케줄링 문제. 그리디 문제로 유명한 well-known이다.

---

4. ESAb ATAd

여기서부터는 머리를 좀 썼다. 일정한 규칙으로 변화하는 길이 100의 이진문자열의 현재 상태를 맞추면 끝난다. 제한 조건은 쿼리 150번 이내이다.

 

쿼리란: index를 물어보면, index의 값을 알려준다.

변화의 규칙은: 쿼리 10번마다 네개의 변화 방법 중 하나가 랜덤하게 일어난다.

네개의 변화 방법은: 1. 아무 변화도 일어나지 않는다. 2. 이진문자열의 좌우 반전이 일어난다. 3. 이진문자열이 invert된다. 4. 이진문자열이 좌우 반전된 후 invert된다.

 

어떻게 하면 좌우 반전이 랜덤하게 일어나는 와중에도 중복 없이 모든 100개의 칸을 열람할 수 있을 지 생각해 본 결과, 문자열의 양쪽 끝에서 각각 5개씩, 총 10개씩을 확인하며 안쪽으로 들어가면 된다는 결론을 얻었다. 쿼리는 총 100번 날린다.

 

이렇게 100개의 칸을 전부 다 확인한 이후, 지금까지 파악한 정보가 무엇인지 한번 생각해 보았다. 조금 생각해 본다면, 10번에 걸쳐 확인한 각 '껍질'이 독립적인 것처럼 각각 4개의 상태 중 하나에 있음을 알 수 있다. 그렇다면 다음 목표는 '현재' 각 껍질이 어떤 상태에 있는지 확인하는 것이다.

 

각 껍질의 현재 상태는 두번의 쿼리만으로 확인이 가능하다(조금 생각해 본다면 각 껍질의 첫째 자리에 있는 값은 0인 경우 두개, 1인 경우 두개이다. 이후 두가지 경우 중 하나로 좁히는 것은 쿼리 하나로 가능하다.). 그렇다면 문자열이 다시 변화하기 전에 총 다섯 껍질의 상태를 확인해 특정할 수 있다. 이렇게 확인한 다섯 껍질은 이제 독립적으로 각각 네 상태로 변화하는 것이 아니라, 전체가 함께 네 상태 중 하나로 있게 된다. 10번의 쿼리를 썼다.

 

그렇다면 남은 다섯 껍질도 특정해준다. 쿼리 10번.

 

마지막으로, 바로 전 단계에서 형성한 '다섯 껍질의 묶음' 두개를 각각 쿼리 두번으로 결정해준다. 쿼리 4번.

 

이제 출력만 하면 문제 해결 완료다. 총 124번의 쿼리를 사용했다.

---

5. Indicium

어려워 보여서 읽기만 했다.

대회 종료 후 Analysis를 보니 역시 어렵다 ㅎ

---

총평

풀 수 있는 만큼 풀었다. 목표는 Round 3!