Game with Dominoes

• 도미노의 높이가 h인 상황을 생각하자. 거리가 h이상 떨어져 있는 도미노들은 서로 영향을 주지 못한다. 거리가 h미만인 도미노들을 그룹으로 묶으면 자기턴에 할 수 있는 일은, 그룹 하나를 고르고 그 그룹에서 원하는 개수만큼의 도미노를 넘어뜨리는 것이다. 결국 도미노 그룹이 돌무더기와 대응되는 님게임과 동일한 게임이 된다.
• 님게임과 동일하므로, h가 고정되어 있으면 승패는 xor sum이 0인지를 체크하는 식으로 간단히 알수 있다. 문제에서는 xor sum이 0이 되는 h의 최솟값을 찾아야 한다. h를 증가시켜 나가면서 그룹의 상태를 계산하면, x가 어떤 인접한 도미노간의 간격보다 커지는 순간만 그룹의 상태가 바뀌게 되므로, 인접한 도미노들의 간격을 모두 모아서, 거기에 해당하는 h값들에 대해서만 그룹을 업데이트하고 xor sum을 구해주면 된다.
• 도미노들을 위치를 기준으로 정렬한 다음, h = a[i+1] - a[i] 이 되었을때 i+1 번과 i번 도미노를 같은 그룹으로 합치는 것은, 디스조인트 셋을 이용해서 처리하면 된다. 그룹으로 합친 뒤에 xor sum을 계산하는 것은, 처음부터 다시 계산할 필요 없이, 이전에 구한 sum에서 i번 그룹과 i+1번 그룹의 값을 제외하고, 대신 합쳐진 그룹의 값을 추가해주면 된다. 다시말해, grundy = grundy ^ size(i) ^ size(i+1) ^ (size(i)+size(i+1)) 과 같이 업데이트 해주면, 업데이트를 전부 O(1)에 할 수 있다.
• h값의 후보는 n개이고, 각각에 대해서 O(1)에 업데이트를 해주면 되므로 이 과정의 시간복잡도는 O(n)이다. 전처리 과정에서 n을 정렬하는데에 O(nlogn)이 걸리므로 총 시간복잡도는 O(nlogn)이다
• 헷갈리기 쉬운 부분은, h가 간격보다 커야만 그룹으로 합칠 수 있다는 부분이다. 사실 문제에서는 h가 정수여야만 한다는 조건이 주어지지 않았기 때문에, i와 i+1이 합쳐지는 순간 xor sum이 0이 된다고 하면, 이론적으로는 답은 a[i+1]-a[i] 보다 큰 수 중 최솟값이 되어 정의될수 없다.. 하지만 알아서 정수라고 찰떡같이 알아듣고, 간격+1 을 답으로 적으면 통과된다
• 그 외에도 답이 h_min 이 되는 경우를 처리하는 데에도 실수할 여지가 있으므로, 잘 신경쓸 필요가 있다

"""Solution code for "BOJ 23540. Game with Dominoes".

- Problem link: https://www.acmicpc.net/problem/23540
- Solution link: http://www.teferi.net/ps/problems/boj/23540

Tags: [game theory]
"""

import collections
import itertools
from teflib import disjointset


def main():
    n, h_min, h_max = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    dsu = disjointset.DisjointSet(n)
    inds_by_dist = collections.defaultdict(list)
    grundy = n % 2
    for i, (l, r) in enumerate(itertools.pairwise(sorted(a))):
        if r - l < h_min:
            s1, s2 = dsu.size(i), dsu.size(i + 1)
            grundy ^= s1 ^ s2 ^ (s1 + s2)
            dsu.union(i, i + 1)
        elif r - l < h_max:
            inds_by_dist[r - l].append(i)
    if grundy == 0:
        print(h_min)
        return

    answer = -1
    for h, inds in sorted(inds_by_dist.items()):
        for i in inds:
            s1, s2 = dsu.size(i), dsu.size(i + 1)
            grundy ^= s1 ^ s2 ^ (s1 + s2)
            dsu.union(i, i + 1)
        if grundy == 0:
            answer = h + 1
            break

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet