Google Code Jam-Qualification Round 2015
ルール
- 問題は全部で四問ある。4問それぞれにSmallデータセット、Largeデータセットの２つがあり、それぞれに配点がある。満点は100。
- 同じ点数なら、最初に提出してからの時間＋ペナルティ時間が短いほうの勝利。
- 27時間の間にとくプログラムを作成する。
- 各問題について、まずSmallのデータセットをダウンロードして、3分以内にそのデータセットに対する回答と、とくのに使ったプログラムを提出する。"InCorrect"に対しては4分のペナルティが課される。回答が"Rejected"(形式が違う)された場合は、再度提出できる。それ以外の場合、再提出はできない。
- Smallのデータセットに対して"Correct"判定をもらうと、Largeのデータセットにチャレンジすることができる。チャンスは１回のみ、ダウンロードしてから8分以内に回答を提出できなければ"InCorrect"となる。ただし、8分の間は何度でも提出し直すことができるが、最後に提出したもののみ採点対象となる。得点は一時的に追加されるが、コンテスト終了後に採点される。
- 20点以上獲得すればQualification Round突破
僕は、A-SL, B-SL, C-Sだけ解けました
C-Lも解けたのですが、対応に間に合わず、8分の間には提出できませんでした・・・
D問題、たまたま先日悩んで諦めた課題だったので、諦めました
代わりに（？）、こんなリンクを貼っておきます
正月の酔っ払い物理学者が数学者の皮を被った天使に出会うお話
全ユーザーの回答を
https://code.google.com/codejam/contest/6224486/scoreboard#vf=1
からダウンロードできます。
全ユーザーの回答を
https://code.google.com/codejam/contest/6224486/scoreboard#vf=1
からダウンロードできます。
以下、僕の回答です。
A問題：Standing Ovation
#coding:utf-8
fr=open("A-large.in","r")
output=""
ans=[]
casenum=0
count=0
for line in fr:
if count==0:
casenum=int(line)
else:
tmp=line.split()
Smax=int(tmp[0])
sumnum=0
level=0
tmpans=0
for a in list(tmp[1]):
number=int(a)
lack=level-sumnum
if lack <= 0:#ok
sumnum=sumnum+number
else:
tmpans=tmpans+lack
sumnum=sumnum+number+lack
level=level+1
ans.append(tmpans)
count=count+1
for i in range(0,casenum):
output=output+"Case #"+str(i+1)+": "+str(ans[i])+"\n"
fr.close()
fw=open("out.txt","w")
fw.write(output)
fw.close()
B問題：Infinite House of Pancakes
#coding:utf-8
#D人の客が、それぞれPi枚のパンケーキを持っている
#他の客は何もない
#一分に一枚食べる
#specialtimeは誰も食べない、パンケーキ有りの客からその他の客へパンケーキが移る
#できるだけ早くパンケーキをなくす
#kに展開した時のかかる時間数
simulate=lambda pan,k :sum([int((i-1)/k) for i in pan])+k
fr=open("B-large.in","r")
output=""
ans=[]
casenum=0
count=0
for line in fr:
if count==0:
casenum=int(line)
else:
if (count%2) == 0:#list
tmpans=10000
diners=list(map(int,line.split()))
for i in range(1,max(diners)+1):
tmp=simulate(diners,i)
if tmpans>tmp:
tmpans=tmp
ans.append(tmpans)
count=count+1
for i in range(0,casenum):
output=output+"Case #"+str(i+1)+": "+str(ans[i])+"\n"
fr.close()
fw=open("out.txt","w")
fw.write(output)
fw.close()
C問題：Dijkstra
#coding:utf-8
#四元数
def multi(b,a):#a*b
dic={"11":"1", "1i":"i", "1j":"j", "1k":"k","i1":"i", "ii":"-1","ij":"-k", "ik":"j","j1":"j", "ji":"k", "jj":"-1", "jk":"-i","k1":"k", "ki":"-j", "kj":"i", "kk":"-1"}
sign=["","-"]
signflag=0
if a[0]=="-":
signflag=signflag+1
a=a[1]
if b[0]=="-":
signflag=signflag+1
b=b[1]
res=dic[a+b]
if res[0]=="-":
signflag=signflag+1
res=res[1]
return sign[signflag%2] + res
def convert(tmpstring):
tmpc=tmpstring[0]
for c in tmpstring[1:]:
tmpc=multi(tmpc,c)
return tmpc
def main():
fr=open("C-large.in","r")
output=""
ans=[]
casenum=0
count=0
for line in fr:
if count==0:
casenum=int(line)
else:
if (count%2) == 1:#繰り返し回数
repeatnum=int(line.split()[1])
else:
print(len(ans))
tmpans=False
stringdata=line.replace("\n","")
rank=0
tmp="1"
converted=convert(stringdata)
for j in range(0,repeatnum):
#あとは残りがkであることを示すのみ
if rank == 2:
for fds in range(0,((repeatnum-j)%4)):
tmp=multi(tmp,converted)
break
#i,jすら見つからないのであきらめ
elif j>=9:
break
#とりまi,jを探しに行く
else:
for c in stringdata[0:]:
tmp=multi(tmp,c)
#ひとまずiを見つける、あればjを探す、
if rank==0:
if tmp=="i":
tmp="1"
rank=1
elif rank==1:
if tmp=="j":
tmp="1"
rank=2
if rank==2 and tmp=="k":
tmpans=True
if tmpans:
ans.append("YES")
else:
ans.append("NO")
count=count+1
for i in range(0,casenum):
output=output+"Case #"+str(i+1)+": "+str(ans[i])+"\n"
fr.close()
fw=open("out.txt","w")
fw.write(output)
fw.close()
main()
- まず気づかなければならないのは、"1"と等価な部分は右に含めても左に含めてもいいこと。つまり、"ijk"と等価なら、"i111jk"と等価なとき、当然"i11jk"、"i1jk","ijk"と等価なので、左から順にiを見つけ、jを見つけ、残りがkであればよい。
- large突破のポイントはループ対策。1111もiiiiもkkkkもjjjjも、すべて"1"と等価。より、n回同じものをかける場合は、n%4回かけるだけでよい
- Cython使おうとしましたがあまり変わりませんでした。
以上です。
