TopCoder SRM 502 Div2 Med / Div1 Easy: TheLotteryBothDivs

SRM練習会に参加。EasyMed提出Easy通過で243.43pt。Easyを参加者で一番早く提出できたのはよかった。

問題はこちら。

問題

クジの番号が000000000から999999999までの宝くじがある。当たり番号はいくつかあり、クジのsuffixが当たり番号のどれかに一致すれば当選とされる。当たり番号がいくつか与えられるので、ランダムにクジを1つ買った時にそれが当選する確率を求めよ。

解法

まずユニークな当たり番号を取り出す。たとえば120は0に含まれるので、こういったものを取り除く。
当たり番号を桁数順にソートし、ある当選番号のsuffixがすでにあるユニークな当たり番号と一致するかどうかを確認していく。
あとはユニークな当選番号に対して0.1^(桁数)を足し合わせていけばいい。

def find(self, goodSuffixes):
    goodSuffixes = sorted(goodSuffixes , key = lambda x: len(x))
    suffixes = []
    for s in goodSuffixes:
        for i in xrange(len(s)):
            if s[i:] in suffixes:
                break
        else:
            suffixes.append(s)
            
    ans = 0
    for s in suffixes:
        ans += 0.1 ** len(s)
    return ans

まとめ

題意がわかってしまえば簡単な部類だと思う。