주사위와 합

세 수를 정렬한 결과를 $x\leq y\leq z$라 하면, 차이의 합은 $(y-x)+(z-x)+(z-y)=2(z-x)$이다. 따라서 $K$가 홀수이면 정답은 $0$이다. $K=0$이면 세 수가 모두 같아야 하므로 정답은 $N$이다.

나머지 경우에는 $d=K/2>0$이라 하자. $d\geq N$이면 가능한 삼중쌍은 없다. $d<N$이면 최솟값 $x$는 부터 까지이고 최댓값은 이다. 중간값이 두 끝값과 다르면 개의 선택과 각각 개의 순열이 있다. 중간값이 최솟값 또는 최댓값과 같으면 각각 개의 순열이 있다. 따라서 최솟값 하나당 개이고, 정답은 이다.

서브태스크 1에서는 모든 $(a_1,a_2,a_3)$을 직접 열거한다. 시간복잡도는 $O({}^{}$, 추가 공간복잡도는 이다. 서브태스크 2에서는 위 공식을 사용한다. 시간복잡도와 추가 공간복잡도는 모두 이다.

$6d(N-d)\leq 6\lfloor N^2/4\rfloor\leq 1\,500\,000\,000\,000\,000\,000$이다. 정답과 곱셈 중간값은 부호 있는 64비트 정수로 계산할 수 있다. 32비트 정수나 부동소수점으로 곱셈하지 않도록 주의한다.

Solution written by GPT