현재 알고리즘은 왕복하면서 방문한 가장 왼쪽/오른쪽 칸의 위치를 저장하면서, 연속된 빈 칸을 한 번에 움직입니다. 때문에 쿼리당 시간복잡도가 O(N lg N)이 되어, 시간 제한을 통과하기에는 너무 느립니다.
연속된 빈 칸을 하나로 고려할 수 있다는 점까지는 파악하셨으니, 특정 위치에서 출발할 때 각 빈 칸들을 몇 번 방문하게 되는지 계산해보시기 바랍니다. 감자가 4~5개 정도 있을 때만 보아도 규칙을 찾을 수 있습니다. 물론 그 외에도 고려해야 할 점들이 있습니다.
다른 분의 PyPy 제출 중 564ms로 '맞았습니다!!'를 받은 코드가 있는 것으로 보아 불가능해 보이진 않습니다. 건투를 빕니다.
grapecw 3년 전
일단 빠르게 찾기 위해서 lowerbound를 통해 찾았습니다.
그리고 구별을 편하게 하기 위해서 오른쪽 돌이냐, 감자냐 찾는 것을 upperbound, 왼쪽 감자냐 돌이냐를 찾는 것을 lowerbound로 하였습니다.
많은 수가 입력이 들어 올 것 같아서 input도 overwirte해주었고요.
이 이상으로 시간을 줄일 수 있는 방법이 있는지 조언을 해 주실 수 있으신가요?