TopCoder Open 2014 Algo Round1A oo- 1338->1339

990th 394.37pts, +0/-0 challenge
Volatility 409->369
Mediumで無駄にややこしいコードを書いてしまって、バグが取れずに終了5分前ぐらいまでコードを書いていた(´・ω・｀)

問題のeditorialが公開されている

• https://docs.google.com/document/d/1O5v5d_iY9zV0slI8fgKhZosDsYDNSZVsOXeL2Cui0DM/pub

Hardは単純に特定のパターンを数えれば解けるらしい

• 2014 TCO Round 1A - TopCoder煮ブログ - TopCoder部

250: EllysSortingTrimmer

文字列をある位置からL文字ソートして、L+1文字以降は削除する操作が、与えられた文字列に対して何回でも行えるとき、辞書順で最小の文字列を答える
後ろから順に操作の定義通りソートして削除していっても間に合う

class EllysSortingTrimmer:
    def getMin(self, S, L):
        S = list(S)
        LS = len(S)
        for i in reversed(xrange(LS - L + 1)):
            temp = S[i:i+L]
            temp.sort()
            S[i:] = temp[:L]
        return ''.join(S[:L])

500: EllysScrabble

ある文字列が与えられた時、文字の位置を元の位置から最大maxDistanceだけ動かしてもいいときの、辞書順で最小の文字列を答える

左から順番にmaxDistanceの範囲内で辞書順最小の文字を見つけて配置していけばよい。
ただしmaxDistanceの範囲の右端に来ている文字はかならず使う

以下のコードは無意味に文字を交換とかしているので汚い。
文字を使ったかどうかを記録しておけばもっと簡単に書ける。

class EllysScrabble:
    def getMin(self, letters, maxDistance):
        L = len(letters)
        candidate = []
        for i in xrange(L):
            candidate.append((i, letters[i]))
        result = ''
        for i in xrange(L):
            possible = [(i, candidate[i])]
            if candidate[i][0] + maxDistance > i:
                for j in xrange(i + 1, L):
                    if candidate[j][0] + maxDistance == i:
                        possible = [(j, candidate[j])]
                        break
                    if abs(i - candidate[j][0]) <= maxDistance:
                        if candidate[j][1] < possible[0][1][1]:
                            possible = [(j, candidate[j])]
                        elif candidate[j][1] == possible[0][1][1]:
                            possible.append((j, candidate[j]))
            possible.sort(key=lambda x:x[1][0])
            candidate[i], candidate[possible[0][0]] = candidate[possible[0][0]], candidate[i]
        return result