Monday, August 29, 2016

[TopCoder]SRM 687 Div2 Quacking | 书影博客

[TopCoder]SRM 687 Div2 Quacking | 书影博客
Ducks have started mysteriously appearing in your room. All ducks make the same sound: "quack". Each duck makes the sound one or more times, one after another. For example, valid sounds for a single duck are "quack", "quackquackquackquack", "quackquack", etc.
You have lost count of how many ducks are in your room. The ducks are quacking, and the sounds of their quacks are getting mixed up. You have recorded the sounds, obtaining a string of characters. When you later listened to the recording, you realized that the quacking of each individual duck forms a (not necessarily contiguous) subsequence of the recording. You also noticed that each letter in the recording belongs to exactly one duck. For example, if there were two ducks, you may have recorded "quqacukqauackck".
You are given a string s that contains an arbitrary recording. Find and return the smallest number of ducks that could have produced the recording. Note that it is possible that the given recording is not a valid recording of quacking ducks. In such case, return -1.

def quack(self, s): QUACK = {v : i + 1 for i, v in enumerate('quack')} size = len(s) duck = [0] * 6 ans = cur = 0 for c in s: i = QUACK[c] if i > 1 and duck[i - 1] == 0: return -1 duck[i - 1] -= 1 duck[i] += 1 if i == 1: cur += 1 elif i == 5: cur -= 1 ans = max(cur, ans) if size % 5 or cur: return -1 return ans

比赛时的解题思路：

def quack(self, s): QUACK = 'quack' size = len(s) duck = {QUACK[:i] : 0 for i in range(size + 1)} ans = 0 for c in s: for i, p in enumerate(QUACK): if p == c: prefix = QUACK[:i] if len(prefix) and duck[prefix] == 0: return -1 duck[prefix] -= 1 duck[prefix + p] += 1 break ans = max(sum(duck.values()) - duck[''] - duck[QUACK], ans) if size % 5 or duck[QUACK] != size / 5: return -1 return ans