7개의 댓글이 있습니다.
-
-
ibroker -
대회에 참가를 안해서 정확한 해법인진 모르겠지만, J번 생각만 해본걸 써보면요 ^^;;
1차원 상에 S집합은 흰색돌로, T집합은 검은색돌로 놓은다음에 모든 흰색과 검은색 돌을 최소의 가중치로 연결해야 한다고 하면,
연결할 돌을 결정할 때는 항상 자신과 인접하게 가장 가까운 돌과 연결을 해야 한다는 것을 알 수 있습니다. 즉 MATCHING을
시킬 때, 인접하게 위치한 돌과 연결하지 않고 구지 하나 건너있는 돌을 연결할 필요가 없다는 뜻입니다.
그러면, 다시 S와 T를 BIPARTITE GRAPH로 바꿔서 생각해보면, MATCHING되는 EDGE는 CROSS가 생기지 않습니다.
여기서 적절히 다이나믹 비스무리하게 돌리면 되지 않을까 생각해 봤습니다. ㅋ
I번은 시작점에서 시작해서 선분 상에 있는 모든 좌표를 LIST로 연결합니다. 그러면서 어떤 점에서 만나게 되면
그 만나는 점에서 LIST를 따라가면서 CYCLE을 제거해 줍니다. LIST를 역행하는 CYCLE은 아마 안생길 거구요(?)
그냥 제 생각이라 틀릴 가능성이 농후합니다 ㅋㅋ
16년 전 link
-
-
-
astein -
음.. I번의 경우에는 두 글자씩 파싱한 다음, step by step별로 최종결과를 갱신하는 식으로 작성하면 됩니다.
현재까지의 결과의 길이가 n에 비례하기 때문에, 답을 구하는 데 O(n^2)이라 충분히 나올겁니다.
H번의 경우는 본선에서 실제 대회에서 아무도 푼 팀이 없는데. 간단하게 설명하자면, 입력받아지는 단어들로 오토마타를 만든 다음, 각각의 Edge에 -1의 가중치를 부여한 후 Bellman-Ford 알고리즘으로 최장경로를 찾으면 됩니다. (오토마타를 만드는 방법은 나중에 에디토리얼에.... 아! 물론 제가 한다는 건 아니고 ...)
J번은 ibroker님의 알고리즘으로는 아마 예제가 안나올거 같은 [...] 근데 저도 답은 모른다는 -_-;
16년 전 link
-
-
-
Taeyoon_Lee -
E랑 G는 잘 모릅니다=_=
ABCDF는 제가 쓸 수 있지만.. 제가 써도 괜찮을까요..?
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Taeyoon_Lee
본선 문제 Editorial은 언제 올라 올까요?
HIJ의 해법이 보고 싶습니다!
=_= 저희 팀은 마지막에 J번이 분홍색이라고 보고, 열심히 생각했는데
문제의 높은 벽에 좌절했습니다 OTL..
16년 전