redcube231   1년 전

https://vjudge.net/problem/UVA...

다른 사이트에서 확인해보니 같은 문제의 제한 시간이 9초이고, 해설에서도 심슨 적분을 구현해 근사치를 얻는 방식으로 답을 찾습니다.

수치적분은 상대적으로 많이 느릴 수 밖에 없기 때문에 시간을 여유롭게 준 것 같은데, 테스트 케이스의 수가 10000개이기 때문에 1초는 턱없이 부족합니다.

제가 풀기 전 유일한 정답자분도 맞을 때까지 억지로 오차와 해상도를 바꿔가며 노가다를 한 것으로 보입니다.

하지만 이 문제는 3차원 기하학을 잘만 구현하면 O(1)에 답을 구할 수 있습니다.

난이도 구분 요청 글을 올렸습니다.

herdson   1년 전

저는 원본 제한을 따를 수 있으면 따라야 한다고 생각하는데요. 과거 스도쿠 문제가 백트래킹으로 풀리는 Easy와 댄싱링크를 쓰는 Hard로 나뉜 것처럼 이것도 원 문제는 9초로 복원하고 시간 제한을 대폭 줄인 Hard 버전을 신설하면 좋을 거 같습니다.

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