BOJ 12975 트라이슬

세 개의 팀 중 하나에 다음 학생을 넣는 것을 반복하는 DP를 생각합니다. 0 이상 255 이하의 정수들의 XOR은 동일한 범위 내에 있으며 각 팀에 적어도 한 명의 학생이 들어갔는지 여부를 추가로 관리해야 하므로, $256^3 \cdot 2^3 \cdot N$의 상태 공간을 갖는 DP를 세울 수 있습니다. 전이할 때는 힘이 $x$인 학생에 대해 팀 1, 팀 2, 팀 3 중 하나에 $x$를 XOR하고 그 팀에 학생이 존재함을 나타내는 비트를 켜주면 됩니다.

여기서 다음의 최적화 중 적어도 하나를 하면 통과합니다.

• 세 개의 팀 중 비어있는 팀이 있을 경우, 그 팀의 힘은 현재 0입니다. 학생이 있는 다른 팀에서 힘이 $x$인 아무 학생을 빼서 비어있는 팀에 옮기면, 기존 팀의 힘은 $x$를 XOR하게 되고 새로운 팀의 힘은 $x$가 되므로, 팀의 힘의 총합은 절대로 손해를 보지 않습니다. 따라서 각 팀에 학생이 존재하는지 여부 체크를 생략할 수 있습니다.
• 1번부터 $i$번 학생까지 처리했다고 하면, 이 $i$명의 전체 XOR는 고정이므로 팀 1과 팀 2의 힘을 알면 팀 3의 힘이 고정됩니다. 따라서 $256^3$에서 차원을 하나 줄일 수 있습니다.