はじめに
AtCoder Beginner Contest 194 – AtCoder
A,B,C,D,Eの5完でした。
0WAで27:22で解けたので271位と高順位でした。
パフォーマンス4も過去最高の2102が出て、Ratingも1662(+62)になりました。
次のコンテストで水落ちすると思っていましたが、一先ず安心ですね。(明日のAGCで死にそうですが…)
A – I Scream
昔のABCみたいな問題。問題文がややこしいですね。
問題文の通り実装していきます。
注意点は、入力が無脂乳固形分はと乳脂肪分なのに対し、判定は乳固形分と乳脂肪分です。問題文を読んで丁寧に処理しましょう。
#include<bits/stdc++.h>
using namespace std;
int main(){
int A,B;
cin>>A>>B;
A+=B;
if(A>=15&&B>=8) cout<<1<<endl;
else if(A>=10&&B>=3) cout<<2<<endl;
else if(A>=3) cout<<3<<endl;
else cout<<4<<endl;
}
B – Job Assignment
B – Job Assignment (atcoder.jp)
ややこしそうですが、Nが高々1000程度なのでO(N^2)が間に合います。
全パターン試して一番小さいものを採用しましょう。
注意点は仕事AとBを同じ人がこなす場合、かかる時間はA+Bになります。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
int A[N],B[N];
for(int i=0;i<N;i++){
cin>>A[i]>>B[i];
}
int ans=INT_MAX;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i==j) ans=min(ans,A[i]+B[j]);
else ans=min(ans,max(A[i],B[j]));
}
}
cout<<ans<<endl;
}
C – Squared Error
C – Squared Error (atcoder.jp)
難しい。
この手の式変形タイプの問題苦手です。
(Ai-Aj)^2を展開すると、2乗部分と2つを掛けた分が出てきます。
☆2乗部分 自分自身を除く、N-1個と差の2乗を取るので 2乗部分はN-1個できる ☆2つを掛けた部分 A1で考えると、-2A1A2-2A1A3-....-2A1ANのN-1個できる。 -2A1でくくると、-2A1(A2+A3+...+AN) A2+A3+...+ANはAsumを事前計算し、A1を引けばよい。
上記考えで、O(N)で求められます。
#include<bits/stdc++.h>
using namespace std;
int main(){
//2,8 2,4 8,4
long long N;
cin>>N;
long long A[N];
long long sum=0;
for(int i=0;i<N;i++){
cin>>A[i];
sum+=A[i];
}
long long ans=0;
for(int i=0;i<N;i++){
ans+=A[i]*A[i]*(N-1);
ans-=A[i]*(sum-A[i]);
//cout<<A[i]*A[i]*(N-1)<<" "<<2*A[i]*(sum-A[i])<<endl;
}
cout<<ans<<endl;
}
このコードだと、2AiAj部分で重複ができるため/2してAiAjとして計算しています。
D – Journey
確率の問題です。
グラフが4頂点の場合、
3/4が当たるまで繰り返す→2/4が当たるまで繰り返す→1/4が当たるまで繰り返す
となりそうです。それぞれの結果は互いに影響を与えないので期待値は、
N頂点の場合 (n-1)/nが当たるまで+(n-2)/nが当たるまで+....1/nが当たるまで
となります。
この当たるまでの期待値が分かれば解けるのですが、当たるまでの期待値は確率の逆数だといわれています。よって、求めたい期待値は
N頂点の場合 n(1/(n-1)+1/(n-2)+....1)
となります。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
double ans=0;
for(int i=N-1;i>=1;i--){
ans+=(double)N/i;
}
printf("%.12f\n",ans);
}
E – Mex Min
mexの説明がややこしいですが、要はM範囲の連続するAiの中で範囲内に含まれない最小の数字がmexです。範囲を動かしたときに、これを最小化するのがこの問題の目的です。
範囲に含まれない個数が知りたいので、数字の出てくる数をカウントすれば良さそうです。
ただ、範囲はN-K+1通りあるので、全てに対してカウントするとTLEします。
7 3 0 0 1 2 0 1 0 の場合 最小の範囲3には 0*2,1*1が出てくる。 範囲を1つ右に動かしたとき、 0 0 1 2 0 1 0 前 - - - 後 - - - 移動前の範囲の末端がなくなって、移動後の範囲の先端が増える。 なのでこの2つだけカウントすればよい。 また、知りたいのはカウント0である数字なので、移動前の範囲の末端に関してだけカウントが0になったかを調べればよい
こういうの尺取り法っていうんでしょうか？(厳密には違う?)
範囲内のカウントがO(1)になったので、十分高速に計算できます。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin>>N>>M;
int A[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
int c[N+10];
for(int i=0;i<N+10;i++) c[i]=0;
for(int i=0;i<M;i++){
c[A[i]]++;
}
int ans=INT_MAX;
for(int i=0;;i++){
if(c[i]==0){
ans=i;
break;
}
}
for(int i=M;i<N;i++){
c[A[i]]++;
c[A[i-M]]--;
if(c[A[i-M]]==0) ans=min(ans,A[i-M]);
}
cout<<ans<<endl;
}
おわりに
頭の中がHeuristic Contestで一杯一杯
これ毎月やられるとしんどいところありますね。
後、ABCで毎回早解きマンやると黄色になれそうなので少し頑張りたいと思います。
(AGC,ARCで溶かして±0になりそうですが…)
コメント