ABC095(バーチャル):水色競プロerの復習
何だか最近このブログを読んでいただける方が増えてきました。
それも16時~20時の間が多いようです。
サークルか何かでしょうか?
ありがたいような恥ずかしいような感じですが、「この部分をもう少し詳しく」や「その考察に至った過程は?」などリクエストをいただければ極力お答えしたいと思います。
〇コンテスト名:ABC095
〇配点:不明
〇制限時間100分(A~Dまでの4問の時代のコンテスト)
〇今回の方針
本番のコンテストのつもりで解く
前回のABC096に引き続きノーミスを狙います。
コンテスト開始!
A - Something on It
ラーメン1杯700円
トッピングは3種あり、全て1つ100円
トッピングは〇、Xでする、しないが与えられるのでラーメンの価格を求めよ。
〇〇XやX〇Xの形で与えられるトッピング情報をきちんと読み取れるか?
という問題ですね。
countを使う等、方法はいくつかあるのでしょうが、
きっと一番単純なのは下の様に〇の数を数える方法でしょう。
S=input() T=0 for i in range(3): if S[i]=="o": T+=1 print(700+T*100)
1:38 AC
B - Bitter Alchemy
お菓子の素がXあり、N種のドーナツ(お菓子の素使用量はそれぞれmi)を作る。
全種類つくりつつたくさん作りたい。
最大いくつ作れるか求めよ。
まず全ての種類のドーナツを作り、後はお菓子の素の使用量の一番少ないドーナツを作れるだけ作れば良いですね。
問題はどうやってコードに落とし込むかですが、
listとsortとsumを使いましょう。
mはlistで受けて、listをsortすればmの一番小さいものは一番前へ、またlistに対してsumを使えば、listの中身の合計が求められます。
と文章で書いてもわかりにくいので、
コードをどうぞ。
N,X=map(int,input().split()) L=[] for i in range(N): m=int(input()) L.append(m) L.sort() X-=sum(L) print(N+X//L[0])
4:00 AC
C - Half and Half
AピザBピザと、Aピザ0.5枚とBピザ0.5枚分に相当するCピザがそれぞれA,B,C円である。
AピザとBピザをそれぞれX,Y枚ずつ欲しい。
必要な最低金額を求めよ。(ピザにあまりが出ても良い)
Cピザを買う枚数が決まればAピザ、Bピザの必要枚数が決まります。
また、Cピザは必ず偶数枚(ゼロを含む)購入するので、
まずはansにありえない大きさの数字を入れておいて、
Cピザの枚数毎の合計金額を求め、それまでの最低金額が出たら更新します。
A,B,C,X,Y=map(int,input().split()) ans=10**10 for i in range(max(X,Y)+1): cnt=0 cnt+=C*2*i x=X-i y=Y-i cnt+=max(0,x*A) cnt+=max(0,y*B) if ans>cnt: ans=cnt print(ans)
8:17 AC
D - Static Sushi
円形状のテーブルに寿司があり、時計回りに動いた際の距離xとカロリーvが与えられる。
好きな向きに動き、好きな位置で退店して良いが、距離1を移動する毎に1カロリー消費する。
得られる最大カロリーを求めよ。
これは難しいですね。
過去に開設を読んで解いた問題ですので考え方は知っているのですが、それでも実装に時間がかかりました。
時計周りに進み、各寿司を食べた時点での(カロリーの合計ー移動距離)から開始地点に戻るための移動距離を引き、
反時計回りに各寿司を食べ進んで得られるカロリーを求める。
累積和を使い、時計回りに進んだ後、反時計回りに進んで得られる最大のカロリーの計算を高速化する。
同様に反時計周りから始める場合も計算する。
import sys import copy input=sys.stdin.readline N,C=map(int,input().split()) Arr=[] for i in range(N): x,v=map(int,input().split()) Arr.append([x,v]) Rev=copy.deepcopy(Arr) Arr=[[0,0]]+Arr Dis=[] for i in range(len(Arr)): Dis.append(Arr[i][0]) #print(Arr) Rev=Rev[::-1] for i in range(N): Rev[i][0]=C-Rev[i][0] Rev=[[0,0]]+Rev #print(Rev) RevDis=[] for i in range(len(Rev)): RevDis.append(Rev[i][0]) #print(RevDis) ArrV=[0] S=0 for i in range(1,N+1): S+=Arr[i][1] ArrV.append(S-Dis[i]) #print(ArrV) ArrVR=[0] for i in range(1,N+1): ArrVR.append(max(ArrVR[-1],ArrV[i])) #print(ArrVR) RevV=[0] S=0 for i in range(1,N+1): S+=Rev[i][1] RevV.append(S- RevDis[i]) #print(RevV) RevVR=[0] for i in range(1,N+1): RevVR.append(max(RevVR[-1],RevV[i])) #print(RevVR) ans=0 for i in range(N+1): cnt=ArrVR[i]-Dis[i]+RevVR[N-i] ans=max(ans,cnt) for i in range(N+1): cnt=RevVR[i]- RevDis[i]+ArrVR[N-i] ans=max(ans,cnt) print(ans)
46:23 AC
46:23で全完(4完)0ペナ
Dは初見では厳しいですね。