티스토리 뷰

공부/Problem solving

Subset XOR Maximization

구사과 2016. 10. 9. 22:23

BOJ

SPOJ

얼마 전 코포에 비슷한게 나와서 풀어본 문제. 집합 S가 주어졌을 때 XOR 값을 최대로 하는 부분집합의 XOR 값을 구하는 문제이다.


대부분의 경우에 2^maxbit - 1이 나올 거 같이 생겼지만, 어떠한 비트들이 다른 비트의 값에 종속적이기 때문에 실제로는 그렇지 않다는 것을 알 수 있다.

여기서 약간의 선형대수학 지식을 활용하자. 일단 주어진 수들을 modulo 2에서의 벡터로 생각할 수 있다. 선대에서 보통 이러한 경우가 나오면 row echelon form을 구해서 종속 관계를 추려내는데, 이것도 똑같이 하면 된다.

주어진 수로 이루어진 row echelon form을 구하는 방법은 다음과 같다. 숫자를 하나씩 하나씩 넣어가는데, 각 숫자에 대해서 가장 큰 비트부터 본다. 현재 row echelon form에서 leading entry가 맞는 row가 있으면, XOR을 시킨 후 계속한다. 아니면, 삽입 정렬의 형태로 끼워넣는다.


row echelon form을 통해 basis를 구하면, 그냥 그리디하게 선택해줘도 최적이다.


코드 : https://gist.github.com/koosaga/5063c7b2307d61287ce35a0777147115

'공부 > Problem solving' 카테고리의 다른 글

L-R Maxflow / Circulation Problem  (2) 2016.10.20
유량 관련 알고리즘 증명  (2) 2016.10.14
(Codeforces) Intel Code Challenge Final Round  (0) 2016.10.09
전갈 그래프 판별하기  (0) 2016.10.05
유량 관련 알고리즘 정리  (10) 2016.10.03
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday