アルゴ式（beta版）の「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
Q1. ハッシュ
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q1. ハッシュ https://algo-method.com/tasks/866 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll v[4]={1,30,900,27000}; ll Hash(string& s){ ll ss=s.size(); ll ret=0; for(ll i=0;i<ss;i++){ char c=s[ss-i-1]; ll n=c-'a'+1; ret+=n*v[i]; } return ret; } int main(void){ ll n; cin>>n; const ll m=810000; vector<ll> cnt(m,0); for(ll i=0;i<n;i++){ string s; cin>>s; cnt[Hash(s)]++; } ll q; cin>>q; for(ll i=0;i<q;i++){ string t; cin>>t; cout<<cnt[Hash(t)]<<endl; } return 0; }
Q2. ハッシュの衝突
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q2. ハッシュの衝突 https://algo-method.com/tasks/870 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; const ll b=30,m=1000003; ll v[10]; void init(void){ for(ll i=0;i<10;i++){ if(i==0){ v[i]=1; }else{ v[i]=v[i-1]*30%m; } } } ll Hash(string& s){ ll ss=s.size(); ll ret=0; for(ll i=0;i<ss;i++){ char c=s[ss-i-1]; ll n=c-'a'+1; ret+=n*v[i]; ret%=m; } return ret; } int main(void){ init(); ll n; cin>>n; vector<string> s(n); vector<ll> cnt(m,0); for(ll i=0;i<n;i++){ cin>>s[i]; cnt[Hash(s[i])]++; } cout<<*max_element(cnt.begin(),cnt.end())<<endl; return 0; }
Q3. ハッシュテーブル
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q3. ハッシュテーブル https://algo-method.com/tasks/878 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; struct Node{ Node* next; string str; Node(const string& str=""):next(NULL),str(str){} }; struct HashmapNode{ Node* nil; void init(void){ nil=new Node(); nil->next=nil; } void insert(Node* v){ v->next=nil->next; nil->next=v; } void erase(string &s){ Node *cur=nil,*curr=cur->next; while(curr!=nil){ if(curr->str==s){ cur->next=curr->next; delete curr; return; }else{ cur=curr; curr=cur->next; } } } bool search(string &s){ Node *cur=nil,*curr=cur->next; while(curr!=nil){ if(curr->str==s){ return true; }else{ cur=curr; curr=cur->next; } } return false; } }; const ll b=30,m=1000003; ll v[10]; void init(void){ for(ll i=0;i<10;i++){ if(i==0){ v[i]=1; }else{ v[i]=v[i-1]*30%m; } } } ll Hash(string& s){ ll ss=s.size(); ll ret=0; for(ll i=0;i<ss;i++){ char c=s[ss-i-1]; ll n=c-'a'+1; ret+=n*v[i]; ret%=m; } return ret; } int main(void){ init(); vector<HashmapNode> h(m); for(ll i=0;i<m;i++){ h[i].init(); } ll q; cin>>q; for(ll i=0;i<q;i++){ ll num; string t; cin>>num>>t; ll Num=Hash(t); if(num==0){ Node *v=new Node(t); h[Num].insert(v); }else if(num==1){ h[Num].erase(t); }else{ if(h[Num].search(t)){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } } } return 0; }
Q4. 挿入・削除・検索 (3)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q4. 挿入・削除・検索 (3) https://algo-method.com/tasks/868 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ unordered_map<string,ll> cnt; ll n; cin>>n; vector<string> a(n); 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; string t; cin>>num>>t; if(num==0){ cnt[t]++; }else if(num==1){ cnt[t]=0; }else{ cout<<cnt[t]<<endl; } } return 0; }
Q5. 文字列の種類数
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q5. 文字列の種類数 https://algo-method.com/tasks/879 提出コードの解答例 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> s; for(ll i=0;i<n;i++){ string S; cin>>S; s.push_back(S); } sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end()); cout<<s.size()<<endl; return 0; }
Q6. distinct にせよ (1)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q6. distinct にせよ (1) https://algo-method.com/tasks/881 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ unordered_map<ll,ll> cnt; ll n; cin>>n; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; cnt[a[i]]++; } ll ans=0; for(auto [i,j] : cnt){ if(j>1){ ans+=(j-1); } } cout<<ans<<endl; return 0; }
Q7. SNS クエリ (3)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q7. SNS クエリ (3) https://algo-method.com/tasks/871 提出コードの解答例 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)); map<vector<ll>,ll> cnt; for(ll i=0;i<n;i++){ cnt[tf[i]]++; } for(ll i=0;i<q;i++){ ll num; cin>>num; if(num==0){ ll x,y; cin>>x>>y; if(tf[y][x]==0){ cnt[tf[y]]--; tf[y][x]=1; cnt[tf[y]]++; } }else if(num==1){ ll x,y; cin>>x>>y; if(tf[y][x]==1){ cnt[tf[y]]--; tf[y][x]=0; cnt[tf[y]]++; } }else{ ll z; cin>>z; cout<<cnt[tf[z]]-1<<endl; } } return 0; }
Q8. アナグラムになる確率
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q8. アナグラムになる確率 https://algo-method.com/tasks/869 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; int main(void){ unordered_map<string,ll> cnt; ll n; cin>>n; vector<string> s(n); for(ll i=0;i<n;i++){ string S; cin>>S; s[i]=S; sort(S.begin(),S.end()); cnt[S]++; } ll all=n*(n-1)/2; ll same=0; for(auto i : cnt){ same+=i.second*(i.second-1)/2; } ld ans=(ld)same/all; cout<<fixed<<setprecision(10)<<ans<<endl; return 0; }
Q9. ４つの整数 (2)
/* C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列 Q9. ４つの整数 (2) https://algo-method.com/tasks/880 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ map<ll,bool> mp; ll n,m; cin>>n>>m; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++){ mp[a[i]*a[i]+a[j]*a[j]]=true; } } bool tf=false; for(auto i : mp){ tf=(tf || (mp[i.first] && mp[m-i.first])); } if(tf){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com
