TopCoder SRM 627 Div1 x-- 1236->1194

• SRM 627 - Togetterまとめ

489th, 0pts, +0/-0 challenge
Volatility: 363->340

例のごとく1回でDiv2落ち。
最近の連続失敗に学んで、Challengeは放棄

250: HappyLetterDiv1

与えられた文字列(長さ最大50、aからz)から異なる2文字を選んで消していって、最後に残った文字が1種類になる場合を考える
このとき最後に残る可能性がある文字を昇順につなげて答える

残したい文字以外を使って消していった時に、最後に残る文字の文字数を最小にしたい
消さない文字を仮定して、その他の文字について多い順から1つずつペアを選んで消していって最後に残った文字の個数が、最初に選んだ消さない文字よりも少なければ、最初に選んだ消さない文字は最後まで残せる

文字列の長さを\(n\)とするとヒープを使って\(O(n^2 \log n)\)ぐらい？(実際には文字の種類が26種類しかないからもっと少なくなる)

import math,string,itertools,fractions,heapq,collections,re,array,bisect

class HappyLetterDiv1:
    def getHappyLetters(self, letters):
        c = collections.Counter(letters)
        
        ret = []
        for i in c:
            heap = []
            for j in c:
                if i == j:
                    rest = c[j]
                else:
                    heap.append(-c[j])
            heapq.heapify(heap)
            while len(heap) > 1:
                for v in [heapq.heappop(heap), heapq.heappop(heap)]:
                    if v < -1:
                        heapq.heappush(heap, v + 1)
            if not heap or rest > -heap[0]:
                ret.append(i)
        ret.sort()
        
        return ''.join(ret)