google code jam 2010 풀이

Rotate

rotate 후, gravity 적용하는것은 그냥 하면 되고
row, column 은 돌면서 K개 연속으로 있는것 체크하면 되고
실수할 수 있는 부분은 대각선인데,
/은 ㅣㅡ (아래)순으로 돌고
\은 ㅣㅡ(위) 순으로 돌면 된다.
대각선에서 실수 할 수 있다.

그리고 시작위치와 속도 를 주면 K개 연속을 detect하는 펑션을 만들면 로직을 단순화 할 수 있다.
풀이를 보고 나서 .

1. 실제로 rotate후 gravity적용하는 것은 왼쪽으로 밀어주면 끝이다. 굳이 rotate하고 gravity적요을 할 필요가 없다 --;; --> 생각을 하자. 젤 중요한 것은 시간 시간이다.
2. N의 max가 50이므로 굳이 최적화 해서 할 필요없이 모든 칸을 돌면서 8방향을 체크하면 된다. --; --> N이 작으면, 최적화 하는 시간보다  bruteforce로 무식하게 하는것이 시간을 더 절약할 수도 있다. 중요한 것은 시간!

Number Game

dynamic programming 문제이고 turn개념때문에 좀 헷갈릴 수 있다.
small set은 cache로 어쩌 해결할 수 있으나 large set은 너무 시간이 걸렸다.
1억번의 빈 루프를 도는 것만 수분이 걸리는데, largeset중에 백만 x 백만 짜리 문제가 있다.-- 이거 머임?


오류들
- B는 모든 k에 대해서 이겨야 하지만 A는 한 k에 대해서만 이겨도 됨..
- turn별로 다른 cache를 사용해야 했는데 그것으로 오류.
- large set은 백만까지 가므로 기존 알고리즘으로는 한계가 있었음.

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일때는 로그도 끌것