[ICPC 본선 대비 뇌셋] Day 15

백준 18753번 Alternative Accounts www.acmicpc.net/problem/18753

18753번: Alternative Accounts

k를 하나씩 늘려가다보면 벤다이어그램을 그려볼 생각을 할 수 있다.

[관찰 1] 벤다이어그램에서 같은 contest에 속한 계정은 다른 오너가 운영해야한다.

관찰 1로부터 k<=3일때까지는 어렵지 않게 생각할 수 있고, 이로부터 k = 4도 비슷하게 생각하면 된다.

[풀이] $A \cap B \cap C \cap D$인 영역은 다른 영역에 있는 것과 같이 있을 수 없다.

$A \cap B \cap C$인 영역은 D영역에 있는 것과만 같이 있을 수 있다.

따라서 $ans+=A \cap B \cap C$, $D-=min(D, $A \cap B \cap C$)를 해준다. 나머지 3개의 교집합에 대해서도 같은 것을 해준다.

두 교집합일 경우가 까다로운데, AB - CD를 연결하는 것이 AB-C-D를 연결하는 것보다 좋거나 같음을 쉽게 증명할 수 있다. 따라서 AB - CD, AC - BD, AD - BC의 연결을 먼저 지워주고, 남은 교집합을 AB - C - D, ...등의 연결을 지워준다.

마지막으로 $ans+=max(A, B, C, D)$을 해주면 끝.

비트연산으로 코딩해주면 어렵지 않게 짤 수 있다.