13개의 댓글이 있습니다.

• 
  Taeyoon_Lee

  저는 꽤 심플한(?) 두가지 방법으로 풀고, 마지막에 더 좋은 답을 취했습니다.

  ~ 방법1 ~
  1. 가장 큰 선거구의 upper bound를 정합니다. 그러면 자동적으로 가장 작은 선거구의 lower bound도 정해지죠.
  2. 지도를 잘라서 bound 크기 내의 직사각형들로 나눌 수 있는 지 확인해봅니다. DP로 할 수 있습니다. f(x1, y1, x2, y2) = ...
  3. 나눌 수 있다면 upper bound를 줄이고, 나눌 수 없다면 upper bound를 늘립니다. upper bound가 작을수록 땅이 더 잘게 쪼개져서 답이 더 좋아지겠지요?
  4. 적절한 upper bound를 찾은 후에는, 지도를 최대한 많은 직사각형으로 나누어 봅니다. 역시 DP로 풀 수 있는 최적해 문제지요.
  5. 100 x 100 크기면 시간이 빠듯하기 때문에, 인접한 두 셀을 합쳐서 50 x 50 이내로 만들고 풉니다.

  ~ 방법2 ~
  1. 텔레토비가 더 많이 사는 구를 "양수구", 외계인이 더 많이 사는 구를 "음수구"라고 정의합니다.
  2. 모든 셀을 하나의 구로 나눕니다.
  3. 가장 인구가 적은 음수구를 선택합니다.
  4. 주변에 가장 인구가 적은 양수구와 합칩니다.
  5. 3으로 돌아가서 음수구가 없어질 때까지 반복합니다.
  6. 가장 인구가 적은 양수구를 선택합니다.
  7. 가장 인구가 많은 양수구와 비교해서 5배 차이 이내면 종료합니다.
  8. 아니면, 주변에 가장 인구가 적은 양수구와 합칩니다.
  9. 6으로 돌아가서 반복.

  
  12년 전 link

• 
  Taeyoon_Lee

  대부분의 경우 방법1의 답이 훨씬 더 좋았고, 방법2는 작은 답들에 대해 더 좋은 경우가 가끔 있었습니다. 50개 데이터에 대해 42:8 정도였던 것 같네요. :)

  
  12년 전 link

• 
  일루

  채점은 1000개 먼저 돌렸고 오차범위 안쪽에 있는 것들이 없으면 중지하려고 했습니다.

  여기서 4000개 더 돌려보고 결과가 어떻게 나오든 그것을 최종 결과로 하려고 합니다~ 내일 안엔 다 돌아갈 거예요.

  
  12년 전 link

• 
  kaizero

  DP로 풀었다가 50*50으로 고쳤는데도 0나와서 하루만에 포기했네요ㅠ

  
  12년 전 link

• 
  hyunhwan

  다시 4,000개의 데이터를 추가하여 돌리고 있습니다. 저는 일루님이 밉습니다.

  
  12년 전 link

• 
  MiNu

  저는 우선 그리디한 방법으로 3단계를 거칩니다.

  1. 부분 구역 만들기

     • 우선 최대 인구 구역을 가장 적게 해야 가장 많은 구역으로 나눌 수 있을 거라 생각 했습니다. 텔레토비 대비 외계인이 집중되어 사는 구역에서 최대 인구가 나올 것으로 예상 했기에 다음과 같은 과정으로 일단 몇개의 부분 구역으로 나눕니다.
     • 모든 (x,y)에 대해서 주변 (x',y')의 (텔레토비-외계인)을 모두 더한 테이블을 만듭니다. (x-C<=x'<=x+C, y-C<=y'<=y+C)
     • 위 테이블에서 우선순위큐를 이용해 (텔레토비-외계인)이 작은(외계인이 많은) 순서대로 (x,y)를 꺼냅니다. (x,y) 주변 4셀 중에서 (텔레토비-외계인)이 큰 셀을 찾아 두 셀을 합쳐 하나의 구역으로 만듭니다. (이미 한 셀에서 텔레토비가 외계인보다 많거나 특정 확률 P로 합치지 않고 한 셀로 구역을 생성합니다.
     • 이렇게 하면 1~2 크기의 작은 구역들로 나눠지게 됩니다.

  2. 각 구역의 외계인이 텔레토비보다 많도록 부분 구역 합치기.

     • 1에서 만들어진 각 구역들을 순회하면서 현재 텔레토비보다 외계인이 많다면 인접한 구역 중에서 합쳤을 때 텔레토비가 외계인보다 많아지는 구역을 찾아 서로 합칩니다. 만약, 텔레토비를 더 많게 하는 구역이 없다면 인접한 구역 중에서 (텔레토비-외계인)이 가장 큰 구역을 선택해서 합칩니다.
     • 이 과정을 모든 구역의 텔레토비가 외계인보다 많아질 때까지 반복합니다.

  3. 구역들의 (최소인구*5>최대인구)가 되도록 부분 구역 합치기

     • 2에서 모든 구역의 (텔레토비>외계인) 조건은 만족했으니 이제 (최소인구*5>최소인구) 조건을 만족시키기 위해 구역들을 다시 합쳐봅시다.
     • 각 구역들을 순회하면서 (구역인구*5<=최대인구)라면 인접한 구역 중 가장 적은 인구의 구역을 찾아 서로 합칩니다. 이 과정을 최대 인구 조건을 만족할 때까지 반복합니다.
     • 여기까지 1~3을 거쳐 만들어진 구역이 한 결과가 됩니다.

  4. 변수 최적화

     • C와 P를 랜덤변수로 하여 제한 시간동안 1~3 과정을 반복하여 더 많은 구역으로 나뉜 결과를 출력합니다. C=2~4, P=0.3~0.9 범위 내에서 선택해서 반복 했을 때 가장 높은 점수가 나오더군요.

  5. 기타

     • 마지막 결과를 출력하기 전에 한 구역의 특정 2점을 잡아 2구역으로 나누고 조건을 만족하면 구역을 나누는 방법을 써보기는 했습니다만 크게 효과는 없었습니다. 간혹 +1이 되긴 합니다.
     • 버그가 있는지 0점이 나오는 케이스가 종종 보입니다 -_-

  
  12년 전 link

• 
  MiNu

  4000개가 더 돌아가다니ㅠㅠㅠ 순위 변동 가능성이 보입니다.

  
  12년 전 link

• 
  일루

  채점시스템에 문제가 있어보이네요; 검증중입니다

  
  12년 전 link

• 
  일루

  정확히는 특정 조건에서 미누님의 서미션이 0점으로 채점이 되는데, 연속된 케이스들에서 0점이 나오는 경우가 있습니다. 이유는 알아보고 있습니다. 다른 분들 채점은 정상적일 확률이 높지만 이유가 파악되면 처음부터 다시 돌릴 것 같아요.

  
  12년 전 link

• 
  MiNu

  저도 생각해 봤는데 아마 시간 초과로 연속된 0점이 나올 수도 있을것 같습니다.
  제가 사용한 타이머로는 5.2초까지 돌려도 채점시스템에서 4.9초 정도에 끝나는 것 같았거든요. 그래서 타이머를 5.1초로 좀 빡빡하게 잡았는데 그게 문제가 되지 않을까도 싶습니다 흑.

  이래저래 제가 일루님을 번거롭게 해드리는거 같네요ㅋㅋ

  
  12년 전 link

• 
  일루

  5.1초인데 왜 4.9초에 끝나는지가 미지수군요...

  
  12년 전 link

• 
  hyunhwan

  아마 real과 wall의 차이가 아닌가 싶긴 합니다. 우선 문제가 된다고 일루님께서 이야기 하신 시드에 대해서 동일 환경에서 sandboxing을 하지 않고 돌려봤을 때의 결과는 다음과 같이 나왔습니다.

  real    0m5.118s
  user    0m1.868s
  sys 0m0.008s
  

  
  12년 전 link

• 
  Taeyoon_Lee

  일로몬의 선택은...!?

  
  12년 전 link

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