티스토리 뷰
얼마 전 코포에 비슷한게 나와서 풀어본 문제. 집합 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