トコロテンの日記

自分の活動内容や普段考えていることをアウトプットするためのブログです。ITに関わる話がメインであり、開発、競技プログラミング、気に入った技術などの話が多くなります。

AtCoder Beginner Contest 115 D - Christmas

競技プログラミング AtCoder ABC

問題

atcoder.jp

考察と解法

メリークリスマス！………ではないですね。 なぜクリスマスにハンバーガーなのかはわかりませんがとりあえず問題と真剣に向き合うことにします。

まずはじめに、ハンバーガーの生成規則について確認しておきます。
ハンバーガーは'P'と'B'からなる文字列で表現されます。 また、ハンバーガーにはレベルがあり、レベルLハンバーガーを表す文字列h(L)は以下のように再帰的に定義されています。 +演算子は文字列の結合を表しています。

{} $$ h(L) = \left\{ \begin{array}{} "P" & (L =0) \\ "B" + h(L - 1) + "P" + h(L - 1) + "B" & (L \ge 1) \end{array} \right. $$

問題は、この定義から生成されるレベルN(1 \le N \le 50)バーガーの文字列の先頭からX文字目(1-indexed)までに含まれる'P'の個数を数えるといったものです。 まずは、全探索する場合を考えます。 これは、レベルNバーガーの文字列を実際に生成して、その文字列の先頭から順にX文字目まで各文字を調べて'P'の個数をカウントすればいいです。 そこで気になるのは、レベルNバーガーの文字列の長さです。なぜなら、全探索を行う場合、文字列を生成後に各文字を調べていくだけでも計算量が文字列の長さに比例するからです。 文字数が多すぎる場合、全探索は行えないことになります。したがって、全探索を行う前にレベルNバーガーの文字列の最大長について考えます。

レベルLバーガーの文字列長を表す関数|h(L)|はh(L)の定義より以下のようになります。

{} $$ |h(L)| = \left\{ \begin{array}{} 1 & (L =0) \\ |h(L - 1)| \times 2 + 3 & (L \ge 1) \end{array} \right. $$

このままではN=50(最大値)であるときの|h(50)|がわからないので漸化式から一般式を求めます。

$$ \begin{align} |h(L)| &= 2|h(L - 1)|+3 \\ &= 2(2|h(L - 2)|+3)+3 \\ &= 2^2|h(L - 2)| + 2^1 \cdot 3 + 2^0 \cdot 3 \\ &= 2^3|h(L - 3)| + 2^2 \cdot 3 + 2^1 \cdot 3 + 2^0 \cdot 3 \\ &= \vdots \\ &= 2^L|h(L - L)| + 3(2^0 + 2^1 + ... + 2^{L - 1}) \\ &= 2^L + 3(2^L - 1) \\ &= 2^L + 3 \cdot 2^L - 3 \\ &= 2^{L+2} - 3 \end{align} $$

|h(L)| = 2^{L+2} - 3が得られたので|h(50)|を求めてみると4503599627370493 \ge 10^{15}となることがわかり、全探索では一生計算が終わりません。 レベルNバーガーを生成してはいけません。あまりにも分厚すぎて手に負えません。悪あがきはやめて大人しく問題と真剣に向き合うことにします。

よく考えてみると、この問題で重要なのは'P'の個数だけであるため、レベルNバーガーの具体的な文字列は知る必要がありません。 レベルNバーガーの中には'P'と'B'、さらにレベルN-1バーガーが含まれていることに着目します(それはそう)。
ここでレベルNバーガーの先頭からX番目までの文字の中の'P'の個数を表す関数をf(N, X)とすると次のようになることがわかります。

{} $$ f(N, X) = \left\{ \begin{array}{} 1 & (N =0, X = 1) \cdots (1) \\ 0 & (N > 0, X = 1) \cdots (2) \\ f(N - 1, X - 1) & (N > 0, 1 < X < 2 + |h(N - 1)|) \cdots (3) \\ f(N - 1, |h(N - 1)|) + 1 & (N > 0, X = 2 + |h(N - 1)|) \cdots (4) \\ f(N - 1, |h(N - 1)|) + f(N - 1, X - 2 - |h(N - 1)|) + 1 & (N > 0, 2 + |h(N - 1)| < X < 3 + 2|h(N - 1)|) \cdots(5) \\ 2f(N - 1, |h(N - 1)|) + 1 & (N > 0, X = 3 + 2|h(N - 1)|) \cdots (6) \end{array} \right. $$

(1)の場合は自明であるため、それ以外について説明します。

  • (2)は、レベル1以上のバーガーの左端は必ず'B'になるため0個となります。
  • (3)は、XがレベルNバーガーに含まれる左側のレベルN-1バーガーの範囲内にあるときです。この時は、レベルN-1バーガーの中にしか'P'が存在しないため、レベルN - 1バーガーのX - 1番目までに含まれる'P'の個数を数えます。
  • (4)は、X番目の文字がレベルNバーガーを構成している中央の'P'(レベルN-1の'P'ではありません)を指している時であるため、左側のレベルN-1バーガーに含まれる'P'の個数+1個になります。
  • (5)は、XがレベルNバーガーに含まれる右側のレベルN-1バーガーの範囲内にあるときです。この時は、左側と右側のレベルN-1バーガーの中にある'P'と(4)の場合の中央の'P'が存在するため、左側のレベルN-1バーガーに含まれる全ての'P' + 右側のレベルN-1バーガーのX - 2 - |h(N - 1)|番目までに含まれる'P'+1個になります。
  • (6)は、XがレベルNバーガーの最後尾を指している場合です。この場合は左右のレベルN-1バーガーが対称であることを利用してレベルN-1バーガーの中に含まれる'P'の2倍の個数に(4)の場合の中央の'P'の+1個になります。

上のような再帰関数を定義して呼び出すことでレベルNバーガーを生成することなくこの問題を解くことができます。

計算量

上記の再帰関数では、N=0となった時に再帰を終了します。 また、(1)以外の場合は必ずNが1ずつ減少していくため、少なくともN回の再帰呼び出しでf(N, X)は終了します。 したがって、時間計算量はO(N)です。

実装上の注意点

最も分厚いレベル50バーガーは32bit整数の範囲には収まらないため、64bit整数の幅を持たせなければなりません。#define int long longの会に入会することでオーバーフローを気にすることなく安心してこの問題を解くことができます。

ソースコード

#include <iostream>
 
// #define int long longの会に入会
#define int long long
 
using namespace std;
 
int calcBurgerSize(int level)
{
    return level ? 2 * calcBurgerSize(level - 1) + 3 : 1;
}
 
int countPatties(int level, int x)
{
    if(level == 0)
    {
        return 1;
    }
 
    int smallSize = calcBurgerSize(level - 1);
 
    if(x == 1)
    {
        return 0;
    }
    else if(x < 2 + smallSize)
    {
        return countPatties(level - 1, x - 1);
    }
    else if(x == 2 + smallSize)
    {
        return countPatties(level - 1, smallSize) + 1;
    }
    else if(x < 3 + smallSize * 2)
    {
        return countPatties(level - 1, smallSize) + countPatties(level - 1, x - smallSize - 2) + 1;
    }
    else
    {
        return countPatties(level - 1, smallSize) * 2 + 1;
    }
}
 
signed main()
{
    int n, x;
 
    cin >> n >> x;
 
    cout << countPatties(n, x) << endl;
}

感想

クリスマスではないにも関わらずChristmasを解いてしまったことに罪悪感を感じてます。場合分けおじさんを体に宿すことでこの問題をACすることができます。