15507번 - 연산 최적화
https://www.acmicpc.net/source...
일단 Suffix Array와 LCP를 통해 겹치는 max_prefix를 구하는 방법까지는 생각해두었고
그렇게 구한 max_prefix를 통해 맨 뒤에서 부터 C를 붙이거나, 또는 A랑 B를 붙이는 방식으로 전수탐색을 하면서
길이가 N을 만족하면, 해당 문자열이 올바른지 검사하는 방식인 풀이입니다.
mp에 대한 상태공간이 아무리 커봤자, n log n을 넘지 못한다는건 wolfram alpha로 계산기 뚜들겨서 증명했는데..
겹치는 부분 있으면 빠른 쪽이 이득이겄지~~ 하는 심정으로 가지치기 좀 섞으니까 맞았습니다.. (!mp[na].count(nb)) < 이 부분 입니다.
그런데 저 가지치기가 아무리 생각해도 정상적인 방법이 아닌것 같아, 반례가 있을 것 같은데, 반례를 도저히 못찾고 있습니다..
반례가 없다면 왜 그런지 아시는 분이 계실까요 ㅠ...
정해를 나중에 읽어보고 다시 풀어보려고 합니다.
일단 반례를 찾아서 추가 요청해 두었습니다. 의심하시는 부분과 관련이 있기를 바랍니다 :)
댓글을 작성하려면 로그인해야 합니다.
shjgkwo 3년 전
https://www.acmicpc.net/source...
일단 Suffix Array와 LCP를 통해 겹치는 max_prefix를 구하는 방법까지는 생각해두었고
그렇게 구한 max_prefix를 통해 맨 뒤에서 부터 C를 붙이거나, 또는 A랑 B를 붙이는 방식으로 전수탐색을 하면서
길이가 N을 만족하면, 해당 문자열이 올바른지 검사하는 방식인 풀이입니다.
mp에 대한 상태공간이 아무리 커봤자, n log n을 넘지 못한다는건 wolfram alpha로 계산기 뚜들겨서 증명했는데..
겹치는 부분 있으면 빠른 쪽이 이득이겄지~~ 하는 심정으로 가지치기 좀 섞으니까 맞았습니다.. (!mp[na].count(nb)) < 이 부분 입니다.
그런데 저 가지치기가 아무리 생각해도 정상적인 방법이 아닌것 같아, 반례가 있을 것 같은데, 반례를 도저히 못찾고 있습니다..
반례가 없다면 왜 그런지 아시는 분이 계실까요 ㅠ...
정해를 나중에 읽어보고 다시 풀어보려고 합니다.