ABC027-D ロボット
using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; string s; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>s; n=(int)s.size(); int now=0; vector<int> v; for(int i=n-1;i>=0;i--){ if(s[i]=='+'){ now++; }else if(s[i]=='-'){ now--; }else{ v.push_back(now); } } sort(v.begin(),v.end()); int ans=0; for(int i=0;i<(int)v.size();i++){ if(i<(int)v.size()/2){ ans+=-v[i]; }else ans+=v[i]; } print(ans); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 僕は入力される+と-にしか注目できませんでした。
- 視点を変えて、Mに注目すると見えるんですね。
ABC026-D 高橋君ボール1号
using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; const double eps=1e-10; int n,m,h,w; string s; double a,b,c; const double PI=acos(-1.0); bool check(double mid){ double f_t=a*mid+b*sin(c*mid*PI); if(f_t>100+eps){ return 1; }else return 0; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>a>>b>>c; double l=0,r; for(int i=1;;i++){ if(a*(double)i+b*sin(c*(double)i*PI)>100+eps){ r=i; l=i-1; break; } } for(int i=0;i<100;i++){ double mid=(l+r)/2; if(check(mid)){ r=mid; }else{ l=mid; } } print(l); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- こんなのも二分探索でいけるんですね。
ARC092-D Two Sequences
using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; string s; ll a[200001],b[200001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i<n;i++){ cin>>b[i]; } ll t=1; ll ans=0; for(int i=0;i<30;i++){ if(i!=0)t*=2; vector<int> v1,v2; for(int j=0;j<n;j++){ v1.push_back(a[j]%(2*t)); v2.push_back(b[j]%(2*t)); } sort(v2.begin(),v2.end()); int res=0; for(int j=0;j<n;j++){ int x=lower_bound(v2.begin(),v2.end(),t-v1[j])-v2.begin(); int y=lower_bound(v2.begin(),v2.end(),2*t-v1[j])-v2.begin(); int z=lower_bound(v2.begin(),v2.end(),3*t-v1[j])-v2.begin(); res+=y-x; res+=n-z; } if(res&1){ ans+=t; } } print(ans); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 解説動画見て実装
- なんかむちゃくちゃ遅かった
- k- bit目が1か0かが周期的であることに気づけなかった
- xorを考えるときは各 bitごとに区切って考えるのが定石だそうです(ツイッターで誰かが言ってました)
ARC092-C 2D Plane 2N Points
using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; string s; vector<pair<int,int> > aka,ao; bool past[101]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>n; for(int i=0;i<n;i++){ int a,b;cin>>a>>b; aka.push_back({a,b}); } for(int i=0;i<n;i++){ int a,b;cin>>a>>b; ao.push_back({a,b}); } sort(ao.begin(),ao.end()); int ans=0; for(int i=0;i<n;i++){ int maxy=-1; int res=-1; for(int j=0;j<n;j++){ if(past[j])continue; if(aka[j].fi<ao[i].fi && aka[j].se<ao[i].se){ if(maxy<aka[j].se){ res=j; maxy=aka[j].se; } } } if(res!=-1){ past[res]=1; ans++; } } print(ans); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 赤の点は左下にあるほど貴重なので、青の点と友達にするのは取れる赤の点のうち最も下にあるもの。
- これを最初に青のx座標でソートして行えば大丈夫。
- x座標でソートしたら、もう赤のx座標のことは考えなくていいよね。
ABC058 井井井/###
- 以前解いた時と解法が全く違ったので記念に。
- 前回は解説見て実装したからそれはそう。
- そう思うと解説のような綺麗な解き方するのは中々難しい。。
#include<bits/stdc++.h> #define fi first #define se second #define show(x) cout<<#x<<"="<<x<<"\n" typedef long long ll; template<typename T> void print_to(std::ostream &os,const char *,const char *tail,const T &fst){ os<<fst<<tail; } template<typename Fst,typename... Rst> void print_to(std::ostream &os,const char *del,const char *tail,const Fst &fst,const Rst &... rst){ os<<fst<<del; print_to(os,del,tail,rst...); } template<typename Iter> void print_to_(std::ostream &os,const char *del,const char *tail,Iter bgn,Iter end){ for(Iter it=bgn;it!=end;){ os<<*it; if(++it!=end)os<<del; else os<<tail; } } template<typename Fst,typename... Rst> void println(const Fst &fst,const Rst &... rst){ print_to(std::cout,"\n","\n",fst,rst...); } template<typename Fst,typename... Rst> void print(const Fst &fst,const Rst &... rst){ print_to(std::cout," ","\n",fst,rst...); } template<typename Iter> void println_(Iter bgn,Iter end){ print_to_(std::cout," ","\n",bgn,end); } using namespace std; const ll MOD=(ll)1e9+7; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; string s; ll x[100001],y[100001],sumy[100001],sumx[100001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>n>>m; for(int i=0;i<n;i++){ cin>>x[i]; } for(int i=0;i<m;i++){ cin>>y[i]; } for(int i=m-1;i>=0;i--){ if(i==m-1){ sumy[i]=y[i]; continue; } sumy[i]=y[i]+sumy[i+1]; } for(int i=n-1;i>=0;i--){ if(i==n-1){ sumx[i]=x[i]; continue; } sumx[i]=x[i]+sumx[i+1]; } ll sumyy=0; for(int i=0;i<m;i++){ ll p=i; sumyy=(sumyy+MOD)%MOD+(sumy[p+1]+MOD)%MOD+-(((m-1-p)%MOD)*(y[p]%MOD)+MOD)%MOD; sumyy%=MOD; //print(sumyy); } ll sumxx=0; for(int i=0;i<n;i++){ ll p=i; sumxx=(sumxx+MOD)%MOD+(sumx[p+1]+MOD)%MOD-(((n-1-p)%MOD)*(x[p]%MOD)+MOD)%MOD; sumxx%=MOD; } //show(sumxx); //show(sumyy); print((((sumxx+MOD)%MOD)*((sumyy+MOD)%MOD)+MOD)%MOD); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
yukicoder No.513 宝探し2
- 最初三分探索してた。二分探索で良いのにね。
- 最初にxを探して、見つかったらマンハッタン距離の残りの差分がyまでの距離だから、yは探索しなくて済むね。
#include<bits/stdc++.h> using namespace std; inline int check(int minx,int maxx){ cout<<minx<<" "<<0<<"\n"; int d1;cin>>d1; if(d1==0)return -1; cout<<maxx<<" "<<0<<"\n"; int d2;cin>>d2; if(d2==0)return -1; if(d1==d2)return 0; else if(d1>d2)return 2; else return 1; } int main(){ int minx=0,maxx=100000; int resx=0; bool flag=0; while(maxx-minx>1){ int temp=check(minx,maxx); if(temp==-1)return 0; else if(temp==0){ resx=(minx+maxx)/2; flag=1; break; }else if(temp==1){ maxx=(minx+maxx)/2; }else{ minx=(minx+maxx)/2; } } if(!flag){ int temp=check(minx,maxx); if(temp==1)resx=minx; else resx=maxx; } cout<<resx<<" "<<0<<endl; int dd;cin>>dd; cout<<resx<<" "<<dd<<endl; return 0; }
yukicoder No.561 東京と京都
- 全部探索したいよー(と思います)
- 2の100乗の計算なんて無理よ…
- じゃあ動的計画法(dp)じゃない？
- よし書こう
- 初期の位置は東京に注意しなきゃね。
#include<bits/stdc++.h> using namespace std; int n,d; int t[101],k[101]; long long dp[101][2]; int main(){ cin>>n>>d; for(int i=0;i<n;i++){ cin>>t[i]>>k[i]; } for(int i=0;i<n;i++){ for(int j=0;j<2;j++){ if(i==0 && j==1)continue;//初期に京都はありえないもんね。 if(j==0){ dp[i+1][j]=max(dp[i][j]+t[i],dp[i+1][j]); dp[i+1][1]=max(dp[i][j]+k[i]-d,dp[i+1][1]); }else{ dp[i+1][j]=max(dp[i][j]+k[i],dp[i+1][j]); dp[i+1][0]=max(dp[i][j]+t[i]-d,dp[i+1][0]); } } } cout<<max(dp[n][1],dp[n][0])<<"\n"; return 0; }
