AtCoder Beginner Contest 057 参加記
はい。 oo– 1240(レーティング変動なし)
http://abc057.contest.atcoder.jp
Aは割りと楽にだったけどもBは実装やや苦戦。Cは数十分かけて解法気付かずでおわり。
A - Remaining Time
Python3
a,b=map(int,input().split()) print((a+b)%24)
A時のB時間後はAとBの和で、0時を跨いで日付が変わったパターンの対応で24の剰余を取れば大丈夫だと思う。多分。
B - Checkpoints
Python3
n,m=map(int,input().split()) g={int(i):[] for i in range(n)} for i in range(n): x,y=map(int,input().split()) g[i].append((x,y)) for i in range(m): x,y=map(int,input().split()) for j in range(n): tmp=abs(g[j][0][0]-x)+abs(g[j][0][1]-y) if i==0: g[j].append(tmp) g[j].append(i) elif tmp<g[j][1]: g[j][1]=tmp g[j][2]=i for i in range(n): print(g[i][2]+1)
n人の学生のi番目の人の情報を入れられるような連想配列を用意しておいて、i番目の学生の現在の座標を放り込む。その後にチェックポイントの座標を受け取りながら全学生と現在入力受け取りのチェックポイントのマンハッタン距離を調べて連想配列に最も近い距離とチェックポイントの番目を記録しておく。入力受け取り終わりイコール計算終わりなので1からn番目までの学生の最も近いチェックポイントの番目を出力する。
C - Digits in Multiplication
Python3
import math n=int(input()) tmp=math.ceil(n**0.5)+1 ans=1000000 for i in range(1,tmp): if n%i==0: tmp=n//i ans=min(ans,len(str(tmp))) print(ans)
なぜかコンテスト中は1からnまで2重ループとかをしようとしてて間に合うわけ無いですがなをしてた。√nくらいで収まるはずなのに??を数十分して思いつかずでアニメ消化に逃げました。コンテスト後に1から√nまでの剰余が0になる数を探せばA * B = Nが成り立つ気がしたのでなんとかACに。
D - Maximum Average Sets
Python2
def pscl(num,l=[1]): for i in range(num): l = map(lambda x,y:x+y,[0]+l,l+[0]) return l n,a,b=map(int,raw_input().split()) v=[int(i) for i in raw_input().split()] chk=[i for i in set(v)] chk.sort() if len(chk)==1: print chk[0]*1.0 print sum(pscl(n)[a:b+1]) exit() d={} for i in v: if i in d: d[i]+=1 else: d[i]=1 total=ans=tmp=0 t=a for p,i in enumerate(chk[::-1]): if d[i]<t: total=total+i*d[i] t=t-d[i] elif p==0 and d[i]>=t: print i*1.0 print sum(pscl(d[i])[a:min(b,d[i])+1]) break else: total=total+i*t print total*1.0/a print pscl(d[i])[t] break
コンテスト後に10回目の提出でAC。。方針としては平均を最大にするには大きい方から最低のA個だけ使うのが最大になる。但し数列vの中で最大値がa個より多ければその個数分か、B個までをminで比較した個数までは使える。nCrを何とかすれば何とかなると思います。なお10回かかったのは例えば3 1 3, 2 2 1のような最大値がa個より多くb個より少ない場合とかでした。多分。
もっと必死に取り組んで大きい方から優先して使う、nCrで何となく計算するの方針立てて、複数パターンのテストケース自作して手動計算と照らし合わせれば調整すればコンテスト時間内ACも狙うべきだった気がする。