TopCoder SRM 648 Div2

14回目のSRM。EasyMed解いたが部屋4位、全体240位くらい。Medで変な実装をしてバグ取りに時間をかけすぎた。Hardが10分しか取り組めず、しかも最後1分で解法がわかっただけにもったいない。902 → 923 (+21)。

問題はこちら。

Easy 250: KitayutaMart2

あるスーパーでは1つ目のリンゴはK円、2つ目は２K円、3つ目は2² K円、、、。とｎ個目のリンゴは2^n-1 K円で買うことができる。今いくつかリンゴを買ったところ支払いはT円となった。何個のリンゴを買ったのかを求める問題。

K+2K+4K... 2^n-1 K = (2ⁿ-1)K　であるからループを回して右辺がTに等しくなるかを調べていけばいい。

def numBought(self, K, T):
    T /= K
    ans = 0
    for i in xrange(1,10000):
        if 2**i-1 == T: return i

Med 500: Fragile2

0からN-1まで頂点を持った無向辺グラフがあたえられる。2つの頂点を選び方のうち、それらを抜き去ったあとのグラフのコンポーネントの数がもとのグラフのものより多くなるような選び方は何通りあるかを答える問題。

2重ループを回して抜き取る頂点を2つ決め、そのときのコンポーネントの数をもとのグラフのものと比較すればいい。以下のコードはごちゃごちゃとしているが、頂点を抜き去ったあとのグラフの頂点間の距離をベルマンフォードで求め、コンポーネントの数を数えている。Nが20以下なので O(N⁵) でも間に合う。

def countPairs(self, graph):
    def getDist(G):
        N = len(G)
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    G[i][j] = min(G[i][j], G[i][k]+G[k][j])
        return G
        
    def countGroup(G):
        res = 0
        G = getDist(G)
        N = len(G)
        V = range(N)
        while V:
            i = V.pop()
            for j in range(N):
                if j not in V: continue
                if G[i][j] < inf: V.remove(j)
            res += 1
        return res
        
    graph = list(list(graphi) for graphi in graph)
    N = len(graph)
    for i in range(N):
        for j in range(N):
            graph[i][j] = 1 if graph[i][j] == "Y" else inf
    group = countGroup(copy.deepcopy(graph))
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            G = [[graph[k][l] for l in range(N) if l != i and l != j] for k in range(N) if k != i and k != j]
            if countGroup(G) > group:
                ans += 1
    return ans

Hard 1000: createString

N 個の文字からなる文字列ｓを考える。各文字はA,B,Cのどれかで、i 番目の文字を s[i] としたとき文字列中に s[i] < s[j] (i < j) の関係が K 個あるようなｓを作れるかどうか、作れるならその具体例を１つ答える問題。

s[i] < s[j] の数を count とすると、count が最大となるのは s = "AAABBBCCC"　(N = 9)のようなとき。このときのcount数がKよりも小さいならどうあっても条件を満たすｓは作れない。上記ｓの場合、隣り合う s[i] < s[i+1] な文字同士をスワップするとcountは1下がる。したがって、上記ｓをひっくり返し、隣り合う s[i] > s[i+1] な文字列をK回スワップすれば条件を満たす文字列を得ることができる。

def createString(self, N, K):
    n = N/3
    s = "A"*n + "B"*n + "C"*n
    if   N%3 == 2: s = "A" + s + "C"
    elif N%3 == 1: s = "A" + s
    s = list(s)

    mx = sum(s[i] < s[j] for j in range(N) for i in range(j))
    if not (0 <= K <= mx): return ""
    if K == 0: return "A"*N

    s = s[::-1]
    cnt = 0
    while cnt < K:
        for i in range(N-1):
            if s[i] > s[i+1]:
                s[i],s[i+1] = s[i+1],s[i]
                cnt += 1
            if cnt == K: break
    return "".join(s)