ARC100 E. Or Plus Max

2018. 10. 4. 15:58알고리즘 문풀/AtCoder 연습

문제 링크


\(1 \le N \le 18\)에 대해 길이 \(2^{N}\)의 정수 배열이 주어진다. (0 - based) 이 때, 모든 \(1 \le K \le 2^{N}-1\)에 대해 다음을 구하라. \(|\)는 bitwise-or이다.


$$ \max_{i < j, \ i \ | \ j \le K} \left(A_{i} + A_{j}\right) $$


Spoiler Alert!

























\(i | j \le K\)는 도저히 답이 안 나온다. 다행히 \(i | j\)의 모든 비트가 \(K\)의 비트에 포함되는 경우만 고려해도 충분하다. K-1일 때의 답과 max를 취해주면 되니까.


모든 i에 대해서 다음과 같은 f(i)가 있으면 좋을 것 같다 : 

f(i) : i에 포함되는 비트를 가진 인덱스(Bit - Subset)들 중 (인덱스가 겹치지 않게) 가장 큰 2개의 값.


\(f(0) = (A_{0},0)\)으로 두고, 

i에서 비트를 하나씩 뺀 \(O(n)\)개의 수들의 f(j) 값 \(O(2n)\)개와 \(A_i\)를 모두 모아서 가장 큰 2개의 값만 부모로 올리면 된다. 이는 dfs로 간단하게 구현할 수 있고, 수 하나당 참조하는 수가 최대 \(2n+1\)개이므로 시간복잡도는 \(O(n2^{n})\)이다. 인덱스끼리 겹치지 않도록 \((A_i,i)\)의 순서쌍을 들고 다녀야 한다.


'알고리즘 문풀 > AtCoder 연습' 카테고리의 다른 글

ARC098 E. Range Minimum Queries  (3) 2018.10.15
ARC100 E. Or Plus Max  (0) 2018.10.04
ARC099 E Independence & 재밌는 완전그래프 문제들  (2) 2018.09.29
180921 ARC CD밀기 #003  (0) 2018.09.21
180919 ARC CD밀기 #002  (0) 2018.09.19
180914 ARC CD밀기 #001  (0) 2018.09.15
1 2 3 4 5 6