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/

buy kamagra 100mgbuy kamagra 100mg2018/04/06 12:56kamagra oral jelly come si usa
<a href="http://kamagrabst.com/">buy kamagra</a>
kamagra plus forum
<a href="http://kamagrabst.com/">super kamagra forum hr</a>
kamagra usa next day shipping
http://kamagrabst.com/
kamagra oral jelly 100mg side effects

kamagra 100 mgkamagra 100 mg2018/04/07 12:30super kamagra kaufen
<a href="http://kamagrabst.com/">buy kamagra 100mg oral jelly uk</a>
kamagra 100mg tablets reviews
<a href="http://kamagrabst.com/">kamagra gold 100mg rendeles</a>
kamagra oral jelly review forum
http://kamagrabst.com/
kamagra kopen nederland

DustintofDustintof2018/04/08 14:12buy cheap cialis online canada
<a href="http://justinpro.com/#">buy generic cialis online</a>
brand cialis by lilly
<a href="http://justinpro.com/#">buy generic cialis</a>
cialis going generic in 2017 in us
<a href="http://airvietnamairline.com/#">buy cialis online</a>
cialis generic vs. brand name
<a href="http://airvietnamairline.com/#">cialis generic</a>
cialis coupon 2018

WilliamFexWilliamFex2018/04/09 07:25coupons for cialis 20 mg
<a href="http://justinpro.com/#">cialis</a>
viagra compared to cialis dosage
<a href="http://justinpro.com/#">buy cialis online</a>
do cialis side effects go away
<a href="http://airvietnamairline.com/#">generic cialis online</a>
viagra e cialis genericos
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
generic for cialis daily 5 mg

WilliamFexWilliamFex2018/04/10 04:44side effects of prolonged use of cialis
<a href="http://justinpro.com/#">buy cialis</a>
cialis maximum daily dose
<a href="http://justinpro.com/#">cialis generic</a>
generic cialis availability date
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
5mg cialis daily generic
<a href="http://airvietnamairline.com/#">buy generic cialis</a>
cialis tablets 20mg price in india

WilliamFexWilliamFex2018/04/11 03:06viagra price versus cialis
<a href="http://justinpro.com/#">generic cialis online</a>
generic cialis soft tabs
<a href="http://justinpro.com/#">generic cialis online</a>
cialis super active+ 20mg pills
<a href="http://airvietnamairline.com/#">generic cialis</a>
generic cialis sales on amazon prime
<a href="http://airvietnamairline.com/#">generic cialis</a>
price comparison for viagra and cialis

WilliamFexWilliamFex2018/04/11 21:59cialis tadalafil 20mg how to use
<a href="http://justinpro.com/#">buy cialis online</a>
cialis tadalafil 20mg reviews
<a href="http://justinpro.com/#">cialis generic</a>
cialis professional vs viagra professional
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
cialis coupon for costco
<a href="http://airvietnamairline.com/#">generic cialis</a>
generic cialis lowest prices

WilliamFexWilliamFex2018/04/13 04:26will cialis go generic in nov 2017
<a href="http://justinpro.com/#">buy generic cialis online</a>
viagra cialis canadian pharmacy
<a href="http://justinpro.com/#">cialis</a>
compare cialis 5mg prices
<a href="http://airvietnamairline.com/#">generic cialis online</a>
precio de cialis generico en farmacias de espaГ±a
<a href="http://airvietnamairline.com/#">cialis generic</a>
best prices on generic cialis 5mg

WilliamFexWilliamFex2018/04/13 18:22viagra coupons walmart
<a href="http://amsboatyard.com/#">buy viagra</a>
names for generic viagra
<a href="http://amsboatyard.com/#">buy viagra online</a>
buy viagra online cheap usa
<a href="http://viagrapillq.com/#">viagra generic</a>
kamagra oral jelly viagra
<a href="http://viagrapillq.com/#">generic viagra</a>
viagra prices at sam's club

WilliamFexWilliamFex2018/04/14 09:15viagra preço rj
<a href="http://blessingsofbirth.com/#">buy viagra online</a>
viagra effects on men
<a href="http://blessingsofbirth.com/#">buy viagra</a>
viagra coupons free samples
<a href="http://timmonssoftware.com/#">viagra generic</a>
viagra coupons 2018
<a href="http://timmonssoftware.com/#">generic viagra</a>
viagra professional vs regular viagra

WilliamFexWilliamFex2018/04/14 22:59buy generic viagra india
<a href="http://blessingsofbirth.com/#">buy generic viagra online</a>
viagra feminino onde encontrar
<a href="http://blessingsofbirth.com/#">buy generic viagra online</a>
price of cialis vs viagra
<a href="http://timmonssoftware.com/#">buy viagra</a>
levitra vs cialis vs viagra
<a href="http://timmonssoftware.com/#">buy viagra online</a>
viagra preço

WilliamFexWilliamFex2018/04/15 12:56cialis coupons 2015
<a href="http://coastalseaplanes.com/#">buy cialis online</a>
cialis 30 lu tablet 20 mg
<a href="http://coastalseaplanes.com/#">cialis generic</a>
cialis vs viagra vs levitra which is better
<a href="http://northcoastgetaway.com/#">cialis generic</a>
donde puedo comprar cialis generico en mexico
<a href="http://northcoastgetaway.com/#">buy generic cialis</a>
cialis generic prices

WilliamFexWilliamFex2018/04/16 03:34cialis 5 mg daily side effects
<a href="http://justinpro.com/#">cialis generic</a>
generic cialis us store
<a href="http://justinpro.com/#">buy cialis online</a>
cialis extra dosage 200 mg
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
generic cialis pharmacy prices
<a href="http://airvietnamairline.com/#">buy cialis online</a>
cialis 5mg daily price in the united states

WilliamFexWilliamFex2018/04/17 08:47cialis generic in us
<a href="http://coastalseaplanes.com/#">buy generic cialis</a>
best price on 20 mg cialis brand
<a href="http://coastalseaplanes.com/#">buy cialis online</a>
main ingredient in cialis
<a href="http://northcoastgetaway.com/#">buy cialis</a>
cialis canadiam pharmacy
<a href="http://northcoastgetaway.com/#">generic cialis online</a>
cialis daily use side effect red eyes

WilliamFexWilliamFex2018/04/17 22:05cheap viagra cialis online
<a href="http://coastalseaplanes.com/#">cialis</a>
cialis 20 mg vs 5mg
<a href="http://coastalseaplanes.com/#">buy generic cialis online</a>
cialis coupons cvs printable
<a href="http://northcoastgetaway.com/#">buy generic cialis online</a>
cialis super active tadalafil 20mg
<a href="http://northcoastgetaway.com/#">generic cialis</a>
cost of stendra vs viagra cialis levitra

LouisDumLouisDum2018/04/26 08:55cost of generic cialis
<a href="http://cialisgrudj.com/">buy generic cialis online</a>
cialis soft uk
<a href="http://cialisgrudj.com/">buy generic cialis</a>
levitra vs viagra vs cialis reddit
http://cialisgrudj.com/
costco pharmacy cialis prices

JamesdokJamesdok2018/04/26 09:40generic brand for cialis 5mg online
<a href="http://cialispaxl.com/">cialis generic</a>
generic cialis from us pharmacy
<a href="http://cialispaxl.com/">buy cialis</a>
safe sites for generic cialis
http://cialispaxl.com/
redhead actress in cialis commercial

TrevorkapTrevorkap2018/04/26 16:54cialis side effects dangers or cialis
<a href="http://cialispaxl.com/">buy generic cialis</a>
generic cialis viagra levitra online
<a href="http://cialispaxl.com/">buy cialis online</a>
buy cialis canada pharmacy
http://cialispaxl.com/
generic cialis tadalafil release date

PeterFapPeterFap2018/04/27 00:08cialis generic price comparison
<a href="http://cialisgrudj.com/">buy generic cialis</a>
cialis 20mg directions
<a href="http://cialisgrudj.com/">cialis generic</a>
extra super cialis
http://cialisgrudj.com/
brand cialis australia

FrancistatFrancistat2018/04/27 03:13cialis tablet 20 mg
<a href="http://cialispaxl.com/">generic cialis</a>
cialis generico opinion
<a href="http://cialispaxl.com/">generic cialis</a>
cialis dosage reddit
http://cialispaxl.com/
cialis single dosage and timing

WilliamtobWilliamtob2018/04/27 08:205 mg or 20 mg cialis after prostate surgery
<a href="http://cialispaxl.com/">cialis generic</a>
viagra cialis levitra comparison chart
<a href="http://cialispaxl.com/">buy cialis online</a>
cialis dosage side effects
http://cialispaxl.com/
cialis side effects vision permanent

BillybeectBillybeect2018/04/27 14:59viagra cialis price comparison
<a href="http://cialisgrudj.com/">buy generic cialis</a>
effectiveness of cialis vs viagra vs levitra forum
<a href="http://cialisgrudj.com/">generic cialis online</a>
cialis 5mg price comparison australia
http://cialisgrudj.com/
cialis 5 mg uses

RobertSOPRobertSOP2018/04/27 19:09cialis 20mg dosing instructions
<a href="http://cialispaxl.com/">generic cialis online</a>
side effects of long term cialis use
<a href="http://cialispaxl.com/">generic cialis</a>
cost of generic cialis 5 mg at walmart
http://cialispaxl.com/
cialis 5 mg or 20 mg

AndrewRooksAndrewRooks2018/04/28 00:15cialis price comparison walmart
<a href="http://cialispaxl.com/">buy cialis online</a>
cialis vs viagra dose
<a href="http://cialispaxl.com/">buy generic cialis online</a>
cialis price vs viagra forum
http://cialispaxl.com/
generic cialis costco

JerrybokJerrybok2018/04/28 05:04effectiveness of cialis vs viagra vs levitra alcohol
<a href="http://cialispaxl.com/">generic cialis</a>
side effects of long term use of cialis
<a href="http://cialispaxl.com/">buy generic cialis</a>
viagra cialis levitra online pharmacy
http://cialispaxl.com/
cialis prices compare

KeithfefKeithfef2018/04/28 07:11best price viagra cialis
<a href="http://cialisgrudj.com/">buy generic cialis online</a>
cialis super active (tadalafil)
<a href="http://cialisgrudj.com/">generic cialis</a>
viagra cialis pharmacy
http://cialisgrudj.com/
cialis soft tabs 20mg

JamesMeariJamesMeari2018/04/28 10:13professional cialis vs regular cialis
<a href="http://cialispaxl.com/">cialis generic</a>
compare prices for cialis 5mg
<a href="http://cialispaxl.com/">cialis</a>
cialis viagra levitra online
http://cialispaxl.com/
cialis super active gГ©nГ©rique 20 mg

SidneyNicSidneyNic2018/04/28 15:25cialis vs viagra
<a href="http://cialispaxl.com/">buy generic cialis</a>
is there a generic cialis available in canada
<a href="http://cialispaxl.com/">buy generic cialis online</a>
specialist in cytotechnology salary
http://cialispaxl.com/
generic cialis is it safe

RogerlotRogerlot2018/04/28 20:39cialis pharmacy prices
<a href="http://cialispaxl.com/">buy generic cialis</a>
5mg generic cialis in usa
<a href="http://cialispaxl.com/">buy generic cialis online</a>
5mg cialis daily reviews
http://cialispaxl.com/
cialis generico precio en farmacias

JimmySinnyJimmySinny2018/04/28 22:23brand cialis lilly
<a href="http://cialisgrudj.com/">buy cialis</a>
cialis super active plus canada
<a href="http://cialisgrudj.com/">generic cialis</a>
cialis prices 2018
http://cialisgrudj.com/
cialis commercial female actors 2014