ho94949   5년 전

이 문제는 N*(N의 약수의 개수)로 문제를 해결하는 풀이가 존재하고, 최신 프로세서와 컴파일러의 최적화가 매우 좋기 때문에, 빠르게 동작하는 종류의 문제입니다.

출제자의 코드를 살펴보면, 해당 풀이를 의도한 것으로 보입니다. http://acm.student.cs.uwaterlo... 또한, 출제자의 의도가 문제의 전부가 아닐지라도, 해당 시간제한과 제한 안의 데이터에 대해서는 통과하는 답입니다.

이 문제에서는 해당 풀이를 허용하고, Failure Function을 사용하는 O(N) 풀이만 동작하는 문제를 새로 만드는 방식이 좋지 않을까 하고 생각합니다. 

sait2000   5년 전

새 문제를 만든다면 N을 소인수분해한 다음 소수 지수에 대해서 이분탐색을 하는 O(n log n) 풀이를 막을지 또는 막을 수 있는지 논의해야 한다고 생각합니다

bubbler   4년 전

O(n)풀이가 정해인 문제를 만드는 데 있어서 이슈가 하나 있는데, C의 strstr, Python/Rust의 str.find()가 선형시간에 첫 match의 index를 찾을 수 있기 때문에 결국 내장함수 쓰는 문제로 귀결됩니다. (제출번호 47600681, 파이썬 <200ms)

현재 언어 내장함수로 풀리는 kmp 문제들의 티어를 실버로 내리는 논의가 진행 중이어서, 이 문제의 풀이를 O(n)으로 한정한 새 문제를 내더라도 실버 내지 (아이디어를 높게 쳐준다면) 골드밖에 되지 않아 새로 문제를 내는 의미가 별로 없어 보입니다.

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