bubbler   1년 전

https://www.acmicpc.net/proble... (9254 역행렬)은 https://www.acmicpc.net/board/... 처럼 ill-conditioned matrix를 데이터에 넣게 되면 사실상 풀 수 없는 문제입니다.

이 문제도 같은 문제가 있습니다. 입력 행렬의 성분의 범위가 명시되지 않았기 때문에 band에 0, 1, 2만 써서 ill-conditioned matrix를 만들 수 있는지 확인해 보았는데, 결론적으로 됩니다. 짝수 크기의 행렬의 주 대각선에는 2, 0, 2, 0, ...를, 양쪽 band에는 1, 2, 1, 2, ...를 채우게 되면, pivoting 없이 LU decomposition을 한 결과의 U의 대각선에는 0이 존재하지 않으면서 (-1을 출력할 상황이 아님), U의 원소로 7.143e300이 등장합니다. 소수점 셋째 자리까지 출력해야 하는 이 문제 저지의 특성상, 이는 300자리 수를 정확히 계산해야 한다는 뜻이 되며, 바로 이웃한 줄에 등장하는 1e-300 단위의 수도 그만큼 정확히 계산해야 한다는 뜻이 됩니다. 현재 정답 코드가 C++로도 100ms 이내에 들어오는 코드가 없는데, 이만한 정밀도의 계산을 추가하여 시간 내에 계산하는 것은 사실상 불가능한 것으로 보여집니다.

(Mathematica 코드)

아래 코드는 위에서 설명한 입력을 생성하는 코드입니다.

djm03178   1년 전

이 이슈 때문에 오늘 solved.ac에서 not ratable 판정을 받았습니다.

댓글을 작성하려면 로그인해야 합니다.