SOS Dynamic Programming

📝 상세 정리

#

• $2^N$개의 정수 배열 $A$가 주어진다. 이때 $\forall x$ 에 대해 $F(x)$를 $\sum\limits_{i \subseteq x}{A[i]}$ 라고 정의하자. 이는 $x\&i = i$ 인 $i$들에 대해 $A[i]$의 합을 의미한다.
• 위와 같은 문제를 어떻게 풀 수있을까?

브루트포스

#

• 느리지만, 다음과 같은 브루트포스로 계산할 수 있겠다.

  for(int mask = 0; mask < (1<<N); mask++){
  	for(int i = 0; i < (1<<N); i++){
  		if((mask&i) == i){
  			F[mask] += A[i];
  		}
  	}
  }

• 위 식을 그대로 옮긴 것에 가깝다.
• 시간복잡도는 ${(2^N)}^2 = 4^N$이다.

조금 더 나은 풀이

#

• 두번째 반복문에 대해, 바깥쪽 반복문에서 켜지지 않은 비트에 대해서도 반복을 도는것은 너무 아깝다.
• 따라서 다음과 같이도 한번 시도해볼 수 있겠다.

  for(int mask = 0; mask < (1<<N); mask++){
  	F[mask] = A[0];
  	for(int i = 0; i < (1<<N); i = (i-1)&mask) F[mask] += A[i];
  }

• 시간복잡도 증명이 어려워보인다.
• 이는 $\sum\limits_{k = 0}^N{\binom{N}{K}2^K} = 3^N$ 이라고 한다.

Sum over Subsets DP

#

• 위의 방식에서 병목은 어디에서 나타날까?
• 어떤 $x$의 비트가 $K$개가 꺼져있을 때, $A[x]$는 $2^K$개의 마스크에 의해 방문된다.
  • 이 반복적인 재계산을 줄여야한다.

S(mask, i) 정의

#

• 위 병목을 피하기 위해 새로운 상태를 하나 정의해보자.
• $S(mask, i)$는 $mask$의 부분집합들 중, $mask$와 하위(오른쪽) $i$개 비트(0~i-1번 인덱스)에서만 다른 것을 의미한다.
• 예를 들어, $S(110, 2) = \{100, 110\}$이다. 오른쪽 두개 비트에서 다를 수 있는데, 부분집합이어야 하므로 $111$같은건 안된다.
• 이 정의를 이용하면, 어떤 집합도 서로 겹치지 않는 $S(mask, i)$들의 합집합으로 나타낼 수 있게 된다.

점화식 유도

#

• 점화식은 다음과 같이 두가지로 정의할 수 있겠다.
• $mask$의 $i$번째 비트가 $0$인 경우
  • $mask$의 부분집합이 $i$번째 비트에서 $0$만을 가질 수 있으므로
  • $S(mask, i) = S(mask, i-1)$
• $mask$의 $i$번째 비트가 $1$인 경우
  • $mask$의 부분집합이 $i$번째 비트에서 $0, 1$ 모두 가질 수 있으므로
  • $S(mask, i) = S(mask, i-1) \cup S(mask \oplus 2^i, i-1)$
• 따라서 이를 코드로 나타내면 다음과 같다.

  for(int mask = 0; mask < (1<<N); mask++) DP[mask] = A[mask];
  
  for(int i = 0; i<N; i++){
  	for(int mask = 0; mask < (1<<N); mask++){
  		if(mask & (1<<i)) DP[mask] += DP[mask ^ (1<<i)];
  	}
  }

• 계산 결과 DP에 들어있는 값은 해당 비트마스킹의 부분집합의 합이다.
• 시간복잡도는 그대로 보이듯이 $O(N2^N)$이다.

N차원 누적합

#

• https://blog.queuedlab.com/posts/sos-dp 를 참고하면, 이를 $N$차원 누적합으로도 해석할 수 있다.
• 하이퍼 수열과 하이퍼 쿼리 문제에서 $N$차원 누적합 아이디어는 써본적이 있었는데, 이것이 SOS DP와 같다는 것이 신기하다.
• 앞으로는 포함배제에서 뭔가 줄이고싶으면 한번씩은 의심해보는걸로?

imos-hanbyul Trick

#

• 이와 비슷한 내용을 https://qwerasdfzxcl.tistory.com/35 여기서 본적이 있다.
• 지금 당장은 이해하기 귀찮으므로 이해한 내용은 나중에 추가하겠다.

❔질문 사항

#

🔗 참고 자료

#

• https://codeforces.com/blog/entry/45223
• https://blog.queuedlab.com/posts/sos-dp
• https://qwerasdfzxcl.tistory.com/35