ABC033 D 三角形の分類
using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const double PI=acos(-1.0); const double EPS=1e-10; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; string s; ll x[2001],y[2001]; 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>>x[i]>>y[i]; } ll ans1=0,ans2=0,ans3=0; for(int i=0;i<n;i++){ vector<double> v; for(int j=0;j<n;j++){ if(i==j)continue; v.push_back(atan2(y[j]-y[i],x[j]-x[i])); } sort(v.begin(),v.end()); for(int j=0;j<n-1;j++){ v.push_back(v[j]+2*PI); } for(int j=0;j<n-1;j++){ int a=lower_bound(v.begin(),v.end(),v[j]+PI/2-EPS)-v.begin(); int b=upper_bound(v.begin(),v.end(),v[j]+PI/2+EPS)-v.begin(); int c=lower_bound(v.begin(),v.end(),v[j]+PI)-v.begin(); ans2+=b-a; ans3+=c-b; } } ans1=(ll)n*(n-1)*(n-2)/6-ans2-ans3; print(ans1,ans2,ans3); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 2種類求めて全体から2種類分引いて残りを求めるのはわかるけど、慣れてないのもあって手が出なかった。
- 角度で持ってあげるのいいね。
- あとEPSの使い方がわからなかったので少し戸惑った(写真)
ABC049 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 k,l; class union_find{ public: explicit union_find(int _n):n(_n){ par.resize(static_cast<unsigned long>(_n)); rank.resize(static_cast<unsigned long>(_n)); sizes.resize(static_cast<unsigned long>(_n)); for(int i=0;i<_n;i++){ par[i]=i; rank[i]=0; sizes[i]=1; } } int find(int a){ if(par[a]==a)return a; return par[a]=find(par[a]); } bool same(int a,int b){ return find(a)==find(b); } void unite(int a,int b){ link(find(a),find(b)); } int size(int a){ return sizes[find(a)]; } void view(){ for(int i=0;i<n;i++){ cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":","); } for(int i=0;i<n;i++){ cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":","); } cout<<endl; } private: void link(int a,int b){ if(same(a,b))return; if(rank[a]>rank[b]){ par[b]=a; sizes[a]+=sizes[b]; //sizes[b]=0; }else{ par[a]=b; if(rank[a]==rank[b])rank[b]++; sizes[b]+=sizes[a]; //sizes[a]=0; } } int n; vector<int> par; vector<int> rank; vector<int> sizes; }; int ans[100001]; map<pair<int,int> ,int> mp; 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>>k>>l; union_find uf1(n); for(int i=0;i<k;i++){ int a,b;cin>>a>>b; a--;b--; uf1.unite(a,b); } union_find uf2(n); for(int i=0;i<l;i++){ int a,b;cin>>a>>b; a--;b--; uf2.unite(a,b); } for(int i=0;i<n;i++){ mp[make_pair(uf1.find(i),uf2.find(i))]++; } for(int i=0;i<n;i++){ if(i==n-1){ cout<<mp[make_pair(uf1.find(i),uf2.find(i))]<<endl; }else{ cout<<mp[make_pair(uf1.find(i),uf2.find(i))]<<" "; } } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- uf使う感じするよね。
- でも答えの求め方がわかんなかった。
- それぞれのufで同じグループだったらオッケーなのを思いつきたかったなぁ。
ABC030-D へんてこ辞書
using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; int n,a; string k; int b[100001]; int num[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>>a;a--; cin>>k; for(int i=0;i<n;i++){ cin>>b[i];b[i]--; } if((int)k.size()<=7){ ll h=stoi(k); int ans=a; for(int i=0;i<h;i++){ ans=b[ans]; } print(ans+1); }else{ for(int i=0;i<n;i++){ num[i]=-1; } int now=a; int t,circle; for(int i=0;;i++){ if(num[now]!=-1){ t=num[now]; circle=i-t; break; } num[now]=i; now=b[now]; } int h=0; for(int i=0;i<(int)k.size();i++){ h=(h*10+(int)(k[i]-'0'))%circle; } h-=t; if(h<0){ int temp=-h/circle; temp++; h+=circle*temp; } int ans=a; for(int i=0;i<t+h;i++){ ans=b[ans]; } print(ans+1); } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 最初、ダブリングだーって思って提出したらWAで、なんでやって制約見たら卒倒した。
- 閉路に入る前と後に分けるのが重要で、modとった後に閉路に入る前の分だけ引く。
- これでマイナスだとダメなので正の数に直してあげましょう。
ABC031-D 語呂合わせ
using namespace std; //const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; int n,k; string v[51],w[51]; int mojisuu[10]; bool check(){ map<char,string> mp; for(int i=0;i<n;i++){ int nowmojisuu=0; for(int j=0;j<(int)v[i].size();j++){ nowmojisuu+=mojisuu[v[i][j]-'0']; } if(nowmojisuu!=(int)w[i].size())return 0; int start=0; for(int j=0;j<(int)v[i].size();j++){ if(mp.count(v[i][j])){ string temp=""; for(int k=0;k<(int)mp[v[i][j]].size();k++)temp+=mp[v[i][j]][k]; string temp2=w[i].substr(start,mojisuu[v[i][j]-'0']); if(temp!=temp2)return 0; else{ start+=mojisuu[v[i][j]-'0']; } continue; } mp[v[i][j]]=w[i].substr(start,mojisuu[v[i][j]-'0']); start+=mojisuu[v[i][j]-'0']; } } for(int i=0;i<n;i++){ string now=""; for(int j=0;j<(int)v[i].size();j++){ now+=mp[v[i][j]]; } if(now!=w[i])return 0; } for(int i=0;i<k;i++){ cout<<mp[(char)(i+'1')]<<"\n"; } return 1; } void dfs(int nownum,int nowmojisuu){ mojisuu[nownum]=nowmojisuu; if(nownum==k){ if(check())exit(0); }else{ for(int i=1;i<=3;i++){ dfs(nownum+1,i); } } } 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>>k>>n; for(int i=0;i<n;i++){ cin>>v[i]>>w[i]; } for(int i=1;i<=3;i++){ dfs(1,i); } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- めっちゃめんどくさかった。。。
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ごとに区切って考えるのが定石だそうです(ツイッターで誰かが言ってました)
