PKU 3685. Matrix. AC get!

#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; }

으흠.

용호군 코드와 많이 닮았죠?

다음 주 풀 문제는 미리 예고하지요.

Maximum sum이라고...

일부러 안 한 건데....

용호군이 이런 무서운걸 해버려서....

용호군 코드와 제 코드에 대해 설명하지요.

일단 원래 내준 식은 i^2 + 100000i + j^2 - 100000j + ij 이지요?

일단 최소와 최대를 -100억, +100억으로 잡고 시작해 봅시다.

이 기존 식에 x라는 변수를 하나 추가하여,

i^2 + 100000i + j^2 - 100000j + ij - x라는 식을 만듭니다.

이 후, i에 대해 판별식을 만들어 det에 저장해 두었지요.

이차방정식의 판별식. 아시죠 다들?

이를 이용해 x값에 따라 i는 고정하고, j값을 1부터 5만까지 반복시켜

x값에 따라 유효한지 아닌지를 체크합니다.

이 때, cal_1과 cal_2는 딱 det값만큼 차이납니다.

j의 증가에 따라 둘 사이의 차이는 계속 변화합니다.

이 차이가 N을 넘을 때는 강제로 N으로 줄여서 sum에 지속적으로 누적시킵니다.

이걸 N번 반복하고 나서, 이 누적된 sum이 M보다 작거나 같다면 이 x는 유효하며,

아직 최소값보다는 작다는 의미입니다. 이에 따라 min을 x + 1로 설정합니다.

만약 sum이 M보다 크다면 x가 무효하다는 것이겠지요?

무효하다는 의미는 곧 최대값이라 봐도 무방하단 의미겠지요.

이를 이용해 계속 min과 max로 하한, 상한을 점차적으로 줄여나가는 방식을 택합니다.

보시면 내부 for문중 N번 돌때 sum <= M인지도 체크하는데,

이때는 이미 sum이 M보다 커진다면 더이상 x의 유효성을 검사할 필요가 없으니 바로 나오는 거지요.

이리하여 서로 상한과 하한이 크로스되면 이때의 min값이 바로 최소값이 되는거지요.

x가 0부터 시작해(-100억과 100억의 중간값) 판별식의 유효성 검사를 통해 이진탐색법처럼

가능한 범위를 점차적으로 좁혀나가는 겁니다.

아참, 유효성 검사란... x를 중심으로 잡았을 때, M번째로 작은 수가 x보다 작은 쪽에 포진해 있어야

유효함을 이용한 체크를 하는겁니다. cal_1과 cal_2는 순수하게 유효성 체크만을 위해 연산하는 변수이죠.

아, 그리고 dizies님께는 죄송합니다만....;;

PKU의 GCC는 비주얼 스튜디오에서 사용하는 dll과 같은 ms계열을 쓰기 때문에 __int64를 써도 전혀 문제가

되지 않는다는군요 -_-;

double형이나 long long형은 모두 오버플로우로 인해 정확하지 못한 연산값이 나와 WA가 나옵니다.

long long형도 처리만 잘 해 주면 정확한 답을 얻을 수 있을것 같습니다.






P.S.

다음주 진짜 Maximum sum 해도 될까요?-_-?