| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 284 | 81 | 48 | 27.429% |
이 문제는 선형 회귀는 너무 쉬워 3과 문제에서 사용하는 식의 차수만 다릅니다.
유림이는 선형 회귀에 자신이 있다. 그래서 MatKor 동아리에서 선형 회귀에 관한 수업을 할 때 집중하지 않았다. 당시 강사였던 동우는 이를 못마땅하게 여겨 유림이에게 과제로 선형 회귀는 너무 쉬워 1과 선형 회귀는 너무 쉬워 2, 선형 회귀는 너무 쉬워 3을 내주었고, 유림이는 세 문제를 쉽게 풀었다.
기존의 일반적인 선형 회귀 문제는 다음과 같다. 데이터 $(x_1,y_1) ,(x_2,y_2) ,\cdots ,(x_n,y_n)$이 주어졌을 때, 이를 가장 잘 설명하는 일차함수 $y=ax+b$를 찾는 문제이다. 여기서 주어진 점들 $(x_i,y_i)$에 대해 $x_i$를 통해 얻는 추정치 $\hat{y_i} =ax_i+b$로 정의하고, 실제 $y_i$에서 예측치인 $\hat{y_i}$를 뺀 값 $y_i-\hat{y_i}$를 잔차 $\epsilon_i$로 정의한다.
선형 회귀 문제는 이 잔차 제곱의 합이 0ドル$에 가장 가깝게, 즉 $f_2(a,b) =\displaystyle\sum_{i=1}^n\epsilon_i^2=\displaystyle\sum_{i=1}^n(y_i-ax_i-b)^2$이 최소가 되도록 하는 실수 $a$와 $b$를 찾는 문제이다.
동우는 여기에서 더 발전시켜 잔차 $k$제곱의 합 즉, $f_k(a,b) =\displaystyle\sum_{i=1}^n\epsilon_i^k=\displaystyle\sum_{i=1}^n(y_i-ax_i-b)^k$이 0ドル$에 가장 가깝게 하는 실수 $a$와 $b$을 구하는 문제를 냈다.
이 문제를 풀던 유림이는 너무 어려워서 동우에게 조금만 쉽게 바꿔 달라고 하자 동우는 조금 고민하다 다음과 같은 조건을 추가한다. ”$k=4$일 때만 구해. 그리고 $y$절편이 정해져 있을 때 기울기만 정해. 또, 모든 점의 $x$좌표는 양의 정수, $y$좌표도 정수라고 가정하자.”
이제 유림이가 풀 문제는 다음과 같다. 주어진 $b$에 대해 $f_4(a) =\displaystyle\sum_{i=1}^n\epsilon_i^4=\displaystyle\sum_{i=1}^n(y_i-ax_i-b)^4$이 0ドル$에 가장 가깝게 하는 실수 $a$를 $a_4$라고 할 때, $a_4$를 구하면 된다.
첫 번째 줄에 데이터의 개수를 의미하는 정수 $n$과 $y$ 절편을 의미하는 정수 $b$가 공백으로 구분되어 주어진다. $(1\le n\le 10^5;$ $-10^6\le b\le 10^6)$
두 번째 줄부터 $n$개의 줄에 걸쳐 한 줄에 하나씩 점의 좌표를 나타내는 정수 $x_i$와 $y_i$의 값이 공백으로 구분되어 주어진다. $(1\le x_i\le 10^6;$ $-10^6\le y_i\le 10^6)$
이때, 서로 같은 점이 여러 번 주어질 수 있음에 유의하라.
첫 번째 줄에 $f_4(a)$의 값이 0ドル$에 가장 가깝게 하는 $a,ドル 즉, $a_4$을 출력한다.
답이 여러 가지라면 그중 아무거나 하나 출력한다.
가능한 정답 중 최소 하나 이상과의 절대오차 또는 상대오차가 10ドル^{-7}$ 이하이면 정답으로 인정된다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $b=0;$ $y_i = 0$ |
| 2 | 48 | $b = 0;$ $-10\le y_i \le 10$ |
| 3 | 57 | $b=0;$ $y_i=x_i$ 혹은 $y_i= 0$ |
| 4 | 55 | $n \le 2$ |
| 5 | 82 | 추가적인 제한 조건 없음 |
2 -2 3 10 1 2
4
$a=4$일 때, $f(a)=(10-4\cdot 3 - (-2))^4 + (2-4\cdot 1 - (-2))^4 = 0 + 0 = 0$으로 0ドル$에 가장 가깝다.
2 0 2 1 3 -8
-1.501196113
$a=\frac{-208 -38 \sqrt[3]{12} + 57\sqrt[3]{18}}{97}$일 때, $f(a)=\frac{130321}{912673}\left(-2255+5256\sqrt[3]{12}-2646\sqrt[3]{18}\right)$로 0ドル$에 가장 가깝다.
5 0 1 1 1 2 1 4 2 5 2 6
2.5757694454
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring G번