저 분들 중 상당수가 여기선 AC가 안나오겠죠ㅠㅠ... 구글링해보니 논문에 의해 O(N)에 풀리는 문제네요...
1659번 - 수 (Hard)
논문 좌표 남겨드려요~ http://john2.poly.edu/papers/jcb05/paper.pdf
일단 링크가 잘려서 web archive 링크를 대신 걸어둡니다
https://web.archive.org/web/20120907013424/http://...
그리고 이 논문을 열심히 읽어봤는데... 논하고 있는 문제는 1659번 문제랑은 약간 다릅니다.
논문에 있는 문제는
|S|>|T| 이면서 S의 원소는 T의 원소 중 정확히 1개와 매칭되어야 하고, T의 원소는 S의 원소 중 적어도 1개와 매칭될 때
전체 cost를 최소로 하는 문제입니다.
논문에서는 이걸 many-to-one assignment problem 이라고 부르고 있습니다.
1659번 문제는 논문에서 잠깐 언급되는 many-to-many version 입니다.
접근 방식을 비슷하게 적용할 수도 있을 것 같아보이지만...여튼... 1659번 문제랑은 약간 다른걸로...ㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
h0ngjun7 9년 전
ACM-ICPC Live Archive나 대회 당시의 문제 원문을 보면 N이 50,000이하인데 저지에 옮기면서 500,000으로 바뀌었나보네요...
Live Archive에선 O(N^2) dp에서 불필요한 iteration은 안하는 알고리즘이 0.079s로 통과하는데 흑....
으아 어려워요!