連載
» 2010年03月06日 00時00分 UPDATE

最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (3/5)

[高橋直大,ITmedia]

今回の問題

 具体例に関してはまだ示していないので、少し数学的なものとなりますが、「動的計画法やメモ化再帰における本質的な部分」を理解してもらえるような問題を示します。TopCoder SRM413 Div1Mediumからの出題です。

Let's consider an infinite sequence A defined as follows:

* Ai = 1 for all i <= 0;

* Ai = A[i/p]-x + A[i/q]-y for all i >= 1, where [x] denotes the floor function of x. (see Notes)

You will be given n, p, q, x and y. Return the n-th element of A (index is 0-based).

Constraints

- n will be between 0 and 10^13, inclusive.

- p and q will both be between 2 and 10^9, inclusive.

- x and y will both be between 0 and 10^9, inclusive.

 これを簡単に訳すと、このような感じでしょうか。

A[i]に関して、

  • i<=0のとき、A[i] = 1
  • i>0のとき、A[i] = A[i/p-x] + A[i/q-y]

と定義する。n、p、q、x、yが与えられた時、A[n]を求めなさい。

ただし、nは10^13以下、p,qは2以上10^9以下、x、yは0以上10^9以下とします。

 今回の問題についても、取り組みやすいように、問題挑戦用のソースコードを用意しました。問題側で設定されたサンプルデータが前半に4つと、本当に正しいかどうかを検証するための凶悪なデータが後半に2つあり、それぞれ自動でチェック可能になっていますので、気軽に挑戦できます。C++、C#、Javaの3種類を用意しましたので、好きな言語で挑戦してみましょう。

 なお、今回の問題には、重要な注意点があります。すべてのケースで正答を出せたとしても、そこで満足しないでください。重大な落とし穴にはまっている危険性があります。必ず次ページの解説編を確認してください。

今回の問題のヒント

 今回は非常にシンプルな問題を選びましたので、これ以上説明の必要がない方も多いでしょうが、そうでない方のために、取っ掛かりとなるようなヒントを示します。

 どんな形式の問題であれ、グラフに変形させてしまえば後は似たような問題に帰着できることはすでにこの連載で述べたとおりです。「幾つかのパターンに当てはめる」といった発想が出てくるのはこれに起因する部分も多いです。類似の問題に帰着させることは非常に大切ですが、そればかり考えていると、発想が貧困になってしまったり、つまらないケアレスミスをしてしまうことが増えてしまうので、どのように解けばよいかをきちんと考えるようにしましょう。

 ここで、適当に小さい数字で幾つかのケースについて試してみましょう。n=50、p=2、q=3、x=4、y=1で図を書いてみると以下のようになります。

 何だか見慣れた形の図になりましたね。こうすることで、前回同様、探索すればあっさりと解けてしまうのではないか、と思えるのではないでしょうか?

 ですが、今回気をつけなければいけないのは実行時間です。nが10^13まで許されてしまうので、1つずつ答えをカウントしていくような回答ではまったく間に合いません。例えばp=q=2、x=y=0などにした際、最下段には必ずn個以上の0が並んでしまうため、オーダーはO(n)かそれ以上になってしまいます。そもそも解が1億以上のものが存在してしまうような問題では、1つずつ数え上げるような手法は使えないと考えてください。

 では、メモ化再帰ではどうでしょう? 上図では、同じ数字が幾つか出現しています。当然ながら、これはまったく同じものですので、この下から出てくる数字も同じとなります。よって、これを記憶していくことで、実行時間を大幅に削減できます。

 しかし、ここで別の問題が生じます。メモリ確保の問題です。いままでほとんど気にしたことはありませんでしたが、前記実装を配列を用いて行う場合、非常に単純に実装すると、A[0]からA[n]までの実行結果をメモしておかなければなりません。

 TopCoderでは、条件を満たすどんな問題に対しても、64Mバイト以内のメモリの使用で、2秒以内に答えを返さなければなりません。この実行時間とメモリのジレンマをいかに解決できるかが、今回の鍵となります。

 もちろん、動的計画法を用いて近いところまで到達することは可能です。i/p-xとi/q+yの2式は、それぞれiより必ず小さくなるので、iより小さいjに対してA[j]が確定していれば、A[i]を求めることができます。よって、A[0]から1つずつ計算していくことで、A[n]を求めることができるわけです。ただし、こちらも同様にA[n]までを記憶していく、つまりn個分のメモリを確保しなければならないので、あまり現実的ではありません。また、1つずつ順番に求める必要があるので、時間もO(n)掛かってしまい、今回の問題に適しているとは言いがたいでしょう。

 それでは、次のページから解説に移りたいと思います。

Copyright © ITmedia, Inc. All Rights Reserved.

ピックアップコンテンツ

- PR -

注目のテーマ

マーケット解説

- PR -