すずろぐ

人生大逆転を目指す、鈴木俊吾の成長日記

Java CodeIQの結城浩出題「マヨイドーロ問題」の解法と解説

プログラミング

こんばんは、すずしんです。

以前の記事「プログラミングスキルの評価なら「CodeIQ」がおすすめ!」では、プログラミングスキルの評価をしてくれるCodeIQというサイトを紹介しました。 その際に、CodeIQで出題されている問題の中で、結城浩さん出題の「マヨイドーロ問題」という問題がありました。 この問題を私はJavaで解いてみました。

この度、CodeIQではマヨイドーロ問題の解答期間が終了しまして…。 問題作成者の結城浩さんが、ブログなどで解説記事を書いて公開しても良いというアナウンスをしていました。 というわけで、せっかくなので私も記事にして公開してみたいと思います。 そこで今回は、このマヨイドーロ問題の自分なりの解法アルゴリズムについての解説記事を書いてみます。

マヨイドーロ問題とは?

「マヨイドーロ問題」というのは、CodeIQに公開されていた問題の内の1つです。 「Java言語プログラミングレッスン」といったプログラミングの入門書や、「数学ガールの秘密ノート/ベクトルの真実」といった数学ガールシリーズ、などの書籍を出版していることで有名な「結城浩」さんが今回出題しています。

マヨイドーロ問題は、XからBに移動した後、Y,A,B,C,Zの間をN回反復しても良いという条件で移動するとき、Yに到達する行き方は何通りあるか(P)を求めるものです。 Y-A-B-C-Zの順番で位置が設定されていて、それぞれの位置で現在の向きに移動するか、それとも反転して反対方向に進むかを選ぶことができます。 最初のBの移動方向は右向きです。 YやZに到達したら移動は終了となります。 この時、反転して良い回数の上限がNとして入力されます。 このNに対応するPを出力して下さいというのが問題となっています。

N = 0 の場合

例えば、N = 0の時には、XからBに移動した後は反転ができないので右方向に向かうしかなく、結果として以下の経路しかありません。 この場合、Yに到達するパターンが無いのでP = 0となります。

[text] X - B - C - Z [/text]

N = 1 の場合

N = 1とした時は、N = 0の時の経路に加えて1回だけ反転した時の経路が加わります。 BまたはCで反転した時の経路がそうですね。 つまり全部で以下のような移動の仕方があります。 この場合、Yに到達するパターンが2つあるのでP = 2となります。

[text] X - B - C - Z X - B - A - Y X - B - C - B - A - Y [/text]

問題の解き方の方針

まず、このマヨイドーロ問題の特徴として分かるのは…。 移動できる経路のパターン数はNが増えるともちろん増えるのですが、N = nとした時のパターンの中にはN = n - 1の時のパターンが含まれています。 上の例でも挙げましたが、N = 1の時の経路のパターンにはN = 0の時の経路も含まれていますよね。 ということは、求めるPの値もこれに対応するはずです。 すなわち、N = nの時のPの値をP(n)とすると、以下のような関係になっていることが分かります。

[text] P(n) = P(n-1) + p [/text]

これから分かるのは、P(n)を求めるのにはP(n-1)までをまず求め、その結果に加えて「n回のみ反転した時にYに到達した経路のパターン数(p)」を加えてやれば良いということです。 ということは、まずP(0)から始めて、P(1)を求める時にはP(0)の値を参照する、P(2)を求める時にはP(1)の値を参照するということを繰り返していけば、最終的にP(n)を求められそうですよね。 つまり、前回までの計算結果を記録しておいて、必要に応じてその結果を参照しながら反復して解くのが良さそうだと考えました。

解答プログラム(ComplicatedRoads)

これまでを踏まえながら、このマヨイドーロ問題を解くJavaプログラム(ComplicatedRoads)を作成してみました。 ComplicatedRoadsのソースコードは以下のようになっています。 ただ、CodeIQに提出する時には、packageの宣言とクラス名の宣言からpublicを削除する必要があります。 ところで、マヨイドーロの英語表記は「Complicated Roads」で良かったのかな…。

[java] package jp.suzushin7.codeiq;

import java.math.BigInteger; import java.util.HashMap; import java.util.Scanner;

public class ComplicatedRoads { private static final HashMap<String, BigInteger> map = new HashMap<>(); private static final String[] pos = {"Y", "A", "B", "C", "Z"}; private static final int LEFT = -1; private static final int RIGHT = 1;

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    while(scanner.hasNextInt()) {
        int N = scanner.nextInt();
        BigInteger P = solve(N);
        System.out.println(P);
    }
}

public static BigInteger solve(int N) {
    BigInteger p = BigInteger.ZERO;
    for(int i = 0; i &lt;= N; i++) {
        p = p.add(evaluate(2, RIGHT, i));
    }
    return p;
}

private static BigInteger evaluate(int index, int dir, int n) {
    if(n == 0) {
        if(dir == LEFT) return BigInteger.ONE;
        if(dir == RIGHT) return BigInteger.ZERO;
    }
    if(pos[index].equals(&quot;Y&quot;) || pos[index].equals(&quot;Z&quot;)) return BigInteger.ZERO;

    String key = pos[index] + (dir == RIGHT ? &quot;R&quot; : &quot;L&quot;) + n;
    if(map.containsKey(key)) return map.get(key);
    BigInteger p = evaluate(index + dir, dir, n).add(evaluate(index - dir, -dir, n - 1));
    map.put(key, p);

    return p;
}

} [/java]

フィールド(変数)

このComplicatedRoadsで使用されているフィールド(変数)についての説明です。

HashMap<String, BigInteger> map

ある位置におけるpの値を記録しておくために用意しているHashMapです。 キーとしては、位置(pos)、現在の向き(dir)、反転可能回数(n)を連結した文字列を使用します。 保存する値は、その条件の時のpの値です。

String pos

位置を表す文字列の配列です。 Y,A,B,C,Zの順番で並んでいます。 前述したmapのキーの値を求めるときに使います。

定数

このComplicatedRoadsで使用されている定数についての説明です。

int RIGHT

右方向を表す定数です。 値は1としています。

int LEFT

左方向を表す定数です。 値は-1としています。

メソッド

このComplicatedRoadsで使用されているメソッドについての説明です。

void main(String args)

mainメソッド内では、まずScannerクラスのインスタンスscannerを作成します。 これは標準入力の処理を行うために使用します。 scanner.hasNextIntメソッドを使って、標準入力に整数があるかどうかを確認します。 もし入力があればその値をNに代入します。 そして、その代入したNを引数としてsolveメソッドを呼び出します。 このsolveメソッドはP(N)の値を返してくるのでPに代入しておきます。 最後に、System.out.printlnメソッドでPを出力しています。

ちなみに、今回のテストケースでは各テスト毎に整数が1回のみの入力となっていますので…。 入力処理をわざわざwhileループにする必要は無いのですよね。 ただ、同時に複数入力された時に備えてこんな感じの実装方法にしてみました。

BigInteger solve(int N)

solveメソッドでは、引数としてNを受け取ります。 そして、BigInteger型の変数pを用意して0に初期化しておきます。 その後、forループを使ってiを0からNまで1ずつ増やしながらevaluateメソッドを呼び出します。 このevaluateメソッドは、n = iのときのP(i)の値を返してくるので、前回の結果のpにaddメソッドを使って加算します。 ループが終わるとP(N)の値がpに保存されています。 なので、後はpを返してやるだけです。

BigInteger evaluate(int index, int dir, int n)

このevaluateメソッドが主な計算処理を行っている部分になります。 このメソッドは引数にインデックス(index)、現在の向き(dir)、反転可能回数(n)を受け取ります。 これはn回反転した時のpを求めます。

n = 0の時は、反転ができないのでdirを確認します。 もしこれが左向き(LEFT)なら最終的にYに到達するので1を、右向きなら(RIGHT)ならZに到達するので0を返します。 nが0では無いときにYやZに到達した時というのは、まだ反転しきっていないので無効(0)とします。

次に、map用のキー(key)を求めます。 ここでは、pos、dir、nを連結した文字列をkeyとしています。 このkeyを元にして、まずmapに計算結果pが登録されているかどうかを確認します。 もし登録されていれば、その値pをそのまま返します。 登録されていない場合は、今の向きで1つ進んだ時の値と、反転して1つ進んだ時の値をそれぞれ求め、それを加算した結果をpに保存しておきます。 最後に、pをmapに新しく登録してからpの値を返しています。

このmapを使った実装にすることで、一度計算した途中結果を再利用することができます。 それによってevaluateメソッドの計算コストが大幅に削減されます。 その結果として、全体的な計算時間が短縮されることで、高速にP(N)の値を求めることができます。

苦労した点

今回、マヨイドーロ問題を解くプログラムを作成するにあたって苦労した点は主に2つあります。

このマヨイドーロ問題を解こうとした際に、最初は反復ではなく直接P(n)を求める実装にしていました。 これでも解けるには解けるのですが、再帰呼び出しの回数が非常に多くなってしまいます。 そのため、Nがある程度大きくなってくるとStackOverFlowのエラーが発生してしまいました。 これではまずいと思い、もっと良い方法は無いかと考えた結果、現在の反復しながらP(n)を求めるアルゴリズムを思いつき、この度実装する流れとなりました。 結果的には満足しています。

また、マヨイドーロ問題のPの値はせいぜいlong型で大丈夫だろうと思っていたのですが…。 テスト時にまさかのオーバーフローになりまして…。 そんなわけで、今回は非常に大きな数を扱うBigIntegerクラスを使っています。 このBigIntegerクラスのことは知らなかったので、使い方を色々調べながら実装しましたね。 これでまた1つ勉強になりました。

まとめ

今回の記事では、CodeIQで結城浩さんが出題した「マヨイドーロ問題」を解くプログラムのアルゴリズムについての解説をしてみました。 途中で何度かつまずきはしましたが、最終的には結果を求めることができました。 結構自分なりには丁寧に解説をしてみたつもりではあるのですが…。 今回の解説で、私のマヨイドーロ問題の解法アルゴリズムについて理解して頂けましたでしょうか?

今回のマヨイドーロ問題もそうですが…。 CodeIQの問題を色々と解いているうちに、プログラミングのスキルが上達していきそうな感じがしますね。 もしあなたがプログラミングに興味があるのなら…。 良かったらCodeIQの問題に挑戦してみてはいかがでしょうか?

[関連] ・プログラミングスキルの評価なら「CodeIQ」がおすすめ!

[参考] ・CodeIQ|ITエンジニアのための実務スキル評価サービスCodeIQの問題に挑戦しよう!