TopCoder SRM 640 Div2 Med: NumberGameAgain

600pt問題だがそこまでの難易度ではないような・・・。

問題はこちら。

問題

次のような数字の操作を考える。

1. 変数xを1つ持つ。はじめにxを1にセットする。
2. xを2xにするか2x+1にする。
3. ただし途中xが禁止された値と等しくなったときはそこで操作を終える。

禁止された値の表tableとk(≦40)を与えられる。目標の値を2から2^k-1としたとき、上記の操作によって到達できる目標の値の個数はいくつあるかを答えよ。

解法

この操作による値の遷移は二分木となる(問題の図参照）。
図を見ればわかるが、xを2で割ることは操作をさかのぼることにあたる。
もしどの値も禁止されていなければ、到達可能な値の個数は 2 から 2^k-1 の 2^k - 2 個となる。
禁止されている値によって到達不可能になる値の個数を引いていくことを方針とする。

まずtableの中で到達不可能なものを除く。たとえば2と4が禁止されているとき、4の前には必ず2を経由しないといけないので4は到達不可能である。操作をさかのぼっていくとほかのtable中の値と等しくなってしまうものを取り出していく。

残ったtable中の値iについて、iによって到達が不可能になる値の個数を数えていく。iを木のノードと考えるとノードiの子ノードはすべて到達不可能となる。ノードiから世代を下るごとにノード数は2倍となる。木の底は平らなのでiが2^k-1を越えるまで2をかけていき、かけた値の分だけ答えを引いていけばよい。

残った値が到達可能な値の個数である。

def solve(self, k, table):
    ls = []
    for n in sorted(table):
        i = n
        while i > 0:
            i /= 2
            if i in ls:
                break
        else:
            ls.append(n)

    ans = 2 ** k - 2
    for i in ls:
        dble = 1
        while i <= 2 ** k - 1:
            ans -= dble
            i *= 2
            dble *= 2
    return ans

まとめ

二分木の性質をうまく扱えるかどうかの問題。