/퍼즐-화물열차

저번 /퍼즐-아군살리기에 이어, 같은 곳에서 본 다른 문제.

[화물 열차]

문제의 조건으로는 컨테이너의 위치가 10^9까지 있을 수 있으니... 이게 열차의 최대 길이라 치고,

1) B열차를 한 칸씩 이동시키면서 그때마다 겹치는 컨테이너의 수를 하나씩 찾아가며 센다:

O(열차길이^2) 형태라 도저히 무리.

2) B열차를 한 칸씩 이동시키되, 그때마다 겹치는 컨테이너의 수를 상수 시간에 계산한다.

이게... 되면 참 좋겠지만, 될 것 같지가 않다.

3) 두 열차에서 컨테이너 구간들 하나씩을 뽑아내어 그 두 구간이 서로 겹치기 위해 필요한 이동횟수들과 그 때마다 겹치는 칸 수를 세어 저장한다. 모든 쌍에 대해 이걸 수행하며 누적하면 이동횟수-겹치는칸수 쌍의 데이타가 완성되니 여기에서 답을 찾는다

내가 시도한 게 이건데, O(A열차의 구간 갯수 * B열차의 구간 갯수 * 구간의 평균 길이) 정도가 소요되어... 구간이 A열차 500개, B열차 1000개가 되는 입력에서 제한 시간을 넘겨버림.

여기서는 저 데이타의 수도 매우 많으므로 저장하는 게 일인데, 해시테이블을 직접 만들어서 써봤음. 이걸 좀 더 잘 고치면 개선의 여지가 있을텐데 적합한 게 뭘지 모르겠다. 근데 일단 500000번의 루프를 도는 것도 일이고...

4) 최대로 겹치기 위한 어떤 충분조건이 있다면 그 조건만 찾으면 되고, 하다못해 필요조건이 있다면 그 조건을 만족하는 경우들만 찾은 후 거기서 뒤지면 될 텐데... 컨테이너가 랜덤하게 위치하는 데 이런 게 존재할 수 있을까?

다음과 같은 조건들은 다 반례를 쉽게 생각할 수 있다

가장 긴 구간끼리 겹쳐야 한다:
      oo_oo_ooo
oo_oo_______ooo


겹치는 구간의 갯수가 많아야 한다:
o_o_o_oooo
o_o_o_____oooo

짧은 열차가 긴 열차 안에 완전히 들어오는 형태여야 한다:
    ooooo__o
o___ooooo

Comments & Trackbacks

2진수의 convolution을 FFT로 구하면 O(n log n)인데, KOI 고등부니까 이건 못쓰겠군요.

FFT는 푸리에 변환 말씀인가요;; 학부 공학수학 이후로 손 대 본 적이...

그리고 전혀 반복이나 규칙이 없는 시퀀스인데도 변환할 여지가 생기나요?

-- Raymundo 2013-1-22 2:29 am

2)의 경우에는 열차를 2진수로 표현하고 두 열차를 XOR 연산하면 되겠네요. 각 경우마다 답을 미리 계산하고, char 단위로 처리하면 가능할지도?

근데 그 2진수의 비트수가 최대 10억개... int단위로 처리해도 3천백만개...

-- Raymundo 2013-1-25 2:41 pm

http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

O(1) 시간에 1의 갯수를 셀 수 있네요...

오잉 =ㅅ=;;; 저거 좀 읽어보고 해봐야겠어요

-- Raymundo 2013-1-25 2:49 pm

아주 간간히 와보게 되어서 문제를 풀지는 못하고 뻘소리만 하는데, 문제의 기술 자체가 (1), (2)로 풀지 말라고 하고 있네요. 구간들을 트리로 표현하고 잘 하면 깔끔하게 풀릴 거 같은데 지금 보고서 300장을 써야 해서....

몇달만에 답을 올리는데,

101110이 있다면 [1,1] [3,5]와 같이 구간으로 표현합니다. 수가 둘이 있으니까 둘 중 구간이 많은 쪽을 m이라고 합시다.

한쪽을 가지고 각 구간을 segment tree에 넣습니다. O(m log m) 시간에 다 넣을 수 있습니다.
다음, 다른 구간들을 차례대로 이 tree에 질의를 하면서 겹치는 부분의 수를 구합니다. 선분이 이동할 때, 체크해야 할 노드 개수가 상수개인지 log m개인지는 좀 헷갈리는데; 어쨌든 이렇게 하면 O(n m log m) 시간에 풀 수 있겠네요. 물론 m log m << n이어야 이 솔루션이 brute force보다 나을 겁니다.

저도 몇 달 동안 방치했던 건데ㅎㅎㅎㅎ 다시 시간 날때 도전해볼게요.

-- Raymundo 2013-4-17 3:35 pm

그런데 결국은 B열차가 한 칸 움직일 때마다 이 쿼리를 전부 새로 해줘야 하는거죠? n이 열차의 길이를 말씀하신 거고요. 길이가 너무 긴 게 영 걸리는군요.

-- Raymundo 2013-4-21 2:54 am

잘 생각해보면, B 열차가 움직일 때마다 단 두개의 트리 노드만 바뀝니다.

안녕하세요 지나가다가 우연히 블로그에 들러서 문제에 흥미를 가지고 몇 시간 끙끙대다가 결국 풀어서 풀이 써놓고 갑니다... 오랜만에 머리 써보네요 ㅎㅎㅎ

#include "stdio.h"
#include "algorithm"
using namespace std;

int N,M; //열차의 개수
int x[1000][2],y[1000][2]; //열차의 정보
int sum,maxvalue,move,slope; //그래프에서 변수들
int i,j,k;

struct G{int p,s;}; //position, slope
G grp[4000000]; //그래프 정보 저장

int f(G temp1,G temp2){return temp1.p<temp2.p;} //정렬 함수

int main(){
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%d%d",&x[i][0],&x[i][1]);

scanf("%d",&M);
for(i=0;i<M;i++)
scanf("%d%d",&y[i][0],&y[i][1]);

for(i=0;i<N;i++)
for(j=0;j<M;j++){
grp[k].p=x[i][0]+y[j][0]-2; grp[k++].s++;
grp[k].p=x[i][0]+y[j][1]-1; grp[k++].s--;
grp[k].p=x[i][1]+y[j][0]-1; grp[k++].s--;
grp[k].p=x[i][1]+y[j][1]; grp[k++].s++;
}

sort(grp,grp+k,f);

for(i=1;i<k;i++){
slope+=grp[i-1].s;
sum+=(grp[i].p-grp[i-1].p)*slope;
if(maxvalue<sum){
maxvalue=sum;
move=grp[i].p;
}
}

printf("%d",move);
}

커헉 아무 생각없이 저 사이트에서 채점시켰다가 바로 통과되어 버렸습니다. 아이구 남의 코드로 통과를 해 버렸네요. OTL

제가 어디에서 타임아웃 걸리는지 비교하면서 공부해야겠어요. 감사합니다.

-- Raymundo 2013-7-22 10:31 pm

slope 이게 핵심이군요. 굳이 일일이 겹치는 횟수를 한칸 이동할 때마다 저장해둘 필요가 없었는데... 정말 잘 배웠습니다.

-- Raymundo 2013-7-23 1:56 am

이름:  

Homepage:

내용:
 

---

주인장분류