grapecw   3년 전

일단 빠르게 찾기 위해서 lowerbound를 통해 찾았습니다.

그리고 구별을 편하게 하기 위해서 오른쪽 돌이냐, 감자냐 찾는 것을 upperbound, 왼쪽 감자냐 돌이냐를 찾는 것을 lowerbound로 하였습니다.

많은 수가 입력이 들어 올 것 같아서 input도 overwirte해주었고요.

이 이상으로 시간을 줄일 수 있는 방법이 있는지 조언을 해 주실 수 있으신가요?

evenharder   3년 전

현재 알고리즘은 왕복하면서 방문한 가장 왼쪽/오른쪽 칸의 위치를 저장하면서, 연속된 빈 칸을 한 번에 움직입니다. 때문에 쿼리당 시간복잡도가 O(N lg N)이 되어, 시간 제한을 통과하기에는 너무 느립니다.

연속된 빈 칸을 하나로 고려할 수 있다는 점까지는 파악하셨으니, 특정 위치에서 출발할 때 각 빈 칸들을 몇 번 방문하게 되는지 계산해보시기 바랍니다. 감자가 4~5개 정도 있을 때만 보아도 규칙을 찾을 수 있습니다. 물론 그 외에도 고려해야 할 점들이 있습니다.

다른 분의 PyPy 제출 중 564ms로 '맞았습니다!!'를 받은 코드가 있는 것으로 보아 불가능해 보이진 않습니다. 건투를 빕니다.

grapecw   3년 전

감사합니다. 좀 더 고민해 봐야 될 것 같습니다.

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