寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列

アルゴ式(beta版)の「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列

僕が作成、提出したコードは、以下のとおりです。

Q1. ハッシュ

algo-method.com

/*
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. ハッシュの衝突

algo-method.com

/*
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. ハッシュテーブル

algo-method.com

/*
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)

algo-method.com

/*
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. 文字列の種類数

algo-method.com

/*
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)

algo-method.com

/*
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)

algo-method.com

/*
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. アナグラムになる確率

algo-method.com

/*
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. 4つの整数 (2)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」6章:ハッシュテーブルと連想配列
Q9. 4つの整数 (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