ARC100 E. Or Plus Max

문제 링크

\(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)\)의 순서쌍을 들고 다녀야 한다.