アルゴ式（beta版）の「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケットからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
Q1. 集計
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q1. 集計 https://algo-method.com/tasks/857 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> a(n),cnt(100001,0); for(ll i=0;i<n;i++){ cin>>a[i]; cnt[a[i]]++; } ll q; cin>>q; for(ll i=0;i<q;i++){ ll x; cin>>x; cout<<cnt[x]<<endl; } return 0; }
Q2. 最頻値
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q2. 最頻値 https://algo-method.com/tasks/860 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> a(n),cnt(500010,0); for(ll i=0;i<n;i++){ cin>>a[i]; cnt[a[i]]++; } ll m=-1; for(ll i=0;i<=500000;i++){ m=max(m,cnt[i]); } ll ans=-1; for(ll i=0;i<=500000;i++){ if(cnt[i]==m){ cout<<i<<endl; return 0; } } }
Q3. 挿入・削除・検索 (2)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q3. 挿入・削除・検索 (2) https://algo-method.com/tasks/858 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> a(n),cnt(100010,0); for(ll i=0;i<n;i++){ cin>>a[i]; cnt[a[i]]++; } ll q; cin>>q; for(ll i=0;i<q;i++){ ll num,v; cin>>num>>v; if(num==0){ cnt[v]++; }else if(num==1){ cnt[v]=0; }else{ cout<<cnt[v]<<endl; } } return 0; }
Q4. パングラム
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q4. パングラム https://algo-method.com/tasks/630 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<string> w(n); vector<ll> cnt(26,0); for(ll i=0;i<n;i++){ cin>>w[i]; for(ll j=0;j<w[i].size();j++){ char c=w[i][j]; ll num=c-97; cnt[num]++; } } for(ll i=0;i<26;i++){ if(cnt[i]==0){ cout<<"No"<<endl; return 0; } } cout<<"Yes"<<endl; return 0; }
Q5. SNSクエリ (2)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q5. SNSクエリ (2) https://algo-method.com/tasks/839 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,q; cin>>n>>q; vector<vector<ll>> tf(n,vector<ll>(n,0)); vector<ll> cnt(n,0); for(ll i=0;i<q;i++){ ll num; cin>>num; if(num==0){ ll x,y; cin>>x>>y; if(tf[x][y]==0){ tf[x][y]=1; cnt[y]++; } }else if(num==1){ ll x,y; cin>>x>>y; if(tf[x][y]==1){ tf[x][y]=0; cnt[y]--; } }else{ ll z; cin>>z; cout<<cnt[z]<<endl; } } return 0; }
Q6. 一致する確率
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q6. 一致する確率 https://algo-method.com/tasks/864 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; int main(void){ ll n; cin>>n; vector<ll> a(n),cnt(100001,0); for(ll i=0;i<n;i++){ cin>>a[i]; cnt[a[i]]++; } ll all=n*(n-1)/2; ll same=0; for(ll i=0;i<100001;i++){ ll num=cnt[i]; same+=num*(num-1)/2; } ld ans=(ld)same/all; cout<<fixed<<setprecision(10)<<ans<<endl; return 0; }
Q7. 数列クエリ
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q7. 数列クエリ https://algo-method.com/tasks/863 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> a(n),cnt(100010,0); ll sum=0; for(ll i=0;i<n;i++){ cin>>a[i]; cnt[a[i]]++; sum+=a[i]; } ll q; cin>>q; for(ll i=0;i<q;i++){ ll num; cin>>num; if(num==0){ ll v; cin>>v; cnt[v]++; sum+=v; }else if(num==1){ ll x,y; cin>>x>>y; sum-=cnt[x]*x; sum+=cnt[x]*y; cnt[y]+=cnt[x]; cnt[x]=0; }else{ cout<<sum<<endl; } } return 0; }
Q8. 共円
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q8. 共円 https://algo-method.com/tasks/859 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll q; cin>>q; vector<ll> p(q); for(ll i=0;i<q;i++){ cin>>p[i]; } const ll num=10000; vector<ll> cnt(2*num+1,0); for(ll x=-100;x<=100;x++){ for(ll y=-100;y<=100;y++){ cnt[x*x+y*y]++; } } for(ll i=0;i<q;i++){ cout<<cnt[p[i]]<<endl; } return 0; }
Q9. 4つの整数 (1)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q9. 4つの整数 (1) https://algo-method.com/tasks/861 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,m; cin>>n>>m; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } const ll num=1000000; vector<ll> v(2*num+1,0); for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++){ ll aa=a[i]*a[i]+a[j]*a[j]; v[aa]=1; } } for(ll i=0;i<2*num+1;i++){ if(i>m){ continue; } if(v[i]==1 && v[m-i]==1){ cout<<"Yes"<<endl; return 0; } } cout<<"No"<<endl; return 0; }
Q10. 倍数クエリ
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット Q10. 倍数クエリ https://algo-method.com/tasks/865 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; const ll m=500000; vector<ll> a(n),cnt(m+1,0); for(ll i=0;i<n;i++){ cin>>a[i]; cnt[a[i]]++; } vector<ll> v(m+1,-1); ll q; cin>>q; for(ll i=0;i<q;i++){ ll x; cin>>x; if(v[x]!=-1){ cout<<v[x]<<endl; }else{ ll ans=0; for(ll j=0;j<=m;j+=x){ ans+=cnt[j]; } cout<<ans<<endl; v[x]=ans; } } return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
