Codeforces Round #832 (Div. 2)

Dashboard - Codeforces Round #832 (Div. 2) - Codeforces

 

간만의 코드포스 포스팅이다. 내가 잘해서 올리는 게 맞다.

 

Prob. A

뭔가 그리디한 전략이 잘 안 먹혀서 사실 그룹을 나눌 필요가 없는 게 아닌가 싶었고, 그래서 배열의 합의 절댓값을 출력하도록 했더니 맞았다. 신기하다.

 

Prob. B

작을 때 해보니까 B, N을 끝에서부터 스왑해주면 되겠다 싶었다.

 

Prob. C

작을 때 해보니까 Alice가 계속 $a_1$만 건들게 되길래, '그럼 Bob도 나머지 중 가장 작은 것만 건들게 되지 않을까?'라는 추측을 했고 맞았다. 구체적인 전략은 생각 안 해봤다.

 

Prob. D

일단 구간의 왼쪽부터 값을 0으로 만들어준다고 생각해보자. 잘 생각해보면, 가장 왼쪽 원소를 포함하도록 XOR을 두 번 이상 취하는 것은 그 중 가장 긴 연산을 한 번 한 것과 상황이 같다는 것을 알 수 있다. 따라서 XOR을 취하는 구간이 겹치는 것은 최적이 아니다. 그럼 전체 구간의 XOR이 0이 아니면 불가능하다는 것도 알 수 있다.

이제 전체 구간의 XOR이 0인 상황만 고려하자. 구간의 길이가 홀수라면 연산 한 번으로 끝난다. 구간의 길이가 짝수라면 중간에 적당히 끊어서 양쪽의 XOR이 각각 0이고 길이가 홀수이도록 만들 수 있어야 한다. 이는 map< [1, i]의 XOR 값, i들의 벡터 > 를 i의 홀짝에 따라 두 개 만들어주고 여기서 이분탐색하는 것으로 해결할 수 있다. 마지막으로, 구간의 길이가 짝수이고 구간의 양 끝 원소 중 하나가 0인 경우를 따로 처리해줘야 함에 주의하자.