Hatena::Grouptopcoder

cou929のTopCoder日記

2009-09-29

SRM449 div2 OddDivisors 再チャレンジ

00:23

前回解けなかった500点問題。他の人のコードを見て、正しさは確認できたんですが、何故そうなるのかが中々理解できませんでした。その後、TopCoderのフォーラムellerさんの日記、そのellerさんの日記の中で言及されていたMishoさんのtweet後輩maka776からのコメントなどを参考にして、なんとか理解できました。皆さんありがとうございます。

この問題のポイントは以下の二点です。

  1. 奇数nのf(x)はn。かつ一つ飛ばしの等差数列になっている。
  2. 偶数部分は一つ飛ばしの偶数のみからなる数列なので、全体を2で割ることで、新たな数列(部分問題)として処理できる。

たとえばN=20の場合、以下のようになります。

  1. (1, 2, ..., 20) -> 奇数部分を処理
  2. (2, 4, 6, ..., 20) -> 全体を2で割る
  3. (1, 2, 3, ..., 10) -> 奇数部分を処理
  4. (2, 4, 6, 8, 10) -> 全体を2で割る
  5. (1, 2, 3, 4, 5) -> 奇数部分を処理
  6. (2, 4) -> 全体を2で割る
  7. (1, 2) -> 奇数部分を処理
  8. (2) -> 全体を2で割る
  9. (1)

奇数部分だけ取り出して計算することは思いつけたのですが、偶数全体を2で割るという方法で問題を部分問題へ分割するという方法は思いつけませんでした。僕の問題の捉え方では、再帰する際はNの偶数すべてを保持する必要があると思い込んでいたので、再帰の際にN/2だけを保持しておけば良いということを理解するのが大変でした。

今回の問題の教訓としては、基本的ですが、なにかの法則性を探すときは、小さい数字から順に手計算で調べてみるというアプローチがあるというところでしょうか。さらに今回の場合は、N=10くらいでぐだぐだ考えていて時間が過ぎていったので、N=20や30くらいまで考えてみても良かったです。また、今回のような法則性の発見(部分問題への分割の仕方)を思いつくには、いろんな問題をといて経験を積むのが良いような気がします。

class OddDivisors {
public:
  long long r(int n)
  {
    if (n == 0)
      return 0;

    int last = n;

    if (last % 2 == 1)
      n--;
    else
      last--;

    return ((last+1)/2)*((last+1)/2) + r(n/2);
  }

  long long findSum(int N)
  {
    return r(N);
  }
};