ABC115-D解説 - naoppyの日記

お詫び

ここに書いてあった記事は naoppy-jyoken.hatenablog.com に移転しました。

この記事ではD問題の思考経緯などを書いていきます。

D - Christmas

問題

思考経緯

法則性を見つける問題かなと思い、まずは問題文通りパティを P、バンを B で表すを実装していきます。

public class Dstr {
    public static void main(String[] args) {
        for (int i = 0; i < 5; i++)
            System.out.println(makeBG(i));
    }

    private static String makeBG(int level) {
        if (level == 0) return "P";

        return new StringBuilder("B")
                .append(makeBG(level - 1))
                .append("P")
                .append(makeBG(level - 1))
                .append("B")
                .toString();
    }
}

まずはレベル0～4までのバーガーを文字列化して出力してみました。

出力結果

P
BPPPB
BBPPPBPBPPPBB
BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
BBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBPPPBPBPPPBBBB

左右は対称だということが問題文からも、結果からもわかりました。バーガーを下から食べていく。という問題文は上から、と読み替えてもいいですし、バーガーを横にして左から(あるいは右から)、と考えてもいいことがわかりました。問題からノイズを取り除いて、本質だけを見ましょう。

ここからわかることは、nが50の時、バーガーは非常に長くなるであろう、ということです。愚直にすることができないことがわかりました。じゃあ、どれくらい長いの？というわけで、次はそれを求めていきます。

バーガーの長さ

public class Datsusa {
    public static long[] AtsusaDP = new long[51];

    static {
        AtsusaDP[0] = 1L;
        for (int i = 0; i < 50; i++) {
            AtsusaDP[i + 1] = 3L + 2 * AtsusaDP[i];
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 51; i++)
            System.out.println(AtsusaDP[i]);
    }
}

厚さの漸化式はlevel_0で1、level_iで3+2*level_(i-1)です。これは問題文から自明だと思います。よってレベルが低い方から求めていくと、順番に求まります。

では、出力結果を見てみましょう。

1
5
13
29
～～省略～～
2251799813685245
4503599627370493

レベル50のバーガーの厚さは4503599627370493ということがわかりました。一枚ずつシュミレーションしながら食べていっても、間に合いそうにはないですね。

この辺りから、バーガーを一気に食べられると楽だなという気持ちになってきます。問題文は何枚食べるかが与えられます。もし、あるレベルのバーガーを一気に食べても、まだ食べられる余力がある（あるレベルのバーガーを食べた後のあと何枚食べるか >= 0）なら一気に食べたいです。そして、無理ならばバーガーを細かく分解して食べていきます。ただ、その時いくつのパティを求めたかがわからないと問題が解けません。

なので次はレベルごとのバーガーに含まれるパティの数を求めていきます。

public class Dpcount {
    public static long[] P_CountDP = new long[51];

    static {
        P_CountDP[0] = 1;
        for (int i = 0; i < 50; i++) {
            P_CountDP[i + 1] = 1L + 2 * P_CountDP[i];
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 51; i++)
            System.out.println(P_CountDP[i]);
    }
}

パティの個数の漸化式はlevel_0で1個、level_iのとき1+2*level_(i-1)です。これも問題文から自明ですね。

出力結果は省略します。

これらあるレベルのバーガーの厚さや含まれるパティの数は一瞬(たった50回のループ)に求まりました。

では、一気に食べるOR分解する動作を実装してみましょう。

実装

再帰関数を使いながら食べていきます。再帰関数には今食べている部分的なバーガーのレベル、そして残りの食べるべき数を渡します。今までに食べたパティの総数は渡さなくていいの？と思うでしょうが、それはグローバル変数ansに記録していきます。関数名はeatBGとします。

バーガーを一気に食べられる場合

/**
 * @param level ハンバーガーのレベル
 * @param rest  残りの食べるべき数
 * @return 新しい残りの食べるべき数
 */
private static long eatBG(int level, long rest) {
    if (rest >= AtsusaDP[level]) {
        rest -= AtsusaDP[level];
        ans += P_CountDP[level];
        return rest;
    }
}

できました。次はelse節を書いていきます。 else節には何を書けばいいでしょうか？ rest >= AtsusaDP[level]がfalseな場合、つまり今の部分的なバーガーのサイズではその途中までしか食べられない場合です。その場合、バーガーを分解していきましょう。食べている途中でrestが0になるでしょう。そのとき、もう食べる必要がないのに食べて、今までに食べたパティの総数を増やしてしまわないように気を付けましょう。

} else {
    rest--;// B part
    if (rest > 0) rest = eatBG(level - 1, rest);// n-1 BG part
    if (rest > 0) {// P part
        rest--;
        ans++;
    }
    if (rest > 0) rest = eatBG(level - 1, rest);// n-1 BG part
    rest--;// B part
    return rest;
}

できました。しかしまだこれで終わりではありません。動かせばわかるのですが、level-0のところまで分解されると、level-(-1)に分解しようとしてしまいます。よってlevel=0のときの処理を関数の先頭に書いてあげます。

if (level == 0) {
    if (rest > 0) {//P part
        ans++;
        return rest-1;
    } else {
        return rest;
    }
}

レベル0まで分解されたら、Pしかないバーガーなので食べれたら食べて終わりです。

では、コードをまとめて見てみましょう。

package ABC115;

import java.util.Scanner;

public class A {
    public static long[] AtsusaDP = new long[51];

    static {
        AtsusaDP[0] = 1L;
        for (int i = 0; i < 50; i++) {
            AtsusaDP[i + 1] = 3L + 2 * AtsusaDP[i];
        }
    }

    public static long[] P_CountDP = new long[51];

    static {
        P_CountDP[0] = 1;
        for (int i = 0; i < 50; i++) {
            P_CountDP[i + 1] = 1L + 2 * P_CountDP[i];
        }
    }


    public static long ans = 0L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();

        eatBG(n, x);
        System.out.println(ans);
    }

    /**
     * @param level ハンバーガーのレベル
     * @param rest  残りの食べるべき数
     * @return 新しい残りの食べるべき数
     */
    private static long eatBG(int level, long rest) {
        if (level == 0) {
            if (rest > 0) {//P part
                ans++;
                return rest-1;
            } else {
                return rest;
            }
        }

        if (rest >= AtsusaDP[level]) {
            rest -= AtsusaDP[level];
            ans += P_CountDP[level];
            return rest;
        } else {
            rest--;//B part
            if (rest > 0) rest = eatBG(level - 1, rest);// n-1 BG part
            if (rest > 0) {//P part
                rest--;
                ans++;
            }
            if (rest > 0) {//n-1 part
                rest = eatBG(level - 1, rest);
            }
            rest--;//B part
            return rest;
        }
    }
}

最後に

めっちゃ丁寧に解説したので、D問題初めてやる人とかの足がかりになればいいな。論理的な意味を重視したコードを書いたので冗長な部分は多々あります。

こんなクソ長い記事を読んでいただきありがとうございました。