27696. Quite the cheater! (Unrated -> Platinum V)

평균 $\mu$와 분산 $v$가 주어진다. 데이터의 개수 $n$과 $n$개의 데이터 값 $a_1, a_2, \cdots, a_n$을 잘 골라서 주어진 평균과 분산을 갖게 하면 된다.

  • 테스트 케이스의 개수 $t \le 100$
  • 입력 제한: $-10^6 \le \mu \le 10^6$, $0 \le v \le 10^9$
  • 출력 제한: $10 \le n \le 1000$, $-10^9 \le a_i \le 10^9$
  • 모든 입력과 출력 값은 정수

문제의 단순화

아이디어 1

평균은 별로 상관이 없다. 평균이 정수이므로, 평균을 0으로 하는 데이터를 만든 다음 모든 데이터에 $\mu$를 더해 주면 올바른 답이 된다.

$v$의 범위와 $a_i$의 범위에서 잠깐 흠칫할 수 있는데, 잘 생각해보면 $v$는 편차의 제곱의 합이므로 $|a_i|$가 그렇게 커질 수 없음을 알 수 있다.

아이디어 2

이제 평균을 0으로 유지하면서 제곱합이 $nv$가 되게 하면 된다. 평균이 0이므로 편차의 제곱은 그냥 $a_i$ 각각의 값이 된다.

평균을 0으로 유지하는 가장 쉬운 방법은 어떤 값 $x$를 데이터에 추가할 때 $-x$도 같이 추가하는 것이다.

아이디어 3

데이터를 만들 때 데이터의 개수 $n$이 바뀌면 제곱합이 moving target이 되어 어려워지므로, $n$을 적당히 큰 수로 고정한다고 치자. 데이터가 $n$개가 되기 전에 제곱합을 $nv$로 만들었다면, 남은 공간은 0으로 채우면 된다.

$x$와 $-x$를 추가하면 $2x^2$만큼 제곱합에 더해진다. 이는 항상 짝수이므로 $n = 2m$으로 두면, 어떤 고정값 $mv$에 대해 $a_1^2 + \cdots + a_m^2 = mv$를 푸는 문제가 된다.

구성 전략

아이디어 4

정수론을 배웠다면 알겠지만 $m=4$만 되어도 항상 해는 존재한다. 그러나 이를 실제로 구성하는 것은 Ruby IV에 준하는 난이도를 자랑하기에, 여기서는 $n$을 여유있게 잡는 풀이를 생각하는 것이 낫다.

간단하게 생각해서, 그리디하게 원하는 합 이하의 가장 큰 제곱수를 제거하는 방법을 생각해보자. 원하는 합이 $k$일 때, 그러한 제곱수를 제거하면 최악의 경우 약 $2 \sqrt{k}$ 정도가 남는다. $m = 50$ 정도로 두면 원하는 합은 최대 $5 \times 10^{10}$이고, 널널하게 대략적으로 계산해 보았을 때 $i$개의 제곱수를 제거한 후 남는 값의 상한은 다음과 같다.

  • 1회 제거 후: $5 \times 10^5$
  • 2회 제거 후: $1500$
  • 3회 제거 후: $80$
  • 4회 제거 후: $20$

따라서 남은 수는 1로만 채워도 충분할 정도의 크기가 되므로, $n = 100$ 정도로 잡는 것으로 조건을 만족하는 답을 항상 얻을 수 있다.

Pseudocode

fn solve(mu, v):
    n = 100
    sum = 50 * v
    a = []
    while sum > 0:
        x = isqrt(sum)
        a.push(mu + x)
        a.push(mu - x)
        sum -= x * x
    while a.len() < n:
        a.push(mu)
    return a