BOJ 28108 - 라이벌
다차원의 구간합은 결국 포함 배제의 원리가 된다.
BOJ 2802도 $3$차원 구간합을 이용하는 문제이므로 풀어보면 좋다.
이 문제는 $6$차원에서 해결을 해야하는데, 문제를 다음과 같이 생각할 수 있다.
$A$가 $B$에서 $B$의 능력치가 하나라도 $A$보다 높다면 $A$는 $B$의 역라이벌이 된다.
하나라도 높다는 경우의 수를 다르게 생각해 하나도 안높은 경우의 수로 여집합을 생각하고 전체의 학생수에서 뺀다고 해보자.
그럼 $B$의 역라이벌 수는 $B$보다 모든 능력치에 대해 같거나 큰 값을 가지는 학생을 전체 학생수에서 뺀 값이 된다.
모든 능력치에 대해 $a[i][j] \coloneqq 7-a[i][j]$ 를 해서 반대로 표현해준다음
$p[a][b][c][d][e][f]$ 를 능력치 $1$은 $1 \sim a$, 능력치 $2$는 $1 \sim b$ $\cdots$ 에 있는 학생의 수라고 하자.
이걸 포함 배제의 원리로 구하면 시간복잡도는 $O(6^6 \cdot 2^6)=O(12^6)$ 이 되고 문제를 해결할 수 있다.
Comments