僕の考えたマヨイドーロの解答

Java CodeIQ

CodeIQ に出題されていたマヨイドーロの僕の解答です。 今は設問が見れませんが出題は以下。

codeiq.jp

解答

以下が僕の解答です。 ただただ漸化式をそのままコーディングしただけのあんまり工夫のないコードになりました。

Java7 で提出しました。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    /** リストのメモ */
    private static List<BigInteger> list = null;

    public static void main(String[] args) throws IOException {
        list = new ArrayList<BigInteger>(Arrays.asList(
                new BigInteger("0"),
                new BigInteger("2"),
                new BigInteger("5")
                ));

        // 標準入力
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        countKindOfRoad(n);
        BigInteger p = new BigInteger("0");
        for(int i = 0; i <= (n + 1) / 2; i++) {
            BigInteger temp = list.get(i);
            p = p.add(temp);
        }

        System.out.println(p);
    }

    private static BigInteger countKindOfRoad(int n) {
        BigInteger p;

        if (list.size() - 1 < (n + 1) / 2) {
            // 未カウント
            // 前回 * 2 + (前回 - 前々回)
            BigInteger last = countKindOfRoad(n - 2);
            BigInteger beforeLast = countKindOfRoad(n - 4);
            p = last.multiply(new BigInteger("2")).add(last.subtract(beforeLast));
            list.add(p);
        } else {
            // カウント済み
            if (n == 0) {
                p = list.get(0);
            } else {
                p = list.get((n + 1) / 2);
            }
        }

        return p;
    }

}

/*
 * BA, CA 始まりは 前回と同数
 * CB 始まりは 前回のC始まりと同数
 * = 前回 + 前回 + 前回のC始まり
 * = 前回 * 2 + (前回 - 前々回)
 *
 *
 * 反転 1 -> 2
 * B
 * C
 *
 * 反転 3 -> 5
 * BAB
 * BAC
 * CAB
 * CAC
 *
 * CBC
 *
 * 反転 5 -> 13
 * BABAB
 * BABAC
 * BACAB
 * BACAC
 * BACBC
 * CABAB
 * CABAC
 * CACAB
 * CACAC
 * CACBC
 *
 * CBCAB
 * CBCAC
 * CBCBC
 *
 * 反転7 -> 34
 * CBCABAB
 * CBCABAC
 * CBCACAB
 * CBCACAC
 * CBCACBC
 * CBCBCAB
 * CBCBCAC
 * CBCBCBC
 *
 */

どのように考えたか

問題文を読み解く

問題文には考える材料が必ずあるはずなので、まずは問題文を穴が空くほど読みます。

問題文から解るのは、反転回数が奇数のときしかYにたどり着かないということと、 N = 3 であれば反転回数が 1 のときと 3 のときの合計がPであること。

つまり、N以下で反転回数が奇数のときの合計を求めればよいことがわかります。

とにかく書き出す

どんな問題もそうですが、法則をみつけるためにはすべてを書き出します。 最後の複数行コメントは書きだした結果です。

ここではアリスが反転した時点の居場所のみ記述しています。

反転回数が 1 のときは X > B > A > Y と X > B > C > B > A > Y の 2 パターンで、 反転する場所が B の場合と C の場合があります。

反転回数が 3 のときの BAB は X > B > A > B > A > Y を示します。

反転 1 -> 2 は反転回数が 1 のとき 2 パターンあることを示します。
反転 3 -> 5 は反転回数が 3 のとき 5 パターンあるということです。

はじめは 1, 3, 5 まで書き出して考えました。

法則をみつける

パターン数の数列は 2 5 13 であり差分は 3 8 なので、 単純にパターン数に法則がないことがなんとなくわかりました。 実際はあるのかもしれません。

というわけで、パターンの構成をみます。

最初はただパターンを羅列していたので B 始まりより C 始まりの方が数が多いなくらいしかみつけられませんでした。

ここでしばらく悩んでいました。 が、ふとみつけたのが 反転 2 回め以降に法則があるというものです。

例として反転回数が 3 のときを考えます。 反転回数が 3 のときのパターンは次の 5 つです。

BAB
BAC
CAB
CAC
CBC

2 回めに反転する場所は A か B しかありません。 しかも、B で反転した次は C で反転するしかありません。

ということは、A で 2 回めの反転をすると反転回数が 1 のときと同じパターンとなり、 かつ、B で 2 回めの反転をすると反転回数が 1 のパターンのうち、C で反転するパターンとなります。

つまり、反転回数が 3 のとき

  • BA -> 反転回数が 1 のパターン
  • CA -> 反転回数が 1 のパターン
  • CB -> 反転回数が 1 のパターンのうち、C で反転するパターン

の 3 つを合計すればよいことになります。

ここで前回 + 前回 + 前回の C 始まりという法則がみつかりました。

最後に悩んだのが前回の C 始まりをどう算出するかです。 パターンの羅列だけ眺めてたときはなかなか気づきませんでしたが、 反転回数が 3 のパターンをみれば一発ですね。

要は反転回数が 3 のときの C 始まりを得るには(反転回数が 3 のときのパターン) - (反転回数が 1 のパターン)。 つまり、前回 - 前々回ですね。

と、いうわけで最終的には前回 * 2 + (前回 - 前々回)という法則がみつかりました。

数式にすると次のようになります。

{ \displaystyle P_N = P_{N-1} * 2 + (P_{N-1} - P_{N-2}) }

かっこいいですね。

コーディングする

コードは見つかった法則をそのまま表してるんじゃないかなと思います。

前回と前々回が必要になるので、反転回数が 1 のときと 3 のときは初めから判明してる値としています。
問題文にも 1 と 3 のときのパターンが明記してあったからこれくらい許されるはず。

あと、結城先生のリツイートに多倍長整数って言葉がいっぱい出てきてたから BigInteger を使いました。
それまで多倍長整数なんて知らなかったので、一生懸命調べました。 BigInteger 便利ですね。

まとめ

問題文の量の割には結構簡単なコードになったなという印象。 短く書くことは意識してなかったのに、完結で短いコードになったので気持ちよかったです。
Java8 の Stream とか使えばもっと短くなると思います。 Java8 はちゃんと勉強してないので未挑戦ですが。

多倍長整数と BigInteger を知るいいキッカケとなったのですごい有意義な問題でした。

あらためてコードを見直すと修正した方がいいなって思うところがチラホラ…

12/21 追記

勘違いしてたこととか後から気づいたことの追記です。

フィボナッチ数列

巷ではフィボナッチ数列と噂になっていましたが、 記事を書いた時点ではなぜフィボナッチ数列なのかわかっていなかったので、 数列には法則がないと書きました。

記事では Z にたどり着く場合を無視していましたが、 Z にたどり着く場合も含めた数列はフィボナッチ数列です。

反転回数 2 のとき、BA, CA, CB の 3 パターン、 反転回数 4 のとき、BABA, BACA, BACB, CABA, CACA, CACB, CBCA, CBCB の 8 パターンであるため、 全体では 2, 3, 5, 8, 13... となります。

僕はフィボナッチ数列をひとつ飛ばしにした数列の漸化式を求めていたということですね。

漸化式

{ \displaystyle P_N = P_{N-1} * 2 + (P_{N-1} - P_{N-2}) }

はもともと

{ \displaystyle P_N = P_{N-1} + P_{N-1} + (P_{N-1} - P_{N-2}) }

であるので、

{ \displaystyle P_N = P_{N-1} * 3 - P_{N-2} }

とまとめられますね。 これならコードも

p = last.multiply(new BigInteger("3")).subtract(beforeLast);

と少し短くできます。

個人的には元の { \displaystyle P_N = P_{N-1} * 2 + (P_{N-1} - P_{N-2}) } が好みです。

理由は導いた法則の前回 + 前回 + 前回の C 始まりに逆変換しやすいからです。

このあたりはどの程度最適化するかという好みの問題になりそうなのであまり深くは掘り下げませんが、 後で見たときにわかりやすいようにと考えると、 余分なことまで考えないといけなくなるようなコードは書きたくないです。

追記のまとめ

追記してしまうほどマヨイドーロには考えさせられました。

追記しなければと思うほどコーディングしてたときの僕が未熟だったということでもありますが...