読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder SRM 648 Div1 o-- 1319->1322

topcoder 競技プログラミング

348th, 146.45pts, +0/-0 challenge
Volatility: 384->347

250: AB

\(N\)と\(K\)が与えられる(\(2 \le N \le 50\))
文字'A'と'B'で構成された長さ\(N\)の文字列を考えた時に、文字'A'が'B'より前に来るような文字の位置のペアの数がちょうど\(K\)になるような文字列があれば出力する

'A'と'B'を半々においてswapしていけば解けるらしいが、自分は'B'を置く数を総当りして貪欲に'A'を決めていった

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class AB:
    def createString(self, N, K):
        print
        for b in xrange(N + 1):
            temp = K
            pos = []
            for a in xrange(N - b):
                if temp >= b:
                    temp -= b
                    pos.append(b)
                else:
                    pos.append(temp)
                    temp = 0
            if temp == 0:
                break
        else:
            return ''
        cur = 0
        result = ''
        pos.sort()
        for i in pos:
            while cur < i:
                result += 'B'
                cur += 1
            result += 'A'
        A = len(pos)
        if len(result) < N:
            result += 'B' * (N - len(result))
        return result[::-1]
-->