Google code jam 2010 Qualification Round : Problem B

Problem : http://code.google.com/codejam/contest/dashboard?c=433101#s=p1

역시나 어려운 부분은 문제 해석이었다.;;
이 문제에서는 새로운 시간개념 사용(기존 시간과 별다를게 없지만, 자칫 헷갈릴수도 있다.)
Event 중복값 처리(필자는 some i, j에 대해 ti tj가 다르다고 한것을 모든 i, j로 잘못해석해서 디버깅이 귀찮아졌다.)
Big Set에서 64비트 초과하는 값을 Deal하는 방법이 관건이었다.

결국 64bit 초과하는 입력에 대해서는 풀지 않았지만, 알고리즘 및 솔루션은 갖고 있다.
1. 해당 숫자를 문자열로 받은뒤에 x자리만큼 파싱해서 int array에 담는 방법이다.)
2. 정확한 구상은 안해봤지만 대략 10자리씩 int 배열 10개정도면, 향후 reuse 측면에서도 충분하지 않을까 생각한다.
3. 향후 재사용을 생각한다면, 소수점 이하도 처리해주는게 좋을 것같다.
4. 소수점 이하자리도 10자리씩 5~10개정도면 충분히 표현할 수 있을것같다.(그 이하로 하는 범위에서는 반올림 혹은 버림을한다.)




문제의 접근
Event 입력의 중복값을 일단 제거하는게 선행되어야 한다.
Event 입력값들의 차이에 대한 최대 공약수가 y만큼의 시간이 흘렀을때인 Tx+y값들의 최소 공배수(M)가 된다.(x는 index라고 생각하면 된다 ex>첫번째 이벤트시간 T1+y)

최소공배수를 구했다면 Event중 가장작은 min값까지의 시간을 a*M >= min 이되는 a값을 찾고,
a*M - min을 해주면 y값을 구할 수 있다.

아래는 구글 code jam 홈페이지에 나와있는 분석내용 이다.
Let's simplify the problem and just look at two numbers a and b. In this case we need to find the largest T so that some positive y exists where a + y and b + y are multiples of T. So (a + y) modulo T = (b + y) modulo T which means that (a - b) modulo T = 0. Thus Tmust be a divisor of |a - b|.


이하 소스
(64bit로 하면 라지셋이 커버될거라 생각했는데 한참 부족했다.)

 
 // 중복값제거를 위해 set사용  
    for(int i=0; i<numOfEvent; i++)  
    {  
       //STL을 사용할때 파일에서 바로 insert하는   
        //방법을몰라서 tmp에 넣은후에 insert 했다.  
       file >> tmp;  
       Event.insert(tmp);   
       if( tmp < minEvent || minEvent==0)  
           minEvent = tmp;  
     }  
     // iterator 하나를 사용해서 첫번째 값과 두번째값을   
      //서로 연산하는 방법을 몰라서 2개의 iterator를 사용했다.  
     set<__int64>::iterator it=Event.begin();  
     set<__int64>::iterator iter=Event.begin();     iter++;  
     set<__int64>::iterator itera=Event.begin(); itera++; itera++;  
     // Event가 2개인경우 두 이벤트의 차이 자체가 최소공배수가 된다.  
     if(Event.size()==2)  
     {  
          multiple = abs((*it) - *(iter));  
     }  
     else  
     {  
          multiple = cal(abs((*it) - (*(iter))), abs((*it) - (*(itera))) );  
     }  
     //각 Event의 '차'들에 대한 최대공약수  
      for(set<__int64>::iterator i=Event.begin(); i!=Event.end(); i++)  
     {  
          set<__int64>::iterator it=i;  
          it++;  
          for(set<__int64>::iterator j=it; j!=Event.end(); j++)  
          {  
              multiple = cal(multiple, abs(*i - *j));  
          }  
     }       
      //아포칼립스 시간계산 : 이벤트 최소값~최소공배수*n배(n은최소값)의 시간  
      for(int i=1; ;i++)  
     {  
          if(multiple*i >= minEvent)  
          {  
               apocalypse = (multiple*i)-minEvent;  
               break;  
          }  
      }  

 // a와 b의 최대공약수를 구하는 루틴 : 유클리드 호제법이용  
 __int64 cal(__int64 a, __int64 b)  
 {  
      __int64 r, tmp, q;  
      if(a < b)  
      {  
           tmp = a;  
           a = b;  
           b = tmp;  
      }  
      r = a % b;  
      while(r!=0)  
      {  
           q = b / r;  
           r = b % r;  
           b = (b - r) / q;  
      }  
      return b;  
 }