ABC045 D すぬけ君の塗り絵
//const ll MOD=(ll)1e9+7; //const ll inf=(ll)1e14; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; ll n,m,h,w; string s; map<pair<int,int>,ll> mp; int x[100001],y[100001]; ll ans[10]; 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>>h>>w>>n; for(int i=0;i<n;i++){ cin>>y[i]>>x[i]; x[i]--;y[i]--; for(int j=-2;j<=0;j++){ for(int k=-2;k<=0;k++){ if(y[i]+j<0 || y[i]+j+2>=h)continue; if(x[i]+k<0 || x[i]+k+2>=w)continue; mp[make_pair(y[i]+j,x[i]+k)]++; } } } for(auto ite=mp.begin();ite!=mp.end();ite++){ //auto temp=ite->fi; //int temp2=ite->se; //print((temp.fi),(temp.se),temp2); ans[ite->se]++; } ans[0]=(w-2)*(h-2)-(int)mp.size(); println__(ans,ans+10); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 塗られた付近のデータだけ保存しとけば、残りは0個なのでね。
ABC036-D 塗り絵
const ll MOD=(ll)1e9+7; const ll inf=(ll)1e14; int n,m,h,w; vector<int> v[100001]; ll f[100001],g[100001]; bool fpast[100001],gpast[100001]; ll Rank[100001]; int r=0; void dfs(int now){ Rank[now]=r; r++; for(int i=0;i<(int)v[now].size();i++){ if(Rank[v[now][i]]!=inf)continue; dfs(v[now][i]); } } int memo(int now,int color){ if(color==0){ if(fpast[now])return f[now]; else { f[now]=memo(now,1); ll temp=1; for(int i=0;i<(int)v[now].size();i++){ if(Rank[v[now][i]]<Rank[now])continue; temp=((temp%MOD)*(memo(v[now][i],1)%MOD))%MOD; } f[now]=(temp+f[now])%MOD; fpast[now]=1; return f[now]; } }else{ if(gpast[now])return g[now]; else{ ll temp=1; for(int i=0;i<(int)v[now].size();i++){ if(Rank[v[now][i]]<Rank[now])continue; temp=(temp%MOD*memo(v[now][i],0)%MOD)%MOD; } g[now]=temp; gpast[now]=1; return g[now]; } } } 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-1;i++){ int a,b;cin>>a>>b; a--;b--; v[a].push_back(b); v[b].push_back(a); } for(int i=0;i<n;i++)Rank[i]=inf; dfs(0); print(memo(0,0)); #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- メモ化再帰なのはわかったけど、漸化式思いつかなかったなー
- こういうのって蟻本のってたっけ？
ABC061 D Score Attack
using namespace std; //const ll MOD=(ll)1e9+7; const ll inf=(ll)1e15; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; string s; ll d[1001]; vector<pair<int,ll> > v[1001]; bool used[1001]; void dfs(int now){ used[now]=1; for(int i=0;i<(int)v[now].size();i++){ if(!used[v[now][i].fi])dfs(v[now][i].fi); } } 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<m;i++){ int from,to; ll cost; cin>>from>>to>>cost; from--;to--; v[from].push_back({to,-cost}); } for(int i=0;i<n;i++){ d[i]=inf; } d[0]=0; ll temp=0; for(int i=0;i<=m+10;i++){ for(int j=0;j<n;j++){ int now=j; if(d[now]==inf)continue; for(int k=0;k<(int)v[now].size();k++){ if(d[now]+v[now][k].se>=d[v[now][k].fi])continue; d[v[now][k].fi]=d[now]+v[now][k].se; } } if(i==m)temp=d[n-1]; } bool circle=0; if(temp!=d[n-1])circle=1; if(circle){ print("inf"); }else{ print(-d[n-1]); } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
- 閉路があるだけじゃあ得点を無限に増やせる理由にならないことに気づきたい。
- これは多めにベルマンフォードで回して、ゴールの距離が更に近づいたかどうかで判定ができる。
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; }
- めっちゃめんどくさかった。。。
