[Codejam][2020][QR] 4. ESAb ATAd

문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9e

---

B 개의 비트 배열이 있다.

사용자는 1과 B 사이의 비트 위치를 질문하고 해당 위치의 비트를 응답받는다.

이 기계는 1, 11, 21 ... 등 일의 자리가 1인 쿼리 횟수 번째에는 양자 변동을 일으킨다.

즉, 1, 11, 21 .. 번째 질문에는 응답하기 전 양자 변동이 일어난 후 변동의 결과를 기준으로 응답한다.

양자 변동은 1/4의 확률로 아래 4가지 중 하나가 발생한다.

1. 모든 0은 1로, 1은 0으로 변환.

2. 배열의 위치가 반전된다. ex) 1번째 비트는 마지막 비트와 교체. 2번째 비트는 마지막에서 2번째 비트와 교체. 반복

3. 1, 2가 둘 다 발생. (모든 0은 1, 1은 0으로 변환된 뒤 반전된다.)

4. 아무 변화 없다.

응답하는 위치에 전체 배열을 찾아라. (이때동안 발생한 양자 변동으로 변화된 비트의 전체 배열)

응답은 질문으로 치지 않으므로 양자 변동은 발생하지 않는다.

---

양자 변동 중 1, 2를 각자 판단해서 이때까지 구한 배열을 변환하면 3, 4를 같이 실행할 수 있다.

즉, 1, 2가 각자 판단 후 둘 다 실행된다면 3. 둘 다 실행되지 않으면 4.

 

인덱스를 1부터 질문하는데(배열 인덱스는 0부터 시작이지만 문제에서는 1부터 시작이라 하였으므로 설명도 인덱스를 1부터 시작으로 가정한다.), 질문 후 마지막비트인덱스-1도 같이 물어서 인덱스를 데칼코마니 식으로 질문을 해나간다.

그리고 비트가 다른 경우와 같은 경우의 인덱스도 저장해둔다.

예를 들어 비트 배열이 1011 일 때, 비트가 같은 인덱스는 1, 다른 인덱스는 2가 저장된다.

 

1, 11, 21... 번째 질문에는 양자 변환이 발생하므로 0(배열 세팅이 안되었으므로 이 경우는 패스), 10, 20, ... 질문 후 양자변환된 배열 세팅을 한다. 이 경우 2번의 질문이 소요된다. (양자 변동 1, 2를 판단하기 위해 각자 1번씩 질문함)

 

양자 변동 중 1번(0 -> 1, 1 -> 0)을 판단하기 위해서 비트가 같은 경우의 인덱스를 이용한다.

array[i] == array[last-i] 가 같기 때문에 배열의 위치가 반전(2)된다고 하더라도 배열의 값은 같다. 만약 값이 달라진다면 이는 양자 변동 중 1번이 발생했기 때문이다.

따라서, 같은 비트를 가진 인덱스의 비트를 질문하고 응답 받은 비트와 이전에 저장한 비트가 다르다면 양자 변동 1번이 발생했다는 뜻이므로 배열을 탐색하면서 0 -> 1, 1 -> 0으로 변환한다.

 

양자 변동 중 2번(위치 반전)을 판단하기 위해 비트가 다른 경우의 인덱스를 이용한다.

이전에 비트 값 반전을 했기 때문에 위치에 대한 고려만 하면 된다.

다른 비트를 가진 인덱스의 비트를 질문하고 응답 받은 비트와 이전에 저장해 두었던 비트가 다르다면 양자 변동 2번이 발생했다는 뜻이므로 1~2/b를 탐색하면서 array[i] <-> arr[b-i]를 교환한다.

 

양자 변환 후 비트 배열 결과를 구하기 위해 2번의 질문이 소요되고 데칼코마니 식으로 배열을 채워나가므로(한 번에 2개의 인덱스 질문을 한다.) 탐색 중인 인덱스 % 4가 0인 경우 양자 변환의 결과를 판단한다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/2020/QR/4.%20ESAb%20ATAd.cpp