Google Code Jam Round1A/Qualification Round 2015 レビュー
Round1A
Dashboard - Round 1A 2015 - Google Code Jam
- とりあえずContest analysisを見ないでトライ
- 制限時間（２時間３０分）で、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
- Contest Analysis Dashboard - Qualification Round 2015 - Google Code Jam
- まさに、これ↓に気付けなかった
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
