Code Jam Japan 2011 報告

昨日書いた Google Code Jam Japan 2011 の予選が先程おわりました。
問題サイズに対する見積りがあまくて、最初の2問の Large を速攻で落とすという痛い失態をかましてしまい、3問目だけは慎重に解いてなんとか正解して本戦に残ることが出来ました。

Large は提出期限が切れた後も解き続け、予選終了後の演習モードで再提出してみたら、ちゃんと正解できましたので、本番もそのくらい慎重にやれ、ってことですかね。

とりあえず、(ちゃんと解いたんだぞ、という証明代わりに)全3問の解答と解説をこちらに貼っておきます。(あ、昨日貼ったテンプレートを使用しているので、実際に問題を解いているのは solve 関数の中だけですよ。)

あとで解いてみようと思っている人は、以下は読まないように注意!

(2011-10-02 追記： ちゃんとデキる人が書いてくれている解説を見つけたので、参考にする人はそちらをどうぞ → 不確定な Android Blog - Google Code Jam Japan 2011 予選終了 )

A. カードシャッフル

シャッフルマシーンが特定のパターンでカードをシャッフルした時のカード順を計算する問題。

カードの配列を持って、指定通りに並びかえれば、small は解けますが、Large だと配列のサイズが巨大になって扱いきれません。

問題の数値配分だと、カードの山は十分に切れず、連番数字があちこちにあるままになりますので、連番数字の部分を短縮して表現することで扱いやすくしています。

具体的には、連番部分を「(先頭の数字,続いている枚数)」で表し、カード山全体はその配列で表しました。

例えば 1〜100 のカードは

[ (1,100) ]

70〜100, 1〜69 と並んだカードは

[ (70,31), (1,69) ]

といった具合です。

あとは、このデータ型のまま「カードを切る」処理を実装してやればOK。

カードのカット回数は高々100回なので、配列の長さは最大でも 201 になります。Small と Large で変わるのはカードの総数だけなので、この形式で処理してやればは処理時間は同じです。

#!/usr/bin/env python2.6

import getopt
from collections import deque, defaultdict, namedtuple
from itertools import *
import multiprocessing
import os.path
from random import *
import sys

# utils
def read_numbers():
    return map(int, infile.readline().split())
def read_string():
    return infile.readline().rstrip('\r\n')
def list2str(*array):
    return ' '.join(map(str,array))

############################################################

def read_precond():
    # NoTC is number of testcases.  others are preconditions.
    (NoTC,) = read_numbers()
    return locals()

# testcase parser
def read_testcase():
    (M,C,W) = read_numbers()
    As = []
    Bs = []
    for c in range(C):
        (a,b) = read_numbers()
        As.append(a)
        Bs.append(b)
    del a, b
    return locals()

CardSequence = namedtuple('CardSequence', ['start', 'count'])

# solver
def solve(M,C,W,As,Bs,**rest):
    cards = (CardSequence(1,M),)
    for c in xrange(C):
        cards = cut(cards, As[c], Bs[c])

    for start,count in cards:
        if W <= count:
            return str(start + W - 1)
        else:
            W -= count 
            continue

def split_single(card, p):
    a, b = card
    if p == 0:
        return ((), (card,))
    elif p == b:
        return ((card,), ())
    else:
        return ((CardSequence(a,p),),(CardSequence(a+p,b-p),))

def split(cards, p):
    s = 0
    for i in xrange(len(cards)):
        if s + cards[i].count == p:
            return (cards[:i+1], cards[i+1:])
        if s + cards[i].count > p: 
            h1,h2 = split_single(cards[i], p - s)
            return (cards[:i] + h1, h2 + cards[i+1:])
        s += cards[i].count

def cut(cards, a, b):
    g1, g2 = split(cards, a - 1)
    g2, g3 = split(g2, b)
    return g2 + g1 + g3


############################################################
# random testcase
def rand_testcase():
    raise NotImplementedError, "Please implement rand_testcase() by yourself."
    #chars = [chr(x) for x in range(ord('a'), ord('z')+1)] + [' ']
    #Ls = [choice(chars) for x in range(1000)]
    #del chars, x
    return locals() 

############################################################

opt_single = True
opt_random = 0

try:
    opts, args = getopt.gnu_getopt(sys.argv[1:], "mr:")
    for o, a in opts:
        if o == '-m':
            opt_single = False
        elif o == '-r':
            opt_random = int(a)
        else:
            raise Exception("unknown option(%s)" % (o,))
    if opt_random:
        outfile = (sys.stdout,)
    else:
        infilename = args[0]
        outfilename = os.path.splitext(infilename)[0] + ".out"
        infile = open(infilename, 'r')
        outfile = (sys.stdout, open(outfilename, 'w'))
except Exception, e:
    print >>sys.stderr, e
    print >>sys.stderr, 'Usage: %s [-m] <inputfile>' % (sys.argv[0])
    print >>sys.stderr, '       %s -r num' % (sys.argv[0])
    exit(1);

if opt_random:
    num_tests = opt_random
    get_testcase = rand_testcase
else:
    precond = read_precond()
    num_tests = precond.pop("NoTC")
    get_testcase = read_testcase

# prepare testcase iterator
def read_testcases(num_tests):
    for i in range(num_tests):
        yield get_testcase()
testcases = read_testcases(num_tests)

# prepare solve iterator
def call_solve(q):
    d = dict(precond)
    d.update(q)
    return solve(**d)
if opt_single:
    res = imap(call_solve, testcases)
else:
    p = multiprocessing.Pool()
    res = p.imap(call_solve, testcases)

# solve & print
for (i, r) in enumerate(res, start=1):
    for f in outfile:
        print >>f, "Case #%d: %s" % (i, str(r))

B. 最高のコーヒー

複数種のコーヒーの賞味期限と残量と満足度を天秤にかけながら、最も満足度の総量が多くなる飲み方を求める、という問題で、多分3問中一番難しい問題です。

単に先に満足度の高い物を飲んでしまうと、次点の美味しいコーヒーの賞味期限が切れてしまいますので、解答のポイントは「最終日から逆順で飲むコーヒーを決めていくこと」になります。最終日まで賞味期限がもつ物の中で最も美味しい物をその日に飲むことにして予約し、その前日はそれを除いた残りから選んで……とくりかえせば良いわけです。

また、Large では日付けが異様に長いものがあるので、1日1日ずつ処理すると間に合いません。最終日に飲むコーヒーを決めたら、そのコーヒーは「いつからいつまで飲むのか」を数値で計算して、日付を飛ばしてやる必要があります。コーヒーの残り個数や次点のコーヒーの賞味期限などが複雑にからむので、ミスしやすく、気付きにくい所ですので、「BのLargeは提出したけど、不正解だった」って人も少くないかもしれません。

#!/usr/bin/env python2.7

import getopt
from collections import Counter, namedtuple
from itertools import *
import operator
import multiprocessing
import os.path
from random import *
import sys
from timeit import Timer
from copy import deepcopy

# utils
def read_numbers():
    return map(int, infile.readline().split())
def read_string():
    return infile.readline().rstrip('\r\n')
def list2str(*array):
    return ' '.join(map(str,array))

############################################################

def read_precond():
    # NoTC is number of testcases.  others are preconditions.
    (NoTC,) = read_numbers()
    return locals()

Coffs = namedtuple("Coffs", ["x_id", "count", "limit", "satisfy"])

# testcase parser
def read_testcase():
    (N, K) = read_numbers()
    cs = []
    ts = []
    ss = []
    coffs = []
    for i in range(N):
        (c,t,s) = read_numbers()
        cs.append(c)
        ts.append(t)
        ss.append(s)
        coffs.append(Coffs(i,c,t,s))
        #coffs.append(Coffs(*([i,] + read_numbers())))
    del i,c,t,s
    return locals()

# solver
def solve(N,K,coffs,**rest):
    left = Counter()
    for coff in coffs:
        left[coff] = coff.count

    total = 0
    k = K
    while k > 0:
        coffs.sort(key=lambda a: (min(a.limit,k), a.satisfy), reverse=True)
        if k > coffs[0].limit:
            k = coffs[0].limit
        # find next
        next_date = 0
        for coff in coffs:
            if coff.satisfy > coffs[0].satisfy:
                next_date = coff.limit
                break

        can_have = min(left[coffs[0]], k - next_date)

        #print total, next_date, coffs,k,can_have,left
        assert(can_have > 0)

        left[coffs[0]] -= can_have
        k -= can_have
        total += coffs[0].satisfy * can_have
        
        if left[coffs[0]] == 0:
            coffs.pop(0)
            if len(coffs) == 0:
                break

    return str(total)

def solve_small(N,K,cs,ts,ss,**rest):
    s_sort = sorted([(-ss[i],i) for i in range(N)])
    s_sort = [s_sort[i][1] for i in range(N)]
    total = 0
    for k in xrange(K,0,-1):
        for s in s_sort:
            if ts[s] >= k and cs[s] > 0:
                print "select: " + str(s)
                total += ss[s]
                cs[s] -= 1
                break
    return str(total)

solvers = filter(lambda a: a[0].startswith("solve"), globals().items())
solvers.sort()

############################################################
# random testcase
def rand_testcase():
    raise NotImplementedError, "Please implement rand_testcase() by yourself."
    #chars = [chr(x) for x in range(ord('a'), ord('z')+1)] + [' ']
    #Ls = [choice(chars) for x in range(1000)]
    #del chars, x
    return locals() 

############################################################

opt_single = True
opt_random = 0
opt_call_all_solvers = False

try:
    opts, args = getopt.gnu_getopt(sys.argv[1:], "mr:c")
    for o, a in opts:
        if o == '-m':
            opt_single = False
        elif o == '-r':
            opt_random = int(a)
        elif o == '-c':
            opt_call_all_solvers = True
        else:
            raise Exception("unknown option(%s)" % (o,))
    outfilename = None
    if not opt_random:
        infilename = args[0]
        outfilename = os.path.splitext(infilename)[0] + ".out"
        infile = open(infilename, 'r')
except Exception, e:
    print >>sys.stderr, e
    print >>sys.stderr, 'Usage: %s [-c] [-m] <inputfile>' % (sys.argv[0])
    print >>sys.stderr, '       %s [-c] -r num' % (sys.argv[0])
    exit(1);

if opt_random:
    num_tests = opt_random
    get_testcase = rand_testcase
else:
    precond = read_precond()
    num_tests = precond.pop("NoTC")
    get_testcase = read_testcase

# prepare testcase iterator
def read_testcases(num_tests):
    for i in range(num_tests):
        yield get_testcase()
testcases = read_testcases(num_tests)

# prepare solve iterator
def call_solve(q):
    d = dict(precond)
    d.update(q)
    if opt_call_all_solvers:
        res = dict()
        for name, func in solvers:
            res[name] = func(**deepcopy(d))
            print "SOLVER:", name, "  \tANSWER:", res[name]
        res = res.values()
        for r in res[1:]:
            if res[0] != r:
                raise RuntimeError, "ansers does not match"
        return res[0]
    else:
        return solve(**d)
if opt_single:
    res = imap(call_solve, testcases)
else:
    p = multiprocessing.Pool()
    res = p.imap(call_solve, testcases)

# open output file
if outfilename != None and not opt_call_all_solvers:
    outfile = (sys.stdout, open(outfilename, 'w'))
else:
    outfile = (sys.stdout,)

# solve & print
for (i, r) in enumerate(res, start=1):
    for f in outfile:
        print >>f, "Case #%d: %s" % (i, str(r))

C. ビット数

これは、与えられた数字 N を N = a + b の形に分解して、a と b を2進数表現した時の 1 のビットの数の合計が最大になる物を求める、という問題です。カンが働けば、コーディングは一番簡単でしょう。

紙に幾つか数字を書いて確認してみたところ、だいたいこんな感じで a と b を作ると、1が最大になるようでした。

N:  100100011001111
-------------------
a:   11111111111111
b:     100011010000

N の下から1が連続している部分と、それより上の部分に分けたうえで、a,bを眺めると、特徴がわかりますよね。なぜこうなるかは、Nの各桁の数字と、a+bの各桁の繰り上がりに注目すればわかるかと思います。

あとはこの数を数えるだけです。(下の解答は若干まわりくどい数えかたをしてしまっています。)

#!/usr/bin/env python2.6

import getopt
from itertools import *
import multiprocessing
import os.path
from random import *
import sys

# utils
def read_numbers():
    return map(int, infile.readline().split())
def read_string():
    return infile.readline().rstrip('\r\n')
def list2str(*array):
    return ' '.join(map(str,array))

############################################################

def read_precond():
    # NoTC is number of testcases.  others are preconditions.
    (NoTC,) = read_numbers()
    return locals()

# testcase parser
def read_testcase():
    (N,) = read_numbers()
    return locals()

# solver
def solve(N,**rest):
    b = list(format(N, 'b'))
    s = 0
    while len(b) > 0:
        if b[-1] == '1':
            s += 1
            b.pop()
        else:
            break
    if len(b) > 0:
        for x in b:
            if x == '1':
                s += 2
            else:
                s += 1
        s -= 1
    return str(s)

############################################################
# random testcase
def rand_testcase():
    raise NotImplementedError, "Please implement rand_testcase() by yourself."
    #chars = [chr(x) for x in range(ord('a'), ord('z')+1)] + [' ']
    #Ls = [choice(chars) for x in range(1000)]
    #del chars, x
    return locals() 

############################################################

opt_single = True
opt_random = 0

try:
    opts, args = getopt.gnu_getopt(sys.argv[1:], "mr:")
    for o, a in opts:
        if o == '-m':
            opt_single = False
        elif o == '-r':
            opt_random = int(a)
        else:
            raise Exception("unknown option(%s)" % (o,))
    if opt_random:
        outfile = (sys.stdout,)
    else:
        infilename = args[0]
        outfilename = os.path.splitext(infilename)[0] + ".out"
        infile = open(infilename, 'r')
        outfile = (sys.stdout, open(outfilename, 'w'))
except Exception, e:
    print >>sys.stderr, e
    print >>sys.stderr, 'Usage: %s [-m] <inputfile>' % (sys.argv[0])
    print >>sys.stderr, '       %s -r num' % (sys.argv[0])
    exit(1);

if opt_random:
    num_tests = opt_random
    get_testcase = rand_testcase
else:
    precond = read_precond()
    num_tests = precond.pop("NoTC")
    get_testcase = read_testcase

# prepare testcase iterator
def read_testcases(num_tests):
    for i in range(num_tests):
        yield get_testcase()
testcases = read_testcases(num_tests)

# prepare solve iterator
def call_solve(q):
    d = dict(precond)
    d.update(q)
    return solve(**d)
if opt_single:
    res = imap(call_solve, testcases)
else:
    p = multiprocessing.Pool()
    res = p.imap(call_solve, testcases)

# solve & print
for (i, r) in enumerate(res, start=1):
    for f in outfile:
        print >>f, "Case #%d: %s" % (i, str(r))