34208번 - 수열과 쿼리 46
현재 정보올림피아드를 준비하고 있는 중학생입니다
2025년 koi중등부 2차 4번문제인 수열과 쿼리를 풀기 위해 도전하고 있는데 현재 $O(N^2 + Q \log N)$풀이로(볼록껍질) 서브태스크 3($N \le 10,000$)까지 풀었습니다
여기서 $O(N^2)$을 $O(N \log N)$으로 바꾸기 위해서 필요한 알고리즘에 분할정복이 있어서 분할정복을 사용해야 할 것같은데 분할정복이 무엇인지 모르겠습니다
분할정복이 뭔지 찾아보지 않고 직접 생각해보는게 좋을지 아니면 분할정복을 인터넷에 찾아본 후 이해한 후에 다시 풀어보는게 좋을지 모르겠습니다
분할정복보다 CHT 를 먼저 공부한건 좀 신기하네요. 분할정복을 간단히 설명하면 각 과정을 절반으로 나눠서 계산하고 그걸 합치는 과정을 반복하는 알고리즘입니다. 분할정복에 대한 내용은 인터넷에서 많이 찾을 수 있으니 한번 검색해보세요.
혹시 올림 준비는 언제부터 하셨나요
CHT를 먼저공부한건 아닙니다
각길이마다 최대를 일차함수인 ax+b로 표현할수있는데 중간에 최댓값을 찍고 다시 내려감으로 이분탐색으로 풀면된다는것을 생각해냈습니다
이 아이디어를 구현한후에 CHT를 찾아보니까 제 아이디어와 일치해서 볼록껍질이라고 쓴것입니다
정올 준비를 얼만큼 했는지 정확하게 기억은 못하지만 아마 본격적으로 시작한건 6~8개월 전일껍니다
혼자 CHT를 생각해낸건 대단하네요... 이렇게 좀 고민해보다가 알고리즘 자체를 모를때는 한번 배워보고 하는 식의 공부방법은 좋은 것 같아요. 정올 수상 응원할게요!
분할정복을 각 길이당 최대를 구하는데 사용하는줄 알았더니 풀이를 완전 바꿔야 했군요
그래도 100점 풀이를 찾는게 좋겠죠?
댓글을 작성하려면 로그인해야 합니다.
b2r 7달 전
현재 정보올림피아드를 준비하고 있는 중학생입니다
2025년 koi중등부 2차 4번문제인 수열과 쿼리를 풀기 위해 도전하고 있는데 현재 $O(N^2 + Q \log N)$풀이로(볼록껍질) 서브태스크 3($N \le 10,000$)까지 풀었습니다
여기서 $O(N^2)$을 $O(N \log N)$으로 바꾸기 위해서 필요한 알고리즘에 분할정복이 있어서 분할정복을 사용해야 할 것같은데 분할정복이 무엇인지 모르겠습니다
분할정복이 뭔지 찾아보지 않고 직접 생각해보는게 좋을지 아니면 분할정복을 인터넷에 찾아본 후 이해한 후에 다시 풀어보는게 좋을지 모르겠습니다