B2. Palindrome Game (hard version) #721 Div.2

https://codeforces.com/contest/1527/problem/B2
시간 1초, 메모리 256MB

input :

• t (1≤t≤103)
• n (1≤n≤103)
• string s of length n

output :

• For each test case print a single word in a new line:
  "ALICE", if Alice will win the game,
  "BOB", if Bob will win the game,
  "DRAW", if the game ends in a draw.
  

각 테스트 케이스에서 아래의 단어 중 하나를 출력한다.
Alic가 이겼을 경우 "ALICE", Bob이 이겼을 경우 "BOB", 비겼을 경우 "DRAW"를 출력하시오.

조건 :

• Both players take alternate turns with Alice going first.
  플레이어들은 번갈아 가면서 플레이 합니다. 선공은 Alice가 가져갑니다.

• Choose any i (1≤i≤n), where s[i]= '0' and change s[i] to '1'. Pay 1 dollar.
  1달러를 지불 하고 i지점의 값을 1로 교체합니다.
  

• Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse.
  문자열을 뒤집습니다. 이 조건은 문자열이 palindrome이 아닐 때에만 사용할 수 있습니다. 그리고 상대의 행동이 reverse가 아니여야 합니다.
  

---

하.. 왜 날라가냐... 암튼 팰린드롬인 경우는 이미 B1.에서 확인했다. 인제는 입력받는 문자열이 팰린드롬이 아닐 수 도 있다.

팰린드롬이 아닐 때

이 때는 거의 그냥 Alice가 이긴다. 왜 그러냐? 팰린드롬이 아닐 때는 계속 뒤집을 수 있다.
그렇기에 계속 뒤집으면 Bob이 1을 하나씩 놓으면서 팰린드롬과 가까워질 텐데 그러다가 Alice가 1을 놓으면서 팰린드롬이 되게 만들어 버리면 Bob은 단 한번도 뒤집을 수 없고 계속 수를 놓아야 한다.

무승부?

근데 생각해야 할 경우가 존재한다. 110101111과 같은 문자열의 경우 어떻게 하든 무승부가 발생한다. 저렇게 0이 2개이고 중간에 0이 있을 때말이다.
0이 2개보다 많다면
110001111 일 때 계속 뒤집다가 팰린드롬 되기 전에 1을 놓으면서 팰린드롬으로 만들면 또 똑같은 상황이 연출 된다.

그러니까 팰린드롬인지 확인, 그리고 나서 위의 조건을 확인

import sys

t = int(sys.stdin.readline())
for i in range(t):
  n = int(sys.stdin.readline())
  data = sys.stdin.readline().rstrip()

  zeros = 0
  for item in data:
      if item == '0':
          zeros += 1

  if data == data[::-1]:
      if zeros == 1 or zeros % 2 == 0:
          print("BOB")
      else:
          print("ALICE")
  else:
      if zeros == 2 and len(data) % 2 == 1 and data[len(data) // 2] == '0':
          print("DRAW")
      else:
          print("ALICE")