Google code jam 2014 Round 1B ◯△△

ねむくてつらかった
A-small、A-largeとB-smallとC-smallを解けて824位、1000位以内なので一応Round2まではいけるっぽい

Problem A. The Repeater

文字列が\(N\)個与えられる
ある文字の次に同じ文字を付け足すか、連続してる同じ文字を1文字削除するかの2つの操作が行える。
全部の文字を同じにするのに最小の操作回数を答える。
ただし同じにできない場合には'Fegla Won'と出力

解法

それぞれの文字列で文字がちゃんと対応しているか確かめる。
対応している部分について文字の長さをソートしてから、それぞれの文字列に合わせるときの操作回数を計算する(現在注目している文字の長さよりも短いものの個数と長いものの個数がわかれば差分が簡単に求められる)
計算量は、テストケース数を\(T\)、文字列の数を\(N\)、文字列の長さを\(L\)としたとき、\(O(TLN\log N)\)

以下ちょっと汚いコード

import sys
import collections

T = int(raw_input())
for t in xrange(1, T + 1):
    N = input()
    
    text = [raw_input().strip() for i in xrange(N)]
    
    cur = [0] * N
    L = map(len, text)
    result = 0
    fail = False
    while cur[0] < L[0]:
        char = text[0][cur[0]]
        temp = cur[:]
        for i in xrange(N):
            while cur[i] < L[i] and text[i][cur[i]] == char:
                cur[i] += 1
        diff = [cur[i] - temp[i] for i in xrange(N)]
        diff.sort()
        s = sum(diff)
        s2 = sum(diff)
        ii = 0
        for i in xrange(N):
            s2 -= (diff[i] - ii) * (N - 1 - i + 1)
            s2 += (diff[i] - ii) * (i)
            s = min(s, s2)
            ii = diff[i]
        result += s
        for i in xrange(N):
            if cur[i] - temp[i] == 0:
                print "Case #{0}: {1}".format(t, 'Fegla Won')
                fail = True
                break
        if fail:
            break
    if fail:
        continue
    for i in xrange(N):
        if cur[i] < len(text[i]):
            print "Case #{0}: {1}".format(t, 'Fegla Won')
            break
    else:
        print "Case #{0}: {1}".format(t, result)

Problem B. New Lottery Game

\(A\)未満の数と\(B\)未満の数の論理積(AND)を取った時に\(K\)未満になる組み合わせの数を答える。

smallは単純に実装すれば良い
計算量は\(O(AB)\)

import sys
import collections

T = int(raw_input())
for t in xrange(1, T + 1):
    result = 0
    A, B, K = map(int, raw_input().split())
    for i in xrange(A):
        for j in xrange(B):
            if i & j < K:
                result += 1
    print "Case #{0}: {1}".format(t, result)

Problem C. The Bored Traveling Salesman

各ノードに文字列がついたグラフが与えられる。
深さ優先探索(？)で行き掛け順に文字列を足していく時の最小の文字列を答える。

smallは単純に全通り試せばよい

import sys
import collections
import random
import itertools

T = int(raw_input())
for t in xrange(1, T + 1):
    N, M = map(int, raw_input().split())
    code = []
    for i in xrange(N):
        code.append(input())
    neighbor = collections.defaultdict(list)
    for i in xrange(M):
        x, y = map(int, raw_input().split())
        neighbor[x - 1].append(y - 1)
        neighbor[y - 1].append(x - 1)
    result = '99999999'*10
    if N == 1 and M == 0:
        print "Case #{0}: {1}".format(t, code[0])
        continue
    for p in itertools.permutations(xrange(N)):
        cur = [p[0]]
        temp = str(code[cur[-1]])
        success = False
        for n in p[1:]:
            while cur:
                if n not in neighbor[cur[-1]]:
                    cur.pop()
                    continue
                else:
                    cur.append(n)
                    temp += str(code[cur[-1]])
                    if n == p[-1]:
                        success = True
                    break
        else:
            if success:
                result = min(temp, result)
    
    print "Case #{0}: {1}".format(t, result)