TopCoder SRM 601 Div2 oox 1191->1224

131st, 690.96pts, +2/-2 challenge
Volatility ?->295

久しぶりに青くなりました
レートも全然上がらないし、参加時間を捻出するのもつらいのでやめようかと……

たまにはPythonで参加しようかと思って見つけた以下のプラグイン(Greed)で参戦(いつもはEclipseCoderを使ってる

• shivawu/topcoder-greed · GitHub

色々設定をいじれるみたいです

250: WinterAndMandarins

配列中から要素を\(K\)個選んだ時の最大の要素と最小の要素の差を最小にする

ソートしてから順に試せばよい

minを取っていく時の初期値に、最大値よりも小さな値を使ってる人がいたので、2人撃墜

class WinterAndMandarins:
    def getNumber(self, bags, K):
        bags = list(bags)
        bags.sort()
        result = 100000000000000
        for i in xrange(len(bags) - K + 1):
            result = min(result, bags[i + K - 1] - bags[i])
        return result

500: WinterAndCandies

配列中から、1個以上の任意の個数の要素を選ぶ組み合わせ数を答える
ただし、完全に同じ組み合わせは重複して数えない
また、1から選んだ個数までの数値がすべて含まれていなければならない

同じ数値はまとめて考えて要素を1個から順に選んでいく
順番に同じ数値の個数をかけたものを足していけばよい
選べなくなったら終了

最初にソートして順に調べているけど、各数値の個数を最初に求めたほうがきれいに書けたような

class WinterAndCandies:
    def getNumber(self, type):
        type = list(type)
        type.sort()
        L = len(type)
        index = 0
        result = 0
        mult = 1
        for i in xrange(1, L + 1):
            count = 0
            while index < L and type[index] == i:
                index += 1
                count += 1
            if count != 0:
                mult *= count
                result += mult
            else:
                break
        return result

1000: WinterAndReindeers

文字列A, B, Cが与えられる
AとBの共通部分列で、かつCを部分文字列として含む、最長の文字列Sの長さを求める
明らかに動的計画法っぽいんで、適当に書いていたものの時間内にはサンプルすら合わず
文字列アラインメント的なやつはROSALINDの問題を解いてた頃にたくさんやったような気がするんだけど……

以下システムテストでTLEになるコード
テストが一つだけ時間切れになるんですが、これってPython以外だったら絶対に通りますよねorz
dp[Aの長さ][Bの長さ][Cの長さ]だから間に合うと思ったんだけど……

追記、よくみたら制約を見間違えていて、長さの最大は2500でした。 そりゃ通るわけがありません

class WinterAndReindeers:
    def lc_substring(self, s1, s2, s3):
        print s1, s2, s3
        m = 0
        table = [[[0 for k in xrange(len(s3) + 1)] for i in xrange(len(s2) + 1)] for j in xrange(len(s1) + 1)]
        for i in xrange(len(s1)):
            for j in xrange(len(s2)):
                for k in xrange(len(s3) + 1):
                    table[i + 1][j + 1][k] = max(table[i + 1][j + 1][k], table[i + 1][j][k], table[i][j + 1][k])
                if s1[i] == s2[j]:
                    if table[i][j][len(s3)] > 0:
                        table[i + 1][j + 1][len(s3)] = table[i][j][len(s3)] + 1
                    for k in xrange(len(s3)):
                        if s1[i] == s3[k]:
                            if (k == 0) or (table[i][j][k] > 0):
                                table[i + 1][j + 1][k + 1] = max(table[i][j][k] + 1, table[i + 1][j + 1][k + 1])
                        table[i + 1][j + 1][0] = max(table[i + 1][j + 1][0], table[i][j][k] + 1)
        for i in xrange(len(s1)):
            for j in xrange(len(s2)):
                m = max(m, table[i + 1][j + 1][len(s3)])
        return m
    def getNumber(self, allA, allB, allC):
        return self.lc_substring(''.join(allA), ''.join(allB), ''.join(allC))