Single Round Match 413 Div1

TopCoder

今回からDiv1で戦うことになりました。うは、みんな青とか黄色とか赤だ(当たり前)
ここにいる全員が僕よりコードの書ける人だと思うとなんかすごいな。

500点問題、回答した18人のうち14人がチャレンジされて落とされている。僕を含む。一見簡単なように思えて、見えにくい所に落とし穴があるのか。ちなみに僕の解答：

  int P, Q, X, Y;
  map<long long, long long> cache;
  long long calc(long long n, int p, int q, int x, int y) {
    P = p; Q = q; X = x; Y = y;
    return calc(n);
  }
  long long calc(long long n){
    if(n <= 0) return 1;
    if(cache.find(n) != cache.end()){
      return cache[n];
    }
    long long t1 = n / P - X, t2 = n / Q - Y;
    return cache[n] = calc(t1) + calc(t2);    
  }

落ちてない人のコードを見たらlong long cache[1000000]とかやってるなぁ。

        • -

キャッシュをmapじゃなくてlong long[1000000]に変えたらシステムテスト通った。うーむ。mapは避けるべきか。

        • -

250点問題しか解けていないのにレーティングが120くらい上がった。しばらくは250点問題を着実に解くことを目指せばいいのかな。250と500を着実に解くだけで黄色をキープできるらしいし。