AtCoder Beginner Contest 123
はい。
https://atcoder.jp/contests/abc123
ooox 957(-19)でした。
A - Five Antennas
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define sc1(a) scanf("%d",&a) int main(){ int a[5],k; rep(i,5) sc1(a[i]); sc1(k); int f=1; rep(i,5) rep(j,5) if (abs(a[i]-a[j])>k) f=0; printf("%s\n",f==1?"Yay!":":("); return 0; }
Python3
d=[] for i in range(5): a=int(input()) d.append(a) k=int(input()) print("Yay!" if k>=d[-1]-d[0] else ":(")
最も離れている両端のアンテナが通信できれば全てのアンテナが通信できる。問題文をよく読んだり、kより大きいとかに気をつければ大丈夫だと思う。
B - Five Dishes
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define sc1(a) scanf("%d",&a) int main(){ int a,m=10,ans=0; rep(i,5) { sc1(a); int c=a%10; ans+=(a+(c>0?10-c:0)); if (c!=0) m=min(m,c); } printf("%d\n",ans+(m==0?0:m-10)); return 0; }
Python3
ans=chk=0 d=[] for i in range(5): x=int(input()) if x%10: d.append((x%10,x)) else: ans+=x d.sort(reverse=True) for i in d: ans+=((i[1]+10)//10)*10 if len(d): ans-=10-d[-1][1]%10 print(ans)
無駄な待ち時間がないように10の倍数のものを優先して消化する。端数があるものはmod10で余りが大きい物を優先して消化して、小さいものを最後に残す。サンプル2を見てそうなっているし、調理時間が1分のお皿と9分のお皿のどっちが早く出てくるかを考えてもそうなるはず。
C - Five Transportations
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define sl1(a) scanf("%lld",&a) int main(){ long long n,a,b=1e15+5,c,ans=0ll; sl1(n); rep(i,5) { sl1(a); b=min(a,b); } c=n/b+(n%b>0?1:0); printf("%lld\n",5+c-1); return 0; }
n=int(input()) d=[] ans=0 for i in range(5): x=int(input()) d.append(x) print(5+(n-1)//min(d))
最小値が重要そうな気がしながらかなり悩んだ。サンプル3からなんとか気づいて式を立ててACした。でもまぁ終わってみれば確かにA-Eで最小のものしか解答に影響しないですね。例えば
・A>Bの場合は、Aがどんなペースで人数を運んできても常にBは満員で運ぶ状態になる。
・A<Bの場合は、Aがどんなペースで人数を運んできても常にBは定員以下で運ぶ状態になる。
待ち時間や運行回数などを考える必要がないので人数とA-Eの最小だけで解答が決まると思う。あと提出したものでは、 print(5+(n-1)//min(d))
と書いているが、解説の式のほうが正しい考え方のような気がしますね。
D - Cake 123
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define sc1(a) scanf("%d",&a) #define sl1(a) scanf("%lld",&a) int main(){ int x,y,z,k; scanf("%d %d %d %d",&x,&y,&z,&k); vector<long long> a(x),b(y),c(z); rep(i,x) sl1(a[i]); rep(i,y) sl1(b[i]); rep(i,z) sl1(c[i]); sort(a.begin(),a.end(),greater<long long> ()); sort(b.begin(),b.end(),greater<long long> ()); sort(c.begin(),c.end(),greater<long long> ()); vector<long long> w(x*y); int p=0; rep(i,x) rep(j,y){ w[p]=a[i]+b[j]; p++; } sort(w.begin(),w.end(),greater<long long> ()); vector<long long> ans(min(x*y,3000)*z); p=0; for(int i=0;i<min(x*y,3000);i++) for (int j=0;j<z;j++) { ans[p]=w[i]+c[j]; p++; } sort(ans.begin(),ans.end(),greater<long long> ()); rep(i,k) printf("%lld\n",ans[i]); return 0; }
Python3
x,y,z,k=map(int,input().split()) a=[int(i) for i in input().split()] b=[int(i) for i in input().split()] c=[int(i) for i in input().split()] a.sort(reverse=True) b.sort(reverse=True) c.sort(reverse=True) if k<x: a=a[:k] if k<y: b=b[:k] if k<z: c=c[:k] d=[] ans=[] for i in a: for j in b: d.append(i+j) d.sort(reverse=True) if k<len(d): d=d[:k] for i in c: for j in d: ans.append(i+j) ans.sort(reverse=True) for i in range(k): print(ans[i])
a,bを逆順でソートしてk個以内でそれぞれの組合せを計算して、それをまたk個以内だけとcのk個以内との組合せを計算してソレの上位k個を解にしました。でも解説にもっときちんとした高速な方法が書いてありますね。
C++で解き直した際に1000 × 1000のループとか、 vecotorの ans(3,000,000) が不安というかダメそうと勝手に思っていたら余裕だったようです。