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
まとめ
題意がわかってしまえば簡単な部類だと思う。