Hatena::Grouptopcoder

cou929のTopCoder日記

2011-05-08

Google Code Jam 2011 Qual

21:08

A, B, C を提出. small, large ともに通ったので無事 round1 に進むことができました.

いつもは C++ なんですが. 今年は python でやっています. まあどっちにしろ一般的な言語です.

A. Bot Trust

シミュレーションするだけです. 計算量も問題なし.

T = int(raw_input())

for test_num in range(1, T + 1):
    ret = 0
    line = raw_input().split()
    N = int(line[0])
    seq = []

    for i in range(1, len(line), 2):
        seq.append((line[i], int(line[i+1])))

    cur_pos = {'O': 1, 'B': 1}
    others_duration = 0
    others_color = seq[0][0]

    for i in seq:
        color = i[0]
        dst = i[1]
        time = abs(cur_pos[color] - dst) + 1

        if others_color == color:
            ret += time
            others_duration += time
        else:
            if time > others_duration:
                diff = time - others_duration
                ret += diff
                others_duration = diff
            else:
                ret += 1
                others_duration = 1

        others_color = color
        cur_pos[color] = dst

    print "Case #{0}: {1}".format(test_num, ret)

B. Magicka

英語ゲー. Example も不親切だし, small input が combines / opposes 最大 1 のものなので, ちゃんと問題文をよく読んで実装しないといけません.

それを除くと, 実装はやや面倒ですが普通にシミュレーションするだけの問題です. 計算量も問題なし.

def check_comb(last, seq):
    for i in seq:
        if last == i[0]:
            return i[1]
    return False

def check_oppos(target, seq):
    for i in seq:
        if target.count(i) > 0:
            return True
    return False

T = int(raw_input())

for test_num in range(1, T + 1):
    line = raw_input().split()
    combs = {}
    oppos = {}
    spells = ""
    ret = []

    # parse
    idx = 0
    C = int(line[idx])

    i = 0
    while i < C:
        i += 1
        idx += 1
        seq = line[idx]
        if combs.has_key(seq[0]):
            combs[seq[0]].append((seq[1], seq[2]))
        else:
            combs[seq[0]] = [(seq[1], seq[2])]
        if combs.has_key(seq[1]):
            combs[seq[1]].append((seq[0], seq[2]))
        else:
            combs[seq[1]] = [(seq[0], seq[2])]

    idx += 1
    D = int(line[idx])

    i = 0
    while i < D:
        i += 1
        idx += 1
        seq = line[idx]
        if oppos.has_key(seq[0]):
            oppos[seq[0]].append(seq[1])
        else:
            oppos[seq[0]] = [seq[1]]
        if oppos.has_key(seq[1]):
            oppos[seq[1]].append(seq[0])
        else:
            oppos[seq[1]] = [seq[0]]

    idx += 1
    N = int(line[idx])
    spells = line[idx + 1]

    # proccess spells
    for s in spells:
        if len(ret) < 1:
            ret.append(s)
        else:
            cur = s
            # check combine
            last = ret[-1]
            if combs.has_key(cur):
                res = check_comb(last, combs[cur])
                if res:
                    cur = res
                    ret.pop()

            # check opposite
            if oppos.has_key(cur) and check_oppos(ret, oppos[cur]):
                ret = []
            else:
                ret.append(cur)

    print "Case #{0}: [{1}]".format(test_num, ", ".join(ret))

C. Candy Splitting

まずは small 用に全探索を書きました. 組み合わせの列挙にはビットを使いました.

import math

T = int(raw_input())
seq = []
ret = -1

def calc(pat1, pat2, sum, n):
    global seq
    global ret

    if n >= len(seq):
        if pat1 == pat2:
            ret = max(ret, max(sum, reduce(lambda x, y: x + y, seq) - sum))
        return

    calc(pat1 ^ seq[n], pat2, sum + seq[n], n + 1)
    calc(pat1, pat2 ^ seq[n], sum, n + 1)

for test_num in range(1, T + 1):
    ret = -1
    N = int(raw_input())
    seq = map(int, raw_input().split())
    total = reduce(lambda x,y: x+y, seq)

    for i in range(1, 2 ** N - 1):
        pat1 = 0
        pat2 = 0
        sum = 0

        for j in xrange(N):
            if i >> j & 1:
                pat1 ^= seq[j]
                sum += seq[j]
            else:
                pat2 ^= seq[j]

        if pat1 == pat2:
            ret = max(ret, max(sum, total - sum))

    ret = ret if ret != -1 else 'NO'
    print "Case #{0}: {1}".format(test_num, ret)

当然ですが large では 2 ^ 100 のループになってしまうので間に合いません.

はじめは dp で計算量を削減するのかと思い検討していたんですが全然できそうにありません. 小さいインプットで問題を手で解いていると,

  • 'NO' にならないのは入力のすべての xor が 0 になる場合
  • A xor B = 0 は A = B
  • よって一番小さいキャンディーセットをパトリックにあげるのが最適な戦略 (パトリック哀れ)

ということに気づきました. 実装後, 念のため全探索で解いた small のアウトプットと diff をとってみたところ一致したので安心して submit. 無事通りました.

T = int(raw_input())

for test_num in range(1, T + 1):
    N = int(raw_input())
    seq = map(int, raw_input().split())
    total = reduce(lambda x,y: x+y, seq)
    patrick_total = reduce(lambda x,y: x^y, seq)
    mini = min(seq)

    if patrick_total != 0:
        ret = 'NO'
    else:
        ret = total - mini

    print "Case #{0}: {1}".format(test_num, ret)

D. Goro Sort

できませんでした. そもそも期待値が出てきた時点で苦手意識が...

詳しくは公式の Contest analytics をどうぞ.

RuteRute2012/07/09 20:46Your cranium must be prtoecting some very valuable brains.

fzxitclfdifzxitclfdi2012/07/10 15:37DcsUB7 <a href="http://idndroelcvuo.com/">idndroelcvuo</a>

zglklfrsfzglklfrsf2012/07/10 21:3376nula , [url=http://ywddkghthnac.com/]ywddkghthnac[/url], [link=http://crdgakptayms.com/]crdgakptayms[/link], http://piqgffcdpjdz.com/

yhomaosajyhomaosaj2012/07/12 11:546nlduI <a href="http://qxqdvckgxidk.com/">qxqdvckgxidk</a>

otqvghxhcotqvghxhc2012/07/12 17:26FaJSvG , [url=http://yjempfikcskq.com/]yjempfikcskq[/url], [link=http://znebtdrnhbru.com/]znebtdrnhbru[/link], http://labvpfdclfqz.com/

okubmozookubmozo2017/11/01 07:57http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

epeigeabaepeigeaba2017/11/01 07:58http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

uvalajakonexeuvalajakonexe2017/11/01 08:11http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

afirayifulafirayiful2017/11/01 08:47http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

upojhipurupojhipur2017/11/01 11:14http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

aqafiobaqafiob2017/11/01 11:38http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

ozuvivirguozuvivirgu2017/11/01 11:53http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

zgluvepabuovezgluvepabuove2017/11/01 15:57http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

enenaeyenenaey2017/11/02 05:59http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

educoexobuboeducoexobubo2017/11/02 06:00http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

iqoyacraduiqoyacradu2017/11/02 06:12http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/

uqehuuzoyeyiyuqehuuzoyeyiy2017/11/02 06:14http://levitrageneric-cheapest-price.net/ - levitrageneric-cheapest-price.net.ankor <a href="http://cheapest-priceventolinonline.net/">cheapest-priceventolinonline.net.ankor</a> http://levitra-online-cheap.net/