h0ngjun7   9년 전

ACM-ICPC Live Archive나 대회 당시의 문제 원문을 보면 N이 50,000이하인데 저지에 옮기면서 500,000으로 바뀌었나보네요...

Live Archive에선 O(N^2) dp에서 불필요한 iteration은 안하는 알고리즘이 0.079s로 통과하는데 흑....

으아 어려워요!

h0ngjun7   9년 전

0e6f0a5d823b7f968dd3f1e4af093a85.png

저 분들 중 상당수가 여기선 AC가 안나오겠죠ㅠㅠ... 구글링해보니 논문에 의해 O(N)에 풀리는 문제네요...

baekjoon   9년 전

원본을 따로 추가할게요

h0ngjun7   9년 전

논문 좌표 남겨드려요~ http://john2.poly.edu/papers/jcb05/paper.pdf

ntopia   8년 전

일단 링크가 잘려서 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번 문제랑은 약간 다른걸로...ㅠㅠ

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