3개의 댓글이 있습니다.

• 
  hyunhwan

  예전에 문자 중계할 때 글들 중에서 해당 문제에 대한 중계내용을 퍼왔습니다.

  출처 : http://shovel.redfeel.net/~libe/daejeon10/?all=1

  • 나나, 스탱, 빙 이렇게 F, G, I번을 좀 파봤는데, F번은 union find, G번은 2SAT, I번은 정렬후 convex hull...도 아니고 그리디하게 외곽선을 구하는 문제로 생각됩니다.

  
  13년 전 link

• 
  Sejoure

  저희 팀에서 연습용으로 풀어봤었는데.. G번과 J번을 제외하고는 고생을 엄청했습니다.
  F번 union_find 이용하면서 각 외부그룹으로 나가는 최소 에지와 최대 에지를 매번 갱신하는 방법으로 N^2에 해결
  G번 한 정점을 네 정점으로 나누어 다른 네 정점과 에지가 있는지 찾아서 에지를 다시 생성하여 그래프 탐색하는 방식으로 N+M만에 해결, 모든 에지를 탐색하며, 사이클도 모두 검사해야함, 저희는 다이나믹+ 비트연산을 이용해서 속도를 빠르게했습니다.
  H번 작업 데드라인이 끝나는 순서대로 정렬하여 배치하면 가장 큰 패널티를 가장 작게 할수 있음을 이용하면 하나의 작업만 그 정렬을 벗어나면 두개의 패널티의 합을 가장 작게 할수 있음(하나만 패널티가 커지고 나머지중 가장 큰 패널티 하나가 작아질수 있으므로)
  N^3에 해결가능한데, 안되는 경우를 체크하면 이보다 줄일수 있을거 같음.
  I번 x+y = k 좌표계에서 k가 증가하는 방향대로 정렬한후, 영역을 체크.
  J번 입력에 나와있는 순서대로 음수시간대로 좌우에 맞춰 맨처음에 기차들을 넣습니다.
  그런다음 양수시간대로 그 기차들을 적절히 뺄수 있는지 체크하면서 넣을 수 있으면 그 선로에 넣고 같이 넣을수 없다면 다른 선로에 넣습니다.(그 체크는 각 선로에 들어가있는 마직 기차와 비교해보면 되겠죠) 수행시간은 선로 * 기차갯수
  이방법이 가능한 이유는, 이문제가 회의실 배정문제(최소 회의실을 배정하면서 모든 회의를 끝내는 문제)와 동일한 매커니즘으로 설명가능합니다. 다이나믹으로도 N^2에 가능합니다만 이방법이 가장 확실함.

  
  13년 전 link

• 
  Dynamical

  G번의 경우에는 아직 코딩은 안 해봤지만, 생각은 해 봤습니다. Sejoure님이 말하신대로 한 정점을 네 정점으로 나누면 아마 한 정점의 4가지 선택 중 하나를 고정했을 때, 나머지 정점들의 선택을 결정해야 하는데 다른 정점과 제대로 연결이 되려면 선택지가 4개가 아닌 2개 이하가 되어 2sat가 가능할 거 같네요.

  맨 마지막 문제 J번의 경우에는 작년에 PS에서 숙제로 나와서 코딩해서 채점하게 되었지만, Dilworth 정리를 이용해서, 인덱스트리 써서 적당히 n log n에 풀었던 것 같습니다. 이 정리는 이산수학 시간에 배웁니다.
  http://en.wikipedia.org/wiki/Dilworth's_theorem

  
  13년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.