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