Google Code Jam Round 1B 2014

A. The Repeater

文字列の組が与えられたとき、a→aaやaa→aという操作を繰り返して、全ての文字列を等しくする最小手数は？

各文字ごとに何文字に揃えるのかを全探索。

※~~↓このコードはLarge落ちた。~~提出ミスだった。

def minify(s):
    r = ""
    for i in range(len(s)):
        if i==0 or s[i-1]!=s[i]:
            r += s[i]
    return r

def toarray(s):
    a = []
    for i in range(len(s)):
        if i==0 or s[i-1]!=s[i]:
            a += [1]
        else:
            a[-1] += 1
    return a
    
def solve(S):
    if len(set(minify(s) for s in S)) > 1:
        return "Fegla Won"

    A = [toarray(s) for s in S]

    ans = 0
    for p in range(len(A[0])):
        a = 99999999
        for x in range(
            min(a[p] for a in A),
            max(a[p] for a in A)+1):
            a = min(a, sum(abs(a[p]-x) for a in A))
        ans += a
    
    return ans

for i in range(input()):
    N = input()
    S = [raw_input() for _ in range(N)]
    a = solve(S)
    print "Case #%s: %s" % (i+1, a)

B. New Lottery Game

正数A, B, Kに対して、a

xがXより小さいとは、Xのiビット目が1で、xのiビット目が0で、iより上位のビットではXとxが等しいというiが存在することである。A, B, Kそれぞれに対してそのようなビットの位置を決め、それを満たす(a,b)が何通りあるかを数えた。場合分けが煩雑になってしまったが、GCJではまずはナイーブなプログラムでSmallを通し、LargeのプログラムはSmallの入出力でテストするという手が使える。

Small

def solve(A, B, K):
    r = 0
    for a in range(A):
        for b in range(B):
            if (a&b)<K:
                r += 1
    return r

for t in range(input()):
    A, B, K = map(int, raw_input().split())
    print "Case #%s: %s" % (t+1, solve(A,B,K))

Large

def solve(A, B, K):
    r = 0
    for a in range(32):
     if A>>a&1:
        for b in range(32):
         if B>>b&1:
            for k in range(32):
             if K>>k&1:
                t = 1
                for i in range(32):
                    if i<k:
                        if i<a and i<b:
                            t *= 4
                        elif i<a or i<b:
                            t *= 2
                        else:
                            t *= 1
                    else:
                        x = K>>i&1
                        if i==k:
                            x = 0
                        if i<a and i<b:
                            t *= [3, 1][x]
                        elif i<a or i<b:
                            if i<a:
                                y = 0 if i==b else B>>i&1
                            else: # i<b
                                y = 0 if i==a else A>>i&1
                            if x==0 and y==0:
                                t *= 2
                            elif x==0 and y==1:
                                t *= 1
                            elif x==1 and y==0:
                                t *= 0
                            elif x==1 and y==1:
                                t *= 1
                        else:
                            y = (0 if i==a else A>>i&1) & (0 if i==b else B>>i&1)
                            if x==y:
                                t *= 1
                            else:
                                t *= 0
                r += t
    return r

for t in range(input()):
    A, B, K = map(int, raw_input().split())
    print "Case #%s: %s" % (t+1, solve(A,B,K))

C. The Bored Traveling Salesman

問題文の条件が分かりづらいけど、要は、

グラフの全域木を辿り行きがけ順で各ノードに与えられた文字列を連結する。辞書順最小の文字列を答えよ

どのノードを根としても当然全域木は得られるので、根は文字列が一番小さいノードを選べば良い。辞書順最小の文字列を答えるので、あとは移動可能なノードのうち文字列が最小のものを選んで行けば良い。移動可能なノードとは、現在地点からの帰り道の途中から移動できて、そのノードに移動したとしても残りの全てのノードを辿れるもの。残り全てのノードを辿れるかどうかは、これまでに通ったノードのうち帰り道以外のものを全て削除して、グラフが連結かどうかを調べれば良い。

import itertools

def solve(N, Z, F):
    p = Z.index(min(Z))
    ans = Z[p]
    S = [p]
    V = [False]*N
    V[p] = True

    for _ in range(N-1):
        next = -1
        for p in range(N):
            if V[p]:
                continue

            s = S[:]
            while len(s)>0 and not F[s[-1]][p]:
                s.pop()
            if len(s)==0:
                continue

            s += [p]
            v = V[:]
            c = [False]*N
            while len(s)>0:
                q = s.pop()
                v[q] = True
                for i in range(N):
                    if F[q][i] and not v[i]:
                        s += [i]
                    c[q] = True

            ok = True
            for i in range(N):
                if not v[i] and not V[i]:
                    ok = False

            if ok and (next<0 or Z[p]<Z[next]):
                next = p

        ans += Z[next]
        while not F[S[-1]][next]:
            S.pop()
        S += [next]
        V[next] = True

    return ans

for t in range(input()):
    N, M = map(int, raw_input().split())
    Z = [raw_input() for _ in range(N)]
    F = [[False]*N for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x)-1, raw_input().split())
        F[a][b] = F[b][a] = True
    print "Case #%s: %s" % (t+1, solve(N,Z,F))