　データ構造に関してはまだこの連載で取り上げていませんので、ここでは詳しく説明しませんが、適当な連想配列dicに対して、dic[i] = j;とすれば、dic[i]の中にjが入っていて、iの領域を気にすることがない便利なもの、程度にとらえていただければ構いません（ただし、今すぐ使用したい場合は、検索などで調べてからの使用を推奨します）。

　C#の連想配列であるDictionaryを用いて1つ前のソースコードを書き換えると、以下のようになります。


using System;
using System.Collections;
using System.Collections.Generic;
public class InfiniteSequence2 {
    Dictionary dic;
    public long calc(long n, int p, int q, int x, int y)
    {
        dic = new Dictionary();
        return saiki(n, p, q, x, y);
    }
    long saiki(long n, int p, int q, int x, int y)
    {
        if (n <= 0) return 1;
        if (dic.ContainsKey(n)) return dic[n];
        return (dic[n] = saiki(n / p - x, p, q, x, y) + saiki(n / q - y, p, q, x, y));
    }
}

連想配列を利用したメモ化再帰

　ほんの少しの書き換えで連想配列を利用したメモ化再帰に変更できました。こうすることで、一度も訪れない数字に対してメモリを割く必要もなくなり、メモリの使用量を大幅に減らせます。このような方法は、記憶範囲が飛び飛びになった場合によく使われる方法なので、覚えておくと戦術の幅が広がります。

　さて、確かにこの方法を利用すれば、メモリの使用量を直感的にもかなり減らすことが可能です。では、メモリの使用量はいったいどれくらいになるのでしょうか？　ほとんどの方はここまで計算しないと思いますし、計算も難しいのですが、O（√n）程度までは減らせます。ただし、連想配列では通常より多くメモリを確保してしまうことを考慮すると、O（√n）でもメモリ使用量を少しオーバーしてしまう可能性があります。

　こういった場合は、実際に組んでみて、本当に大丈夫であるかをテストしてみるのがよいでしょう。メモリ使用量を最大とするには、小さい数字が大量に発生をすることを考えれば、大きい数字をばらつかせてたくさん発生させることが重要なので、

p、qは、大きい数字への割り算の影響が大きいので、両方最小の2とする
x、yは、大きい数字への引き算となるため、最初の影響は小さい。ここはばらつかせるために差をつける

といったことを考慮し、例えば、n=10^13、p=2、q=2、x=0、y=123456などのテストケースを考え、TopCoder上で実行させてみると、メモリ使用量がオーバーしてしまうことが確認できます。つまり、TopCoderではこの方法でも、残念ながら不正解というわけです。

初心者でも書ける意外な解決策

　さて、それではどうすればよいのでしょうか。動的計画法やメモ化再帰で、なぜメモリ上に記憶をさせるかというと、「同じところを何度も訪れることで無駄が生じるから」です。それなら、通った状態をすべて記憶できないなら、よく訪れるものだけ記憶すればよいのです。分かってしまえば非常に簡単ですね。

　この問題では、図を見れば分かるとおり、大きな数字より小さな数字が明らかに大量に発生します。それならば、大きな数字のときは普通に探索をし、ある程度小さい数字になったところでメモ化再帰に切り替えればよいでしょう。

　小さい数字を適当に10^6と設定し、ソースコードを書くと以下のようになります。


using System;
using System.Collections;
using System.Collections.Generic;
public class InfiniteSequence2 {
    long[] dp;
    public long calc(long n, int p, int q, int x, int y)
    {
        dp = new long[1000001];
        return saiki(n, p, q, x, y);
    }
    long saiki(long n, int p, int q, int x, int y)
    {
        if (n <= 0) return 1;
        if (n <= 1000000 && dp[n] != 0) return dp[n];
        long res = saiki(n / p - x, p, q, x, y) + saiki(n / q - y, p, q, x, y);
        if (n <= 1000000) dp[n] = res;
        return res;
    }
}

　さて、本当にこの方法で正しいのでしょうか？

　メモリ使用量は、long型の配列を10^6個なので、8バイト*10^6 = 約8Mバイトとなり、条件を満たします。

　一方、実行時間についても、10^6未満とそれ以上に分けて考えると、問題がないことが分かります。10^6未満に関しては、すべて求めてもO（10^6）となり、0.1秒も掛からず終わります。1000000（10^6）より大きな数字に関しては、nから1000000までに変化するまでに発生する頂点の個数を考えれば分かります。この式において、p、qは2以上、x、yは0以上であることを考えれば、子の頂点の数字の和が、親の頂点の和を超えることは有り得ません。よって、発生する頂点の個数はO（n/10^6）=O（10^7）となり、こちらも2秒の実行時間の制限に引っかかることはありません。よって、このコードでどんなケースにおいても対応できることが分かります。

　なお、再帰専用の関数を削除し、1関数にすると、以下のようにさらにシンプルなものになります。このコードをチャレンジ用のソースにそのまま流用すると、恐らく不正解が返されると思いますが、これは初期化の問題です。TopCoderでは、各々のテストケースを実行する度に初期化を行っていますが、そうではない場合、配列に前の計算結果が残ってしまいますので、注意してください。


using System;
using System.Collections;
using System.Collections.Generic;
public class InfiniteSequence2 {
    long[] dp = new long[1000001];
    public long calc(long n, int p, int q, int x, int y)
    {
        if (n <= 0) return 1;
        if (n <= 1000000 && dp[n] != 0) return dp[n];
        long res = calc(n / p - x, p, q, x, y) + calc(n / q - y, p, q, x, y);
        if (n <= 1000000) dp[n] = res;
        return res;
    }
}

　最終的な回答となったソースコードは非常に短いですが、この回答にたどり着くのはなかなか難しいと思います。使用できるメモリと実行時間を意識して適切なソースコードを書くというのは、TopCoderにおいてはほかの人との差となって現れてきますし、実務においても重要なポイントです。

　今回のポイントは、「メモ化再帰・動的計画法は同じ計算をする無駄を省く」ということに尽きます。それをしっかりと意識できるようになれば、今回のような問題にも立ち向かえるようになるでしょう。

　今回紹介したものよりも美しい実装方針を思いついたり、きれいなコードが書けたら、ぜひご意見ください。ソーシャルブックマークのコメントでも、筆者のブログに書き込んでいただいても構いません。可能な限り反応したいと思っていますので、どんどんご意見をお寄せください。それでは、次回もお楽しみに！

著者プロフィール：高橋直大（たかはし　なおひろ）

Microsoftが主催する技術コンテスト「Imagine Cup」の2008年アルゴリズム部門で世界第3位に入賞した若きアルゴリズマー。TopCoderでは誰もが恐れるRedcoderとして活躍中。2009年に開催された「天下一プログラマーコンテスト」では特別賞を受賞した。現在、慶應義塾大学環境情報学部2年。口癖は「みょんみょん」。

世界でも有数のRedcoder、高橋直大がアルゴリズムの魅力と極意を伝授する「最強最速アルゴリズマー養成講座」はこちらから

トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。
細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック
競技プログラミングはレベルの高い人たちの集まり――そんな考えを持っている初心者の方、TopCoderはあなたのコーディングスキルを爆発的に高める魔法のような場です。今回は、初心者にこそお勧めしたいTopCoderの魅力について考えます。
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」
典型的なアルゴリズムをたくさん知っている人間が最強か――？　いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。
オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。
あなたの論理的思考とコーディング力は3倍高められる
全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。本稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。
高橋直大、Imagine Cupアルゴリズム部門で世界の三強に
フランスの地でアルゴリズムの未来を切り開く男　高橋直大
Microsoftが主催する学生向けの技術コンテスト「Imagine Cup」。そのアルゴリズム部門で世界の頂点に挑むのは、プログラミング歴が2年にも満たない一人の数学好きだった。
アルゴリズムと戯れる元野球少年が手に入れた宝物
Imagine Cup 2008のアルゴリズム部門で世界第3位となった高橋直大氏。彼の軌跡を眺めてみると、わたしたちが忘れてしまったことにすら気づかない何かを思い出させてくれるような気持ちになる。
TopCoderで世界と渡り合う日本IBMの異才――夷藤勇人
もしあなたが美しい（あるいはトリッキーな）コードが飛び交う世界を知りたいと願うならそれはTopCoderに参加することで容易に実現することができる。このTopCoderに参加している数少ない日本人で、生涯プログラマーを宣言する人物にTopCoderの魅力を聞いた。