TopCoder SRM 426 Div2 Easy: KnockoutTourney

Div2 Easyにしてはむずかしめな気がする

問題はこちら。

問題

N人で行うトーナメントをしている。出場選手はトーナメント表の左から順番に番号付けされており、あなたは番号youでライバルは番号rivalである。あなたとライバルがぶつかるのは、ともに何回勝ち進んだときであるかを答えよ。

解法

いわゆる分割統治的なアプローチで解ける。
あなたとライバルの番号が、2ⁿの半分より多い側と少ない側分かれたとき、あなたとライバルはn回戦うとぶつかることができる。
問題ではNが2のべき乗以外の場合もありうるが、簡単のためにNをNより大きな2のべき乗に直してしまっても答えは変わらない。

def meetRival(self, N, you, rival):
    ans = 0
    n = 1
    while n < N:
        n *= 2
        ans += 1
    you -= 1; rival -= 1
    while n:
        if you / (n / 2) != rival / (n / 2): return ans
        n /= 2
        ans -= 1

まとめ

2のべき乗に直すテクは便利だ