読者です 読者をやめる 読者になる 読者になる

Google Code Jam Round1A/Qualification Round 2015 レビュー

Round1A

Dashboard - Round 1A 2015 - Google Code Jam

  • とりあえずContest analysisを見ないでトライ
  • 制限時間(2時間30分)で、A-Small+A-Large+B-Small、まで正答(間違いなく合格圏外 orz)

Problem A. Mushroom Monster

  • 問題文を理解するのに時間がかかった
  • ネストは無くO(2n)なので問題無し
import sys

T=int(raw_input())
t=0
while t<T:
    n=int(raw_input())
    ms=map(lambda x:int(x),raw_input().split())

    eat1=0
    _max=0
    for i in range(0,len(ms)-1):
        eat1+= ms[i]-ms[i+1] if ms[i]>ms[i+1] else 0
        _max = ms[i]-ms[i+1] if ms[i]-ms[i+1]>_max else _max

    eat2=0
    for i in range(0,len(ms)-1):
        eat2+= _max if ms[i]>_max else ms[i]

    t+=1
    print "Case #%d"%t+": %d %d"%(eat1,eat2)

Problem B. Haircut

  • 3つ以上の最大公約数・最小公倍数を求める方法を確立
  • ただし、このメソッドだとLargeで最小公倍数がばかでかくなって解けない
import sys

def fgcd(a,b):
    if a%b==0: return b
    else:      return fgcd(b,a%b)

def flcm(a,b):
    if a<b: a,b=b,a 
    return  a*b/fgcd(a,b)

T=int(raw_input())
t=0
while t<T:
    bn=map(lambda x:int(x),raw_input().split())
    b=bn[0]
    n=bn[1]

    ms=map(lambda x:int(x),raw_input().split())

    lcm=ms[0]
    for m in ms[1:]: lcm=flcm(lcm,m)

    print >> sys.stderr, "lcm=%d"%lcm
    cnt=0
    for m in ms: cnt+=lcm/m
    print >> sys.stderr, "cnt=%d"%cnt

    bcnt=(n-1)%cnt
    print >> sys.stderr, "bcnt=%d"%bcnt
    if bcnt<b:
        ans=bcnt+1
    else:
        bcnt=bcnt-(b-1)
        _ms=list(ms)
        while bcnt>0:
            index=_ms.index(min(_ms))
            _ms[index]+=ms[index]
            bcnt-=1
        ans=index+1

    t+=1
    print "Case #%d:"%t+" %d"%ans
    print >> sys.stderr, "Case #%d:"%t+" %d"%ans

Qualification Round(レビュー)

Dashboard - Qualification Round 2015 - Google Code Jam

  • いつも通りとたかをくくって日曜日の朝から始めたら合格圏に届かなかった orz
  • 早くもBでつまづき、デバッグの甲斐なく時間切れ

Problem B. Infinite House of Pancakes

自分の回答

import sys

T=int(raw_input())
case=1
while case<T+1:
    d=raw_input().split()
    ps=map(lambda x:int(x), raw_input().split())

    ans=1<<31
    cnt=0

    while ans>cnt:
        #print ps,cnt,ans

        m=max(ps)
        if m%2==0:
            ps.append(m/2)
            ps.append(m/2)
        else:
            ps.append(m/2)
            ps.append(m/2+1)
        ps.remove(m)

        if cnt+m<ans:
            ans=cnt+m

        cnt+=1

    print "Case #"+str(case)+": "+str(ans)
    case+=1

Analysis

She replies quickly, "Your strategy is bad. Imagine that you had a plate of 9 pancakes. If we use your strategy, the best we can do is to split the plate into plates with 4 and 5 pancakes, and let the diners eat them. It costs us 6 minutes to end breakfast. But if you split the plate into three plates with 3 pancakes each (using 2 moves), we can finish breakfast in only 5 minutes!"
  • つまり
    • 9 -> 4, 5 -> 4, 2, 3 -> 2, 2, 2, 3 -> あとは毎分食べていくだけ(+3) => 6分後に朝食終了
  • ではなく

    • 9 -> 3, 6 -> 3, 3, 3 -> あとは毎分食べていくだけ(+3) => 5分後に朝食終了
  • 提案されているアルゴリズムでは

    • 9 -> 1, 8 -> 1, 1, 7 -> ... -> 1, 1, 1, 1, 1, 1, 1, 1, 1 -> あとは毎分食べていくだけ(+1) => 9分後に朝食終了
    • 9 -> 2, 7 -> 2, 2, 5 -> ... -> 2, 2, 2, 2, 1 -> あとは毎分食べていくだけ(+2) => 6分後に朝食終了
    • 9 -> 3, 6 -> 3, 3, 3 -> あとは毎分食べていくだけ(+3) => 5分後に朝食終了
    • 9 -> 4, 5 -> 4, 4, 1 -> あとは毎分食べていくだけ(+4) => 6分後に朝食終了
    • ...
  • の最小を取る
import sys

T=int(raw_input())
case=1
while case<T+1:
    d=int(raw_input())
    ps=map(lambda x:int(x), raw_input().split())

    ans=max(ps)
    for n in range(1,max(ps)):
        cnt=0
        for p in ps:
            # ceil(p/n)-1=(p-1)/n
            cnt+=(p-1)/n
        ans=ans if ans<cnt+n else cnt+n

    print "Case #"+str(case)+": "+str(ans)
    case+=1
  • 計算量はO(MN)(MAX(M*N)=1M)で、Largeだと4秒くらいかかった*1
  • アルゴリズムを改善することでもう少し計算量は落とせるらしい

*1:2.4GHz Core i5