google code jam 2009 풀이

google code jam 2009년 문제.

* AllYourBase

C#이나 Java에서
double Match.pow(double, double)
만 제공을 한다.

해서 pow(5,23) 처럼 int의 범위를 넘어가는 큰 수의 경우 pow(double,double)은 부정확한 값을 리턴 할 수 있다.
위키에 따르면
double은
sing 1 bit
exponent 11 bit
significand 52 bit
이렇게 64 bit로 이루어진다.

즉, double이 significan가 표현할수 있는 수의 범위는 2^52승이 한계라는 말이다.
헌데 pow(5,23)같은 경우는 2^53을 넘어가는 범위에 있으므로 double버전의 pow로는 정확한 값을 계산해 낼수 없다는 얘기다.

그래서 long 버전의 pow(long,long)을 구현하거나 쓰는 것이 key인 문제였다.

* CenterOfMass

double은 의외로 오차가 많다. 특히나 정밀도를 요하는 계산에서.
문제에서 Any answer with absolute or relative error of at most 10^-5 will be accepted. 이것이 key이다.

* bribe the prisoners

1. P=10000이고 Q가100일 경우 가능한 경우의 수는 100! 이므로 bruteforce로는 시간적 한계가 있음.  large set 문제는 무식하게 풀면 풀지 못함.
2. 이런 종류의 문제를 DP 문제라고 함. 정확히 catch는 못했지만 정확한 알고리즘이 없을 경우이고, recursive이면서, 반복될 확률이 높은 경우에 cache 를 적용해서 DP 문제라고 하는 것 같음. 
3. log를 남기는 것도 큰 퍼포먼스 감소를 가져오므로 large일때는 로그도 끌것