« プロジェクトオイラーを遊び倒すガイド(初級編) | メイン | プロジェクトオイラーを遊び倒すガイド(上級編) »

プロジェクトオイラーを遊び倒すガイド(中級編)


今回は、初級編からさらに一歩進んだ難度の問題を解いてみます。中級編の問題はこれです。

【中級問題】 344 という数は面白い性質を持っている。 344 の平方根を小数表示した √344 = 18.547236990・・・ は、小数点を無視すると、先頭の9桁に1から9までの数字がちょうど一度ずつ現れる。344 はこのような性質を持つもっとも小さな整数である。 31078 もこの性質を持つ。√31078 = 176.28953457・・・である。31078 はこの性質を持つ10番目に小さな整数である。 この性質を持つ160万番目に小さな整数を求めよ。

初級編と比べて、すこし複雑になりました。うまく解くにはいくらか工夫が必要になります。

単純なアプローチではうまくいかない

さて、この問題はどのように解けばよいでしょうか?

単純に考えると、344 以上の数について、片っぱしから、条件を満たすかどうか調べるやり方が思いつきます。まずはこの方法でやってみることにしましょう。

条件を満たしているかのチェックには少しプログラミングの腕が必要です。ここでは、C 標準関数の sqrt() を使って平方根の小数表示を得たあとで、整数部分が9桁になるまで小数点を右に移動させ、それを unsigned int 型にキャストして小数部分を落とします。次に1~9の各数字が使われたかを記録する bool 型の配列を用意して、各桁が他と重複していないか調べます。どれも重複していなければ、条件を満たしていると判定します。

以上の手順をコードに書きました。is_root_pandigital() という関数で、平方根が条件を満たすかのチェックを行っています。また、count という変数で、見つかった個数をカウントしています。count が 10000 増えるごとに進捗状況を出力させています。

#include <stdio.h>
#include <math.h>
#define N 1600000

bool is_root_pandigital(unsigned int n)
{
  double r = sqrt((double)n);
  while (r < 100000000.0) r *= 10.0;
  unsigned int m = (unsigned int)r;
  bool b[10];
  b[0] = true;  // ゼロは現れてはならない
  for (int i = 1; i < 10; i ++) b[i] = false;
  for (int i = 1; i < 10; i ++) {
    if (b[m % 10]) return false;
    b[m % 10] = true;
    m /= 10;
  }
  return true;
}

int main(int argc, char* argv[])
{
  int count = 0;
  for (unsigned int n = 1; ; n ++) {
    if (is_root_pandigital(n)) {
      count ++;
      if (count % 10000 == 0) printf("%d %u\n", count, n);
      if (count == N) {
        printf("%u\n", n);
        break;
      }
    }
  }
  return 0;
}

さて、コードを実行してみましょう。

3分後の出力が上です。見ての通り、たった17万個しか見つかっていません。このペースだと、160万番目が見つかるのは約半時間後ということになってしまいます。

ここで、プロジェクトオイラーのもう一つの重要なルール、「1分ルール」について説明します。1分ルールというのは、「工夫したプログラムを書けば、たとえ低速なマシンでも1分以内の実行時間で正答を得ることができる」という原則のことです。プロジェクトオイラーで出題される問題は、すべてこの原則にもとづいて作成されています。

つまり、上のような何十分もかかるプログラムは、出題者の期待するレベルに達していないということです。

ではどうすればよいか? 一つは、ひたすらプログラムの完了を待つというものです。もちろん、これでも正答を得ることは可能ですし、こうしたやり方が禁止されているわけではありません。ですが今回はせっかくですので、1分ルールを満たすようにプログラムを改良してみましょう。

改良:固定する数を変える

とは言っても、一体どこをどう改良すればよいのでしょうか? 整数をしらみつぶしに探すというさきほどのアプローチは非効率すぎたわけです。発想を変えましょう。整数を選ぶのではなく、「先頭に1~9が一度ずつ現れる数をまず固定する」と考えてみましょう。

どういうことか? 17923.4658 という数を例にとります。これは先頭の9桁に1~9が一度ずつ現れる数です。ここで、「平方根が 17923.4658・・・ となるような整数は何か?」と考えるのがこのアイデアのポイントです。このような整数を探すのは容易です。17923.4658 ≦ √n < 17923.4659 を満たすような整数 n を探せばよいわけです。各辺を2乗すれば 321250626.28376964 ≦ n < 321250629.86846281 ですから、そのような n は 321250627、321250628、321250629 の3つだと分かります。

つまり、先頭に1~9が一度ずつ現れる数を小さい順に生成し、それぞれに上の手続きを使って n を求めればよいということです。

以上の内容をプログラミングしました。1~9が一度ずつ現れる数を小さい順に生成するのは少し大変ですが、順列生成としてよく知られた手順ですので、自作したり、うまくネット上のコード(ここなど)を再利用したりして下さい。下記では STL の next_permtation() を使いました。

また、同じ数を重複カウントしてしまわないように、未カウントの最小の整数を n_next に記録しました。

#include <algorithm>
#include <stdio.h>
#define N 1600000

int main(int argc, char* argv[])
{
  int count = 0;
  for (int d = 100000000; d > 0; d /= 10) {
    char c[] = "123456789";
    unsigned int n_next = 1;
    do {
      int m = atoi(c);
      double d0 = (double)m / d;
      double d1 = (double)(m + 1) / d;
      unsigned int n0 = (unsigned int)(d0 * d0) + 1;
      unsigned int n1 = (unsigned int)(d1 * d1);
      if (n0 < n_next) n0 = n_next;
      for (unsigned int n = n0; n <= n1; n ++) {
        count ++;
        if (count % 10000 == 0) printf("%d %u\n", count, n);
        if (count == N) {
          printf("%u\n", n);
          goto end;
        }
        n_next = n + 1;
      }
    } while (std::next_permutation(c, c + 9));
  }
end:
  return 0;
}

実行結果は次のとおりです。

一瞬で答え 3951343689 が得られました。

と、発想を変えるだけで、圧倒的に早く答を得られるようになったことが分かると思います。プロジェクトオイラーでは、素朴なアプローチではうまくいかず、高速化が必要になる問題が出てきます。すでに正解した問題でも、1分ルールを満たすようにアプローチを変えたり、より高速になるようプログラムを改良したりするのも面白いですね。

なお、プロジェクトオイラーでは、正解者専用の掲示板が各問ごとに設けられています。他の参加者の優れたアイデアを学んだり、自分のプログラムを披露したりするのも楽しいでしょう。

以上で中級編の説明を終わります。次回は、さらに難度が上がり、ぱっと見ただけではアプローチが思い浮かばない上級編に取り組んでいきます。

トラックバック

このエントリーのトラックバックURL:
http://www.riverplus.net/cgi/mt/mt-tb.cgi/3035