朝の競プロです！
A – Programming Education
A – Programming Education (atcoder.jp)
A問にしては少しややこしいです。
Nの入力が1か2かで入力の形式が変わることが注意です。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
if(N==1){
cout<<"Hello World"<<endl;
}
else{
int A,B;
cin>>A>>B;
cout<<A+B<<endl;
}
}
B – Time Limit Exceeded
B – Time Limit Exceeded (atcoder.jp)
問題文通りです。
(ci,ti)の組の中で、tiがT以下であるものの中で最小のciを探せばOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,T;
cin>>N>>T;
int ans=INT_MAX;
for(int i=0;i<N;i++){
int c,t;
cin>>c>>t;
if(t<=T){
ans=min(ans,c);
}
}
if(ans==INT_MAX) cout<<"TLE"<<endl;
else cout<<ans<<endl;
}
C – Pyramid
難問でした。
(xi,yi,hi)の入力の組から、ピラミッドの中心座標と高さを復元する問題。
ピラミッドには中心座標(CX,CY)と高さHが定まっており, 座標 (X,Y)の高度はmax(H−|X−CX|−|Y−CY|,0)
なので、(xi,yi,hi)から各座標が中心座標であった場合の高さは
見ている座標を(AX,AY)とした場合、 hi+|xi-AX|+|yi-AY|
となります。これを0<=AX,AY<=100の全パターンにして確認し、N個の入力で矛盾がなかった個所が中心座標となります。
気を付ける点はhi=0の場合です。中心座標からの高さの計算で、マイナスは0に補正されているため、hi=0は補正された値である可能性があります。
その可能性を考慮してコーディングしましょう。(私は考慮できておらず大量WA出してました。)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
long long xy[101][101];
for(int i=0;i<=100;i++){
for(int j=0;j<=100;j++){
xy[i][j]=-1;
}
}
vector<int> zx,zy;
for(int i=0;i<N;i++){
long long x,y,h;
cin>>x>>y>>h;
if(h==0){
zx.push_back(x);
zy.push_back(y);
xy[y][x]=-2;
}
else{
for(int j=0;j<=100;j++){
for(int k=0;k<=100;k++){
long long h2=h+abs(j-y)+abs(k-x);
if(xy[j][k]==-1) xy[j][k]=h2;
else if(xy[j][k]!=h2) xy[j][k]=-2;
}
}
}
}
for(int i=0;i<zx.size();i++){
int y=zy[i];
int x=zx[i];
for(int j=0;j<=100;j++){
for(int k=0;k<=100;k++){
long long h2=abs(j-y)+abs(k-x)+1;
if(xy[j][k]>=h2) xy[j][k]=-2;
}
}
}
for(int i=0;i<=100;i++){
for(int j=0;j<=100;j++){
if(xy[i][j]>0){
cout<<j<<" "<<i<<" "<<xy[i][j]<<endl;
return 0;
}
}
}
}
hi=0である個所は補正前の値が大きくても0であるため、hi+|xi-AX|+|yi-AY|より大きい場合は矛盾があるとしました。
D – Partition
最大公約数を最大化したいため、a1～aNは何かしらの値の倍数となり、その倍数を最大化すると言い換えられます。
倍数をAとしたとき、
a1+a2+....+aN=M α1A+α2A+.....+αNA=M (α1～αNは1以上の整数) A(α1+α2+.....+αN)=M
となります。括弧の中身は最小がN(全て1の場合)で最大は∞(大きさに上限なし)です。
そのため、MはA*N以上である必要があります。
また、A*(….)=MであるためAはMの約数である必要があります。
上記をコードに落としていきます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,M;
cin>>N>>M;
int ans=1;
for(int i=1;i<=sqrt(M)+2;i++){
if(M%i==0){
if(M/i>=N) ans=max(ans,i);
if(i>=N) ans=max(ans,M/i);
}
}
cout<<ans<<endl;
}
Aは線形探索していますが、MがAで割り切れる場合、M/Aでも割り切れます。(M/A=βなら、式変形してM/β=Aになる)
そのため、MがAの倍数であることを確認するついでにMがM/Aの倍数であることを確認すると、sqrt(M)以下と以上の範囲を同時に調べられるため、線形探索の範囲がsqrt(M)でOKになります。
コメント