ABC115D - ChristmasをJavaでといてみる

もうすぐクリスマスですが、私の大学は毎年クリスマスにテストがあるので、ここ数年は単位がプレゼントでした。ハンバーガーを犬が食べる問題ABC115D - Christmasをといた話。

戦略

Stringを使った再起が一番書きやすくて、すぐに思いつきました。ダメだったらメモ化再起、それもだめだったらStringBuilderしよ。みたいな感じではじめに書いたのがメモ化再起なしのString再起。これだとOOME(out of memory error)(メモリが足りないと怒られた)になりました。メモ化再起を利用したのが解法１。結果は変わりませんでした汗
Stringは足し算すると、後ろに追加とかできなくて、新しくメモリを確保して入れ直すので、メモリの解放が追いつかなかったんだろうなあ...(ちゃんと調べてないけど)
ほかの人の解法をチラ見して、インデックスでどうにかできそうだったので、longの再起で解決しました。(解法２) このレベルの再起はまだまだ書いてる途中でわかんなくなるので苦手です..

解法１

私的にすごく素直なコードだと思います。バーガーの全体の層を文字列で表した後、犬が食べる層だけsubstringで抜き出してから、バンを抜いた文字列の長さを出力しています。

コード

import java.util.*;
class Main{
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long X = sc.nextLong();
    HashMap<Integer, String> map = new HashMap<Integer, String>();
    String burger = makeBurger(N, map);

    String tabeta = burger.substring(burger.length() - (int)X);
    tabeta = tabeta.replace("B","");
    System.out.println(tabeta.length());
    }
    public static String makeBurger(int N, HashMap<Integer, String> map) {
    if(N == 1) {
        return "BPPPB";
    }

    String str = map.get(N-1);
    if(str == null) {
        str = makeBurger(N-1, map);
        map.put(N-1, str);
    }

    return "B" + str + "P" + str + "B";
    }
}

だめなところ

めっちゃメモリを消費しています。

    return "B" + str + "P" + str + "B";

解法２

ほかの人の解法をチラ見しました。うまくパティだけ数える方法です。再起の中はごたごたしますが、数が大きくても動きました。

コード

import java.util.*;
class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long X = sc.nextLong();
        HashMap<Integer, Long> map = new HashMap<Integer, Long>();
        long Nlen = 5;
        map.put(1, Nlen);
        for(int i = 2; i <= N; i++) {
            Nlen = Nlen*2 + 3;
            map.put(i, Nlen);
        }

        long tabeta = havePatty(N,X,map);
        System.out.println(tabeta);
    }

    public static long havePatty(int N, long X, HashMap<Integer, Long> map) {
        if(X <= 1) return 0;
        if(N == 1) {
            if(X == 1) return 0;
            else if(X == 2) return 1;
            else if(X == 3) return 2;
            else if(X == 4 || X == 5) return 3;
        }

        long Nlen = map.get(N);
        long l = map.get(N-1);
        if(X == Nlen) {
            return 1 + 2 * havePatty(N-1, l, map);
    } else if(X >= Nlen/2+1){
            return 1 + havePatty(N-1, l, map) + havePatty(N-1, X-l-2, map);
        } else {
            return havePatty(N-1, X-1, map);
        }
    }
}

まとめ

犬がハンバーガーを食べる問題を解きました。次の問題では少しでも「...かもしれない」が「...だからだ」ってなるようになろうと思いました。