Google Kickstart 2019 Round B

소스 코드 위치: Google Kickstart 2019 Round B

A. Building Palindromes

  쿼리 (L, R) 마다 L과 R 사이에 있는 문자들을 재배열하여 팰린드롬을 만들 수 있는지를 묻는 문제다. 사용되는 문자가 26밖에 없으므로 prefix array를 정의하여 L과 R 사이의 i번째 문자가 출현하는 수가 홀수면 1, 짝수면 0으로 두고 이러한 홀수의 수가 2 이상이면 팰린드롬을 구성할 수 없다고 계산하면 된다.

B. Energy Stones

  [시간] 모든 에너지 스톤을 먹었을 때 가능한 가장 긴 시간은 10000까지다.

  [Lossless] L이 0인 에너지 스톤은 L이 1 이상인 스톤을 모두 먹고난 뒤 처리하는 것이 이득이다.

  [Ordering] L > 0인 에너지 스톤만 가져오자.

  i번째 에너지 스톤과 j번째 에너지 스톤을 생각해보자. 누굴 먼저 먹어야 하는지 결정해보자. i번째 스톤을 먹고나면 j번째는 E[j]-L[j]*S[i]만큼 에너지가 남는다. 반대로 j번째 스톤을 먹고나면 i번째는 E[i] - L[i] * S[j]만큼 에너지가 남는다. 여기서 변화량만 보자. E배열은 볼 필요가 없어지는데, 그 이유는 x번째 스톤을 먹음으로써 손해보는 에너지의 양을 기준으로 누굴 먼저 먹으면 되는지를 결정하기만 하면 되기 때문이다.

  변화량은 각각 L[j]*S[i], L[i]*S[j]가 되는데, 앞서 말했듯 손해보는 에너지양이 적은 쪽을 먼저 먹으면 된다. 따라서 L[j]*S[i] < L[i]*S[j]을 조건으로 i번째, j번째 중 누굴 먼저 먹는 것이 이득일 수 있는지를 정렬한다.

  [Dynamic programming]

  손해가 적다고 무조건 먹는 것이 반드시 최적은 아니다. 정렬은 한 것은 단순히 손해가 적은 기준으로 순서대로 보기 위함이기에 앞에서부터 먹는 것이 최적이 아닐 수 있다.

  시간이 최대 10000까지, N의 최대가 100이므로 dp[10001][100]으로 dp[t][p] ="t 시각에 p번째 에너지 스톤을 먹을지 말지를 결정할 때의 최대값"으로 상태 설정해서 진행하면 된다.

C. Diverse Subarray

  주어진 A 배열에서 i번째 카드를 취득하는 경우 얻거나 잃게되는 카드의 변화값으로 변형해보자. 변형된 배열을 B라고 하자.

1번 예제에서 A배열은 다음과 같다.

A : 1 1 4 1 4 4

  그러면 B배열은 다음처럼 계산된다.

B: 1 1 1 -2 1 -2

  여기서 첫 번째를 반드시 사용한다는 전제가 있어야 한다. 이 때 최대값은 첫 번째를 반드시 포함해야하므로 첫 번째를 포함하는 구간 중 가장 큰 값을 가져오면된다. 이를 다르게 말하면 prefix의 최대값을 가져온다고 생각하면 된다.

  그러면 두 번째를 반드시 포함하는 구간은 어떻게 계산해야할까? 첫 번째를 제거한 뒤의 B배열을 가져오면 되지 않을까 ? 그러기 위해서는 첫 번째에 해당하는 카드(A[1]=c)를 제거함으로써 발생하는 이벤트는 다음과 같다.

  1. B[1] = 0으로 세팅한다. 

  2. c로 표현된 S번째 카드의 인덱스를 j라고 하면 B[j] = 1로 세팅한다.

  3. c로 표현된 S+1번째 카드의 인덱스를 k라고 B[k] = -S로 세팅한다.

1.은 카드를 제거함으로써 발생한다.

2.는 카드 S개까지는 ok이므로 c로 표현된 카드 중 S번째 카드는 취득할 수 있는 상태로 변경한다.

3.은 카드 S+1개부터는 가져갈 수 없으므로 잃는 카드 수는 -S가 된다.

 

  위 과정을 거치고 나면 B배열은 다음처럼 변경된다.

B: 0 1 1 1 1 -2

  두 번째 카드를 반드시 취득하는 상태에서 prefix 최대값을 가져오면 된다.

구현은 세그먼트 트리를 변형해서 구현할 수 있겠다. 나는 구간합과 prefix 최대값으로 트리 두 개를 운용하여 구현했다.