ABC168 解説
かなりグダグダだったけど、今回のセットで全完できたのは結構偉いと思います。2100点(95:00)34位でした。
A - ∴ (Therefore)
思考
pythonとかなら楽だったなと思いながら、愚直に実装。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; n%=10; if(n==3) cout<<"bon"; else if(n==0 or n==1 or n==6 or n==8) cout<<"pon"; else cout<<"hon"; cout<<'\n'; }
B - ... (Triple Dots)
思考
場合わけしてやるだけ、Aより楽じゃね?
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int k; string s; cin>>k>>s; if(s.length()>k) cout<<s.substr(0,k)<<"..."<<'\n'; else cout<<s<<'\n'; }
C - : (Colon)
思考
気合で、2つの針のなす角を求めれば、余弦定理でできる。なす角は、12の向きからの時計回りの角度を求めて、差をよしなにすれば良い(よく考えるとよしなにしないでそのまま突っ込んでもcosの値に影響はない)。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ double a,b,h,m,H,M; constexpr double pi=3.14159265358979; cin>>a>>b>>h>>m; H=h*pi/6+m*pi/360; M=m*pi/30; cout<<setprecision(20)<<sqrt(a*a+b*b-2*a*b*cos(H-M))<<'\n'; }
D - .. (Double Dots)
思考
1からDFSして行けば最短経路がわかるので、DFSしながら手前の点を書き込んでいけば良い。
実装例
#include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> e[100000]; for(int i{};i<m;++i){ int a,b; cin>>a>>b; --a,--b; e[a].emplace_back(b); e[b].emplace_back(a); } queue<int> q; q.push(0); vector<int> ans(n,-1); ans[0]=0; while(!q.empty()){ int i=q.front();q.pop(); for(auto&j:e[i]) if(ans[j]<0){ ans[j]=i+1; q.push(j); } } cout<<"Yes"<<'\n'; for(int i{1};i<n;++i) cout<<ans[i]<<'\n'; }
E - ∙ (Bullet)
思考
仲の悪い条件を整理すると、0除算とかを一旦考えないことして適当に考えると
となる。なのでと言う比が重要であることがわかる。ここで、のものは誰が相手でも仲が悪いので、無視して、最後にその数だけ足せば良い。よってと考えて良い。重要なのは比なので、を比が変わらない様に、互いに素で、となるようにとりなおすことにする。これは同じ比のに対して一意に定まる。
mapなどを利用して、と(符号などは適切に変換する)の数をそれぞれとすると、これらの個の選び方はで、他のものの選び方とは独立している。よってこれらを適切に掛け算すれば良い。
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; struct modint; //いつもの modint pwr(ll,ll) //mod累乗 int main(){ ll n,a,b,d,c{}; using P=pair<ll,ll>; map<P,int> v0,v1; cin>>n; for(int i{};i<n;++i){ cin>>a>>b; if(a or b){ d=gcd(a,b); a/=d;b/=d; } else{ ++c; continue; } if(a<0) a=-a,b=-b; else if(a==0 and b<0) b=-b; v0[make_pair(a,b)]++; swap(a,b); b=-b; if(a<0) a=-a,b=-b; else if(a==0 and b<0) b=-b; v1[make_pair(a,b)]++; } map<P,bool> v; modint s{1}; for(auto&[p,y]:v0){ if(v[p]) continue; P q(p.second,p.first); q.second=-q.second; if(q.first<0) q.first=-q.first,q.second=-q.second; else if(q.first==0 and q.second<0) q.second=-q.second; v[q]=true; s*=pwr(2,y)+pwr(2,v1[p])-1; } cout<<s+c-1<<'\n'; }
F - . (Single Dot)
思考
いい性質が全然なさそうで、行ける場所をDFSなりBFSなりで全探索する以外できそうもないです。よく考えると、座標圧縮してやることで、個くらいしか考える必要がないので、気合入れて実装すれば通ります。
実装例
#include<bits/stdc++.h> using namespace std; using ll=long long; template<class T> void cc(vector<T> a,unordered_map<T,int>& nm,vector<int>& c){ //座標圧縮(aが座圧前、nmが前->後、cが後->前 sort(a.begin(),a.end()); fr(i,a.size()){ if(i<a.size()-1&&a[i]==a[i+1]) continue; nm[a[i]]=c.size(); c.emplace_back(a[i]); } } int main(){ int n,m; cin>>n>>m; vector<int> a(n),b(n),c(n),d(m),e(m),f(m),v(2*n+m+1),h(n+2*m+1); for(int i{};i<n;++i){ cin>>a[i]>>b[i]>>c[i]; v[i]=a[i]; v[i+n]=b[i]; h[i]=c[i]; } for(int i{};i<m;++i){ cin>>d[i]>>e[i]>>f[i]; v[i+n*2]=d[i]; h[i+n]=e[i]; h[i+n+m]=f[i]; } unordered_map<int,int> nmv,nmh; vector<int> V,H; cc(v,nmv,V);cc(h,nmh,H); auto lv=vector(V.size(),vector<bool>(H.size())); auto lh=vector(V.size(),vector<bool>(H.size())); for(int i{};i<n;++i){ a[i]=nmv[a[i]]; b[i]=nmv[b[i]]; c[i]=nmh[c[i]]; for(int I=a[i];I<b[i];++I) lv[I][c[i]]=true; } for(int i{};i<m;++i){ d[i]=nmv[d[i]]; e[i]=nmh[e[i]]; f[i]=nmh[f[i]]; for(int J=e[i];J<f[i];++J) lh[d[i]][J]=true; } ll ans{}; int X=nmv[0],Y=nmh[0]; stack<pair<int,int>> st; st.emplace(X,Y); int limv=V.size()-1,limh=H.size()-1; if(X==limv or Y==limh) return puts("INF"),0; auto vis=vector(limv,vector<bool>(limh)); while(!st.empty()){ auto[x,y]=st.top();st.pop(); if(vis[x][y]) continue; vis[x][y]=true; ans+=(ll)(V[x+1]-V[x])*(H[y+1]-H[y]); if(x==0 and !lh[x][y]) return puts("INF"),0; if(y==0 and !lv[x][y]) return puts("INF"),0; if(x+1==limv and !lh[x+1][y]) return puts("INF"),0; if(y+1==limh and !lv[x][y+1]) return puts("INF"),0; if(x>0 and !vis[x-1][y] and !lh[x][y]) st.emplace(x-1,y); if(y>0 and !vis[x][y-1] and !lv[x][y]) st.emplace(x,y-1); if(x+1<limv and !vis[x+1][y] and !lh[x+1][y]) st.emplace(x+1,y); if(y+1<limh and !vis[x][y+1] and !lv[x][y+1]) st.emplace(x,y+1); } cout<<ans<<'\n'; }
終わりに
タイトルが面白くていい感じですね。問題としても気合が結構要る感じで、†競技プログラミング†って感じがしました。楽しい。