« プロジェクトオイラーを遊び倒すガイド(中級編) | メイン | +と-の電荷が引き合わない例が見つかった »

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


これまで、初級編中級編の2問を題材に説明してきました。最後は、さらに難度の上がった問題を解きます。上級編の問題はこれです。

【上級問題】 6枚のタイルが横1列に並んでいる。 いま、左端のタイル(S)上に1匹のバッタがいる。バッタは次のルールにしたがってジャンプを繰り返し、右端のタイル(G)に向かう。
・バッタは右または左方向にジャンプする。任意の枚数のタイルを飛び越え、他のタイルに着地する。
・バッタはジャンプすると、次はその反対方向にジャンプする。
・バッタはGに到着する前に、他のすべてのタイルにちょうど一度ずつ着地する。Sは始めから着地済みとみなす。
このようにGへ到着する仕方は、全部で5通りある。
20枚のタイルが横1列に並ぶとき、Gへ到着する仕方は何通りあるか?

前の2問とかなり雰囲気が異なる問題です。こうしたいわゆる数え上げの問題も、プロジェクトオイラーではよく出題されます。

さて、どうすれば解けるでしょうか。とりあえず、紙にペンで20個のタイルを書いてみるわけですが、膨大なパターンを数えないといけないことに気付きます。どう数えたらよいか、途方に暮れる人もいるのではないでしょうか。

問題をサイズダウンする

そんなときに有効な考え方として、「大きすぎる問題を小さな問題に分割する」やり方を試してみましょう。問題のサイズを一回り小さくすることによって、再帰的にパターン数を表せないか考えるわけです。

問題サイズを小さくするというのは、この場合は途中経過の様子を思い浮かべることを意味します。こうしたことを考えながら、しばらく図を眺めてみると、ある事実に気がつきます。結局のところ、Gへ着くパターン数は、「バッタの左側にある未訪問のタイル数と、右側にある未訪問のタイル数」のみによって決まっているのです。下の2つの例(訪問済みのタイルを水色で示しています)のように、バッタの左と右にある未訪問のタイル数さえ一緒なら、このあとGに着くパターン数は同じになるのです。

この事実に気が付けば、バッタの左と右の未訪問タイル数が left と right のときのパターン数を求める get_count(left, right) という関数を作ればよいと分かります。関数内では、次の一手によって場合分けして、それぞれ対応する引数で get_count を再帰的に呼んでやります。

コードは以下です。

#include <stdio.h>
#define N 20

long long get_count(int left, int right)
{
  long long count = 0;
  if (left == 0 && right == 0) return 1;
  if ((left + right) % 2 == 0) {  // 右にジャンプする
    for (int i = 0; i < right; i ++) {
      count += get_count(left + i, right - 1 - i);
    }
  } else {  // 左にジャンプする
    for (int i = 0; i < left; i ++) {
      count += get_count(i, left + right - 1 - i);
    }
  }
  return count;
}

int main(int argc, char* argv[])
{
  long long count = get_count(0, N - 2);
  printf("%I64u\n", count);
  return 0;
}

しかしながら、実行しても、何時間経っても一向に終了しません。どうやらさらにもう一ひねりが要るようです。

メモ化探索による改良

そもそも上のプログラムは、バッタの次の可能な行き先ごとに get_count を繰り返し呼びます。その先では、さらにその次の可能な行き先ごとに呼びます。つまり、計算を進めるごとに、関数を呼ぶ回数が爆発的に増えてしまうのです。これが、いつまで経っても終わらない理由です。

そこで、「メモ化探索(メモイズ)」というプログラミングのテクニックを使うことにしましょう。メモ化探索とは、過去に行った計算結果をキャッシュしておいて 同じ引数の計算に対して高速化を計ることを言います。

ある left と right の組み合わせのときの関数の結果を覚えておく2次元配列 memo を用意しました。始めに要素を -1 で初期化しておき、get_count() の先頭でキャッシュが計算済みかを調べます。改良後のコードは次の通りです。

#include <stdio.h>
#define N 20
#define UNDEF ((long long)(-1))
long long memo[N][N];

long long get_count(int left, int right)
{
  if (memo[left][right] != UNDEF) return memo[left][right];
  memo[left][right] = 0;
  if (left == 0 && right == 0) return 1;
  if ((left + right) % 2 == 0) {  // 右にジャンプする
    for (int i = 0; i < right; i ++) {
      memo[left][right] += get_count(left + i, right - 1 - i);
    }
  } else {  // 左にジャンプする
    for (int i = 0; i < left; i ++) {
      memo[left][right] += get_count(i, left + right - 1 - i);
    }
  }
  return memo[left][right];
}

int main(int argc, char* argv[])
{
  for (int i = 0; i < N; i ++)
    for (int j = 0; j < N; j ++)
      memo[i][j] = UNDEF;  // キャッシュの初期化
  long long count = get_count(0, N - 2);
  printf("%I64u\n", count);
  return 0;
}

さて、結果はどうでしょうか。

すぐに答え 2404879675441 が得られました。

さらに優れた洞察

もしあなたが、「結局これって、オイラー数(通称ジグザグ数)を求めればいいだけじゃないの?」と気づいたのであれば、さらにずっと短い手順で答にたどり着くことができます。詳しくはこちらなどを参照して下さい。

以上、3つの例題を使ってプロジェクトオイラーの問題を解いてみました。実際の問題は、これよりもずっと複雑なコーディングや、難しい数学の知識を必要とするものが多く出題されてます。ランキングの上位を狙うもよし、素晴らしいアイデアをフォーラムに投稿するもよし、いろんな遊び方を試してみてください。

最後に僕自身の思いを。プロジェクトオイラーのよいところは、解くのに制限時間が設けられていない点だと思っています。急いで答えを出すプレッシャーがなく、リラックスして問題に挑めるし、また電車内や待ち時間にぼんやりと解法を練ってもよいです。また、複雑なプログラムを細かくデバッグして、やっと正解が得られたときの満足感は、テレビゲームよりもずっと高いと思ってます。全問正解にはまだ何十問か足りませんが、いずれ世界トップにこれたらいいなあ。

(20151022追記:コードのコメントの誤りを修正しました。)

トラックバック

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