Diary/퍼즐-화물열차 페이지의 소스 보기

내용출력
로그인[l]
수정할 수 없습니다: Diary/퍼즐-화물열차 는 읽기 전용 페이지입니다.
#TEMPLATE [[Diary/DynamicTemplate]]
<div class="diary">
== [[/퍼즐-화물열차]] ==

저번 [[/퍼즐-아군살리기]]에 이어, 같은 곳에서 본 다른 문제.
: [http://211.228.163.31/pool/koi_freight/koi_freight.php?pname=koi_freight 화물 열차]

문제의 조건으로는 컨테이너의 위치가 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
}}}

<mysign([[Raymundo]],2013-1-21 3:33 am)>

===== Comments & Trackbacks =====

2진수의 convolution을 FFT로 구하면 O(n log n)인데, KOI 고등부니까 이건 못쓰겠군요. <mysign(inboklee,2013-1-22 12:45 am)>

: FFT는 푸리에 변환 말씀인가요;; 학부 공학수학 이후로 손 대 본 적이... \\
 \\
그리고 전혀 반복이나 규칙이 없는 시퀀스인데도 변환할 여지가 생기나요? <mysign([[Raymundo]],2013-1-22 2:29 am)>

2)의 경우에는 열차를 2진수로 표현하고 두 열차를 XOR 연산하면 되겠네요. 각 경우마다 답을 미리 계산하고, char 단위로 처리하면 가능할지도? <mysign(inboklee,2013-1-25 2:33 pm)>

: 근데 그 2진수의 비트수가 최대 10억개... int단위로 처리해도 3천백만개... <mysign([[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의 갯수를 셀 수 있네요... <mysign(inboklee,2013-1-25 2:41 pm)>

: 오잉 =ㅅ=;;; 저거 좀 읽어보고 해봐야겠어요 <mysign([[Raymundo]],2013-1-25 2:49 pm)>

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

몇달만에 답을 올리는데,  \\
 \\
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보다 나을 겁니다. <mysign(inboklee,2013-4-17 10:54 am)>

: 저도 몇 달 동안 방치했던 건데ㅎㅎㅎㅎ 다시 시간 날때 도전해볼게요. <mysign([[Raymundo]],2013-4-17 3:35 pm)>

: 그런데 결국은 B열차가 한 칸 움직일 때마다 이 쿼리를 전부 새로 해줘야 하는거죠? n이 열차의 길이를 말씀하신 거고요. 길이가 너무 긴 게 영 걸리는군요. <mysign([[Raymundo]],2013-4-21 2:54 am)>

잘 생각해보면, B 열차가 움직일 때마다 단 두개의 트리 노드만 바뀝니다. <mysign(inboklee,2013-4-22 12:43 am)>

안녕하세요 지나가다가 우연히 블로그에 들러서 문제에 흥미를 가지고 몇 시간 끙끙대다가 결국 풀어서 풀이 써놓고 갑니다... 오랜만에 머리 써보네요 ㅎㅎㅎ \\
 \\
#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); \\
} <mysign(GG,2013-7-22 9:46 pm)>

: 커헉 아무 생각없이 저 사이트에서 채점시켰다가 바로 통과되어 버렸습니다. 아이구 남의 코드로 통과를 해 버렸네요. OTL \\
 \\
제가 어디에서 타임아웃 걸리는지 비교하면서 공부해야겠어요. 감사합니다. <mysign([[Raymundo]],2013-7-22 10:31 pm)>

: slope 이게 핵심이군요. 굳이 일일이 겹치는 횟수를 한칸 이동할 때마다 저장해둘 필요가 없었는데... 정말 잘 배웠습니다. <mysign([[Raymundo]],2013-7-23 1:56 am)>
<longcomments(100)>
----
[[주인장분류]]
</div>
Diary/퍼즐-화물열차 페이지로 돌아가기 | 다른 수정본 보기