PKU 3685. Matrix. Solution.

#include <stdio.h> #include <math.h> int main() { int n; __int64 N, M; __int64 min, max; __int64 x, j; __int64 sum; __int64 det, cal_1, cal_2; const __int64 w = 100000; scanf("%d", &n); while (n--) { scanf("%I64d%I64d", &N, &M); max = w * w * 10; min = -1 * max; while (min < max) { x = (min + max) / 2; if (x == max) { x--; } sum = 0; for (j = 1 ;(j <= N) && (sum <= M) ;j++) { det = (__int64)sqrt((w + j) * (w + j) - 4 * (j * j - w * j - x)); cal_1 = (-1 * w - j - det) / 2; cal_2 = (-1 * w - j + det) / 2; if (cal_2 > N) { cal_2 = N; } if (cal_1 < 1) { cal_1 = 1; } if (cal_2 >= cal_1) { sum += (cal_2 - cal_1 + 1); } } if (sum < M) { min = x + 1; } else { max = x; } } printf("%I64d\n",min); } return 0; }

크흥흥

제가 이걸 소개하게 됐군요.

-_-

이차함수 그림 대충 그린건 죄송합니다 -_-;

자신이 없었어요;;

일단, 환타님은 2차원 좌표평면에서 자유변수를 축으로 쓰는 법에 대해 안배우셨을테니,

준식인 i^2 + wi + j^2 - wj + ij에서 i를 x로 치환합니다.

해당 줄(옆으로~)에서 각 원소의 값을 가진다고 생각하며,

j는 1부터 N까지의 상수라고 생각합니다.

이 경우, 준식을 y에 대한 식으로 표현한다면 위의 그래프를 그릴 수 있습니다.

여기서 w는 10만으로, 편의상 치환했습니다.

cal_1과 cal_2는 보시다시피 x의 두 근(해) 입니다.

또한 K라고 써둔 저 부분은 코드에서는 x로 둔 부분입니다.

이 코드는 "M번째로 작은 원소가 K 일 것이다." 라고 가정하고 시작합니다.

이때 min값과 max값을 행렬 내에서 절대 존재할수 없을 정도로 크고 작은 값으로 설정한 후 시작하게 됩니다.

k는 그 내부에서 임의로 설정하나, 편의상 min과 max의 중간값으로 설정하면 이분탐색 메소드로

사용이 가능하게 됩니다.

위의 그래프에서 보시면 알겠지만,

해당 그래프에서 K보다 작은 부분의 모든 정수 x값들은 j번째 줄에서 K보다 작은 원소값을 갖게 됩니다.

여.기.서. 잠깐 -_-

리턴군의 코드는 여기에서 문제점이 발생합니다.

cal_2가 cal_1보다 작을 일은 당연히 없는데, 리턴군은 cal_2 >= cal_1일 경우에 대해 체크하게 해 두었지요.

사실 그럴 필요가 없었습니다.

cal_2가 음수라면.... cal_1도 당연히 음수이고(cal_2가 큰 근이기 때문이지요.),

이에 따라 이 행렬에서 음수 인덱스는 존재하지 않기 때문에 검토할 가치도 없습니다.

동시에 cal_1이 N보다 큰 경우도 검토할 가치도 없지요.

N by N 행렬의 인덱스 바운드 밖에 있는 값은 볼 필요가 없으니까요.

단, cal_1 ~ cal_2의 범위 내에 1 ~ N이 존재한다면, 해당 줄의 N개 원소가 모두 K보다 작은겁니다.

이렇게 j를 1부터 N번쨰줄까지 모두 체크하여

cal_2와 cal_1의 차를 계속 구해서 sum에 합하면 (당연히 바로 위에 설명한대로

두 값의 차가 N을 넘는다면 N으로 바꾸어줘야 하지요.)

sum의 값은 for문을 탈출할 무렵엔 K보다 작은 숫자의 갯수가 됩니다.

이떄 이 sum이 M과 같다면 그냥 그대로 출력하면 되겠지요?

이 부분이 리턴군의 코드에서는 체크되지 않았습니다.

동시에, sum이 M보다 작다면 K값이 더 작아져야 하므로,max값을 K 로 설정합니다.

(아래 부분은 리턴군과 제 생각에 차이가 있던 부분입니다. 제 경우는 원래 K로 하려고 했었지요.

리턴군의 방식이 맞았었습니다.)

반대로, sum이 M보다 크다면 당연히 K값은 더 커져야 하므로 min값이 K + 1이 되어야 하지요.

이 과정을 반복해나가면 sum이 M과 같아지거나,

min과 max값이 서로 교차되어 min과 max가 같아지는 경우가 생깁니다.

(이 부분에서 리턴군의 독특한 실수 하나. 외부 while문 보시면 min < max인 동안 돌게 되어있습니다 -ㅁ-

맞긴 맞습니다만 뭐....)

이 경우 min값, max값이 바로 답이 되는 경우이지요.

자, 여기서 제가 증명하지 못한 부분이 있습니다.

ㅡ,.ㅡ...

cal_1과 cal_2가 항상 정수는 아니므로 답이 확실하지 않다.

....

실제로 K가 1이라 한다면,

K는 이 행렬 내에 존재하는 값이 아니므로(찾아보세요... 없어요 -_-;;)

cal_1과 cal_2는 정수값이 아닙니다.

제 원래 구상 코드에서는 ceil()로 반올림을 해서 처리를 하는 방안을 생각했었고,

리턴군은 그냥 int형에 쑤셔넣어서(-_-?;;;) AC를 받아냈습니다.

제가 보기에 둘 다 오차도가 생각보다 커지긴 합니다만...

min과 max가 교차하는 순간이 바로 답이라는건 틀릴 수 없는 진리이기 때문에 AC가 두 경우 모두

나오긴 합니다. -_-;

cal_1과 cal_2가 정수가 아닌 실수값을 갖는 순간에 대해 이 알고리즘의 신뢰도가 보장하기 힘든데도

답이 정확히 나오는것에 대해 정확한 증명은 못했으니...

Mr.K.

이걸론 태클 걸지 마시게나 -_-;;

P.S.

cal_1과 cal_2의 의미를 언급을 안했었군요.

저 그래프를 보시면 아시겠다만,

j번째 줄에서 cal_1번째 i(혹은 x)부터 cal_2번째까지의 원소는 모두 K보다 작은 값입니다.