[문제 제작 후기] BAEKJOON 15328 - 산타의 선물

이 문서는, acmicpc.net 15328번 산타의 선물 문제를 만들게 된 계기, 풀이 그리고 테스트 데이터를 만든 방법에 대해 설명합니다. 문제 스포일러를 원치 않는 분은 읽지 않아주셨으면 합니다.

---

문제를 단순화 하면 다음과 같습니다.인지 아닌지 판단하세요.

이 문제를 만들게 된 계기는 어떤 트윗에서 시작합니다.

아니... 그... 저..... pic.twitter.com/agXpmPH9r3

— 시프트 / shift* (@shiftpsh) December 27, 2017

UCPC 2016 D번문제인 Flowey's Love입니다. 입력과 출력이 전부다 정수이지만, 실수오차에 매우 민감한 가혹한 문제입니다. 사실 데이터가 충분히 강한지도 의문입니다. 왜냐하면 이 문제는 유리수, 혹은 제곱근, 혹은 그 수의 제곱근등등을 대소비교를 해야하는 문제이고, 이 문제가 다항시간 안에 풀리는지 안 풀리는지는 현재도 아직 결론이 나지 않은 문제입니다.

Is there an polynomial time algorithm to find that sum of square-roots is less than an integer?https://t.co/6KrhmWuhZchttps://t.co/qeQlJKaZFa

— 이혜아 (@mega_kina) December 27, 2017

뭐 결론적으로 말해서, 컴퓨터에서 지원하는 double 자료형은 오차가 있기 때문에 사용을 해서는 안됩니다. 한가지 예로는 double을 사용한 sqrt에서는

sqrt(6222) + sqrt(8801) + sqrt(14431) + sqrt(8132): 383.00000000000006

이지만, 실제로는

입니다. double을 사용하면 383보다 크다고 나오지만, 실제로는 작죠.

여담으로, a, b, c, d가 모두 제곱수가 아닌 경우에는 등호가 성립하지 않습니다. 숫자가 4개가 아니라 임의의 갯수여도 성립합니다. 다음 논문을 참조하면 좋을 것 같습니다. http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/INCOMING/reu_paper.pdf

뭐 결국에는, 문제는 실수 오차입니다. 실수 오차에 대해서 깊은 설명은 하지 않겠지만, double자료형의 경우에는 2^-53, long double자료형의 경우에는 2^-64만큼의 오차가 계산할 때 생길 수 있습니다. 이 문제를 풀기 위해서는 충분하지 못한 정확도 입니다.

사람들이 실수 오차에 대해 좀 더 유의해줬으면 바라고, 문제를 내는 사람들이 실수에 대해 좀 더 관대한 생각을 가지기를 그리고 사람들이 고통받는것을 보기 위해 이 문제를 내었습니다.

---

이 문제에 대한 제 코드는 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
typedef __float128 real_t;

__float128 mysqrt(__float128 x)
{
    if(x==0) return 0;
    __float128 y = 1, gy = 0;
    do
    {
        __float128 t = (y+(x/y))/2;
        gy = y;
        y = t;
    }while(y!=gy);
    return y;
}


int main()
{
    int N; scanf("%d", &N);
    for(int i=0; i<N; ++i)
    {
        int px = 0, py = 0, pz = 0;
        real_t ans = 0;
        int x; scanf("%d", &x);
        for(int j=0; j<4; ++j)
        {
            int a, b, c; scanf("%d%d%d",&a,&b,&c);
            ans += mysqrt(real_t((px-a)*(px-a)+(py-b)*(py-b)+(pz-c)*(pz-c)));
            px = a, py = b, pz = c;
        }
        if(ans <= x) puts("YES");
        else puts("NO");
    }
    return 0;
}

결국에는, __float128자료형을 써서 해결했습니다. 어떻게 __float128을 사용하면 충분한 정확도를 가지냐 라는것을 확인했냐고요? 왜냐하면, 이 문제를 만들 때에 모든 가능한 입력에 대해서 확인을 해 보았습니다.

0부터 40000까지의 제곱수 세개의 합으로 표현 가능한 숫자는 58000개 정도가 나옵니다. 여기서 4SUM 문제를 풀고 (4SUM문제는 N^2 lgN의 시간복잡도를 가집니다.)  오차가 일정 범위안에 있는 수들을 다 뽑아내었습니다. 램은 26GB, CPU시간은 2.8GHz 프로세서에서 18분이 걸렸고, 숫자들의 후보를 모은 파일은 60GB였습니다.

여기서 오차가 매우 작은 숫자들을 추려내고 추려내서 숫자들을 뽑아내고, 그리고 그 데이터를 가지고 절댓값이 100 이하가 되게 넣을 수 있는지를 이리저리 계산을 했습니다. 그래서 데이터 파일들을 만들었습니다.

사용된 데이터 중 하나는,

2
583
-9 -5 0
-97 -21 -16
22 -100 95
-100 98 -96
747
-42 -30 -2
-98 -93 74
97 57 -66
-98 -98 99

이고,

의 결과를 얻었습니다.

참고로 이 문제는, 제곱을 열심히 반복하면 정수만 사용해서 문제를 풀 수 있다고 합니다. minimal polynomial이 16차이고, 이걸 구해서 대소비교를 하는 방법으로도 해결을 할 수는 있습니다.

sqrt(d)<k-sqrt(a)+sqrt(b)+sqrt(c) 가 되고 제곱하면 xsqrt(ab)+ysqrt(bc)+zsqrt(ca)<뭔가 정수 가 돼서 c 짝수개 있는 거 오른쪽으로 보내고 하면 되지 않을까요

— 서콴 (@sukh1222) December 27, 2017

---

기프티콘을 받으신 모든 분들 축하합니다! 그리고 기프티콘을 받지 못하신 분도 이런 재미있는 문제가 있으면 제가 다시 기프티콘을 들고 오도록 하겠으니 풀어주셨으면 합니다. 감사합니다.