AtCoder Beginner Contest 115 D問題

問題：Christmas

本番では解くことができなかった。しかし、解法がとてもシンプルかつ、再帰関数の実装に関して教育的な問題だと感じた。

解法

• 各レベルiの「層の総数」と「含まれるパティの数」は入力に関係なく、事前に計算できる。
• レベルiのバーガーにはレベル(i-1)のバーガーが２個含まれる再帰的な構造を利用して、再帰関数を実装する。引数は、現在考えているレベルiと下から食べる層の最高位置xとする。
• レベルiのバーガーは、５つの部分に分かれている。それぞれ下側から、次のように呼称する。
  1. 最下層バン
  2. レベル(i-1)バーガー（下）
  3. 中間パティ
  4. レベル(i-1)バーガー（上）
  5. 最上層バン
• 位置xがバーガー中の５つの内どの部分かによって処理が分岐する。
  1. 最下層バン１枚のみ食べる。（ただしレベル０のときはパティ１枚）
  2. レベル(i-1)バーガー（下）の中で再帰的に考える。
  3. 最下層バン、 レベル(i-1)バーガー（下）、中間パティをちょうど食べる。
  4. 最下層バン、 レベル(i-1)バーガー（下）、中間パティを食べ、レベル(i-1)バーガー（上）の中で再帰的に考える。
  5. 最下層バン、 レベル(i-1)バーガー（下）、中間パティを食べ、レベル(i-1)バーガー（上）、最情報バンをちょうど食べる。

long long N, X;
long long s[55];   // s[i]: レベルiのバーガーの層の総数
long long p[55];   // p[i]: レベルiのバーガーに含まれるパティの総数

long long f(long long i, long long x){   //レベルn, 下からx
    if(x == 1){ //ケース１
        return i == 0 ? 1 : 0;
    }else if(1 < x && x <= s[i-1] + 1){ //ケース２
        return f(i-1, x-1);
    }else if(x == s[i-1] + 2){  //ケース３
        return p[i-1] + 1;
    }else if(s[i-1] + 2 < x && x <= 2*s[i-1] + 2){  //ケース４
        return p[i-1] + 1 + f(i-1, x-(s[i-1]+2));
    }else{  //x == 2*s[n-1] + 3（ケース５）
        return p[i];
    }
}

int main() {
    cin>>N>>X;

    // 各レベルの層の総数と含まれるパティの数を計算
    s[0] = 1;
    p[0] = 1;
    REP(i,1,N+1) s[i] = 2*s[i-1] + 3;
    REP(i,1,N+1) p[i] = 2*p[i-1] + 1;

    cout<<f(N, X)<<endl;

    return 0;
}

コンテスト中の思考（失敗）

• レベルが決まれば、パティの数が求められることとその式については気づいていた。
• レベルiにおけるバーガーの層の総数を式で表すことは思いつかなかった。
• iを増やしながら実験をして、何かルールがないか探していた。
• 反省：再帰構造が見え見えだったので、それを利用してもっと愚直な実装を考えてい見るべきだった。