mythofys   2년 전

제출번호 : 77060538

m, k 제한이 낮아 추가 시간이 주어지는 pypy3로 구간 합 알고리즘을 활용한 풀이가 통과합니다.(약 4초)

추가 시간 10초가 주어지는 것을 감안하면 데이터 추가로는 위 풀이를 막기 힘들어 보입니다.

n, m, k 제한을 다시 설정하여 데이터를 추가하거나 pypy3 시간을 재 조정해주세요.

djm03178   2년 전

C++로도 넉넉하게 통과됩니다. https://www.acmicpc.net/source...

문제를 푸는 방법은 하나로 정해진 게 아니고, 이 문제에서 O(mk) 풀이는 충분히 시간 내에 돌 수 있는 정도로 생각할 수 있기에 굳이 막을 필요가 없어 보입니다.

mythofys   2년 전

늦은 시간에 죄송합니다!

위 문제가 세그먼트 트리 알고리즘의 기본 문제로 불리는 문제이기도 하고, n, m, k 제한이 세그먼트 트리 풀이를 의도한 것으로 보여 요청을 제시하였습니다.

https://www.acmicpc.net/board/...

위 링크와 같은 사례 (물론 위 풀이가 O(mk) 구간 합이라는 보장은 없지만)도 존재하였기에 요청을 올려두면 재량껏 판별하시지 않을까 싶어서 올렸습니다.


혹시 요청 내리는 게 맞다고 판단하신다면 답글 주신다면 내리겠습니다!


(별개로 위 풀이도 정해 풀이라면 solved.ac 티어는 재 조정될 필요가 있어 보이네요)

djm03178   2년 전

제 의견도 그냥 하나의 의견일 뿐이니, 요청을 내릴 필요는 없어 보입니다. 최종 판단은 백준님이 하시는 거니까요.

문제가 세그먼트 트리를 의도하고 만들어진 것은 맞는 것 같으나, 의도가 어쨌건 문제의 제한을 통과할 수 있는 다른 풀이가 존재하고, 이러한 풀이를 생각해서 푼 사람이 문제 조건의 조정으로 인해 페널티를 받는 것은 부당해 보입니다.

또한 solved.ac 티어도 조정될 필요가 없다고 생각합니다. 저는 O(mk) 풀이가 세그먼트 트리보다 떠올리기 어렵다고 생각하고, 세그먼트 트리에 대한 사전지식이 없는 사람이라고 해도 O(mk) 풀이를 생각하는 건 충분히 골드 1보다는 어려운 발상이라고 봅니다.

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