$A, B, C$와 $k$가 주어질 때, 서로 다른 순서쌍 $(a, b, c)$ ($1 \le a \le A, 1 \le b \le B, 1 \le c \le C$)를 최대한 많이 고르는데, 같은 $(a, b)$, $(b, c)$, $(a, c)$의 조합을 $k$번 이하로만 사용할 수 있다. 예를 들어, $(1, 2, 3)$과 $(1, 2, 2)$를 고르면 $(a=1, b=2)$는 두 번, $(a=1, c=2)$는 한 번 사용한 것이다.

  • 공통 조건
    • 테스트 케이스의 개수 $T \le 100$
    • $1 \le K \le 10$
    • $1 \le A \le B \le C$
  • Small
    • $C \le 3$
  • Large
    • $C \le 10$

Small 풀이

먼저, $C \le K$이면 모든 조합을 고르면 된다는 것을 쉽게 파악할 수 있다. 그렇게 뽑아도 각각의 $(a, b)$ 조합은 $C$번, $(a, c)$ 조합은 $B$번, $(b, c)$ 조합은 $A$번 나오므로 조건을 만족하기 때문이다.

그렇지 않은 경우는 $ABC \le 27$이므로 $2^{27}$가지의 모든 부분집합을 만들어 보고 조건에 맞는지 테스트하는 방법을 생각해볼 수 있다. 이는 1억이 조금 넘는 수이고 각각의 부분집합을 테스트하기 위해서 그 부분집합의 크기만큼의 시간이 추가로 들기 때문에 런타임에 돌리기는 어려워 보인다. 하지만 $1 \le A \le B \le C \le 3$을 만족하는 조합의 개수가 10개밖에 되지 않으므로, 모든 경우를 precomputation하여 제출할 수 있다.

Small을 런타임에 푸는 풀이

$2^{27} \times 27$의 시간을 줄이기 위해 여러 가지 방법을 생각해 볼 수 있다. 먼저 생각나는 것은 원소를 하나씩 추가하면서 어떤 쌍이 등장한 횟수가 $K$를 초과하면 branch cut을 하는 방법인데, 이는 구현을 실수하기 쉽고 생각보다 잘 커팅되지 않는다.

대신에 $2^{27}$가지 방법을 모두 탐색하되 $\times 27$을 제거하는 방법이 존재한다. Gray code를 사용하는 방법인데, 한 번에 원소 하나만을 추가 또는 제거하여 모든 조합을 생성할 수 있으며, 조금 잘 생각하면 하나의 원소를 추가하거나 제거하고 현재의 조합이 조건을 만족하는지를 $\mathcal{O}(1)$에 판별할 수 있다.

AB_count = 2D array of shape (A, B) filled with zeros
AC_count = 2D array of shape (A, C) filled with zeros
BC_count = 2D array of shape (B, C) filled with zeros
Over_K_count = 0
iterate 2^(A * B * C) times:
    using gray code, check if we are adding or deleting a triple (a, b, c)
    if adding (a, b, c):
        AB_count[a][b] += 1
        AC_count[a][c] += 1
        BC_count[b][c] += 1
    else:
        AB_count[a][b] -= 1
        AC_count[a][c] -= 1
        BC_count[b][c] -= 1
    update Over_K_count
    if Over_K_count == 0:
        take the current set as potential answer

이 알고리즘을 러스트로 구현하여 약 1600ms AC를 받았다. $K$가 클 때는 바로 답을 출력하였기 때문에 $2^{27}$ 루프는 두 번만 실행된 것으로 추정된다.

Large 풀이

Large를 풀기 위해서는 새로운 관찰이 필요하다.

서로 다른 $(a, b)$의 쌍은 $AB$가지가 있다. 이들이 각각 최대 $K$번 등장할 수 있으므로 정답의 상한은 $ABK$가 된다. $(a, c)$와 $(b, c)$에 대해 같은 논리를 전개하면 $ACK$와 $BCK$를 얻는데, 문제 조건에 의해 $ABK$가 가장 작다. 또한, 각 트리플이 서로 달라야 하므로 $(a, b)$의 쌍은 $C$번을 초과하여 등장할 수 없고, 따라서 $ABC$ 또한 답의 상한이 된다. 그러므로 상한을 $\min(ABK, ABC) = AB \min(K, C)$로 둘 수 있다.

Small을 먼저 풀었다면 이 상한이 모두 답이 됨을 관찰할 수 있다. 이제 경우를 나누어 최적해가 무엇인지 찾아보자.

  • $C \le K$라면, $ABC$개의 조합을 모두 사용하면 된다. 그 외의 경우 답의 크기는 $ABK$이다.
  • $B \le K < C$이면, $1 \le c \le K$만을 사용하면 $ABK$개의 조합이 만들어지며, 이러면 각 $(a, b)$ 조합은 $K$번, $(a, c)$ 조합은 $B$번, $(b, c)$ 조합은 $A$번 등장하므로 조건을 만족한다.

이제 $K < B$인 경우가 남았다.

$B < C$인 경우에도 예상되는 답의 크기가 같으므로, $C$를 $B$로 줄여서 나오는 답을 그대로 출력하면 된다.

$A = B = C > K$인 경우를 생각해보면, $ABK$개의 트리플을 선택하는데 모든 $(a, b)$, $(a, c)$, $(b, c)$의 쌍이 각각 정확히 $K$번 등장해야 한다. Small의 답을 잘 살펴보면 어느 정도 추측이 가능한데, 이를 만족하는 한 가지 방법은 다음과 같다.

  • 먼저 모든 $(b, c)$의 쌍을 생성한다. 이러한 쌍은 $B^2$개가 있다.
  • $B^2$개의 쌍을 $B$개씩 $B$개의 그룹으로 나누는데, 각 그룹에 속한 모든 $b$와 $c$의 값이 서로 다르도록 한다. $B = 3$이라면 다음과 같은 방법이 있다. (1, 1), (2, 2), (3, 3) / (1, 2), (2, 3), (3, 1) / (1, 3), (2, 1), (3, 2)
  • 이제 각 그룹을 $S_1, S_2, \cdots, S_B$라고 하자. 모든 그룹은 정확히 $K$번 등장해야 한다. 또한, 하나의 $a$를 하나의 그룹과 짝지어서 $B$개의 트리플을 만들면, 그 $a$와 모든 $b$의 쌍, 그리고 그 $a$와 모든 $c$의 쌍이 정확히 한 번씩 추가된다. 이제 각 $a$를 $K$개의 서로 다른 그룹과 짝지으면 해가 완성된다. 이를 달성하는 하나의 방법으로는 $B$개의 그룹을 충분히 반복해서 나열해 놓고, $a = 1, \cdots, A$ 순서대로 앞에서부터 $K$개의 그룹을 할당해주면 된다.

이렇게 하면 $A$가 더 작은 경우에도 모든 조건을 만족하게 된다.