Topcoder SRM 722 Div.1 Easy - TCPhoneHome

問題概要

あるシステムにおいて、電話番号の桁数はNである。またこのシステムでは特定の接頭辞がついた電話番号はすべて「特別な番号」として予約されている。Nと接頭辞の集合Sが与えられるので、特別でない番号が何通り存在するか求めよ。

1 <= N <= 17, 0 <= |S| <= 50

解法

基本的には特別な接頭辞がつく番号の数を数え、それを10Nから引けばよい。ただしこのままだと重複が出るので、それは数えないようにする必要がある。具体的にはある接頭辞が別の接頭辞の接頭辞になっている場合、重複が起きる。例えば'12'と'123'が接頭辞に含まれるとき、'12'で始まる番号の数を数えるとその中に'123'で始まる番号を含んでいることになる。逆に、これ以外のケースで重複数え上げは発生しえない。以上よりある接頭辞が別の接頭辞を接頭辞として含んでいる場合は数え上げの対象に含めない、ということをすればよい。O(|S|^2)

感想

easyとしてちょうどいい感じがあって良かった。コードのところにpythonを載せるの初めてかもしれない。基本的にはD言語でやってるんですが、定数倍が不安だとかDが使えない場所だとかではC++を, 実装軽くて計算量にも十分な余裕がある場合はPythonを気まぐれで使ったりしてます

コード (Python2)

class TCPhoneHome:
    def validNumbers(self, digits, specialPrefixes):
        specialPrefixes = list(specialPrefixes)
        specialPrefixes.sort(key=lambda x: len(x))
        noneed = []
        for i in xrange(len(specialPrefixes)):
            for j in xrange(i+1, len(specialPrefixes)):
                if specialPrefixes[j].startswith(specialPrefixes[i]):
                    noneed.append(j)
        noneed = reversed(sorted(set(noneed)))
        for n in noneed:
            specialPrefixes.pop(n)

        ans = 10 ** digits
        for s in specialPrefixes:
            ans -= 10 ** (digits - len(s))

        return ans