paizaラーニング: C++による「ハッシュメニュー」問題集: ハッシュテーブルを使おう

paizaラーニングのレベルアップ問題集「ハッシュメニュー」からの出典です。
paiza.jp
C++による「ハッシュメニュー」問題集: 座標系での向きの変わる移動と、それらの提出コードの解答例です。

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

・STEP: 1 ハッシュテーブル(オープンアドレス法)

paiza.jp

/*
paizaラーニング: C++による「ハッシュメニュー」問題集: ハッシュテーブルを使おう
STEP: 1 ハッシュテーブル(オープンアドレス法)
https://paiza.jp/works/mondai/hash_problems/hash_problems__hashtable_step0
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll H(ll n){
    return (n%10);
}
ll H2(ll n){
    return (H(n)+1)%10;
}
int main(void){
    vector<ll> hash(11,-1);
    ll n;
    cin>>n;
    vector<ll> x(n);
    for(ll i=0;i<n;i++){
        cin>>x[i];
        if(hash[H(x[i])]==-1){
            hash[H(x[i])]=x[i];
        }else{
            ll num=H(x[i]);
            while(hash[num]!=-1){
                num=H2(num);
            }
            hash[num]=x[i];
        }
    }
    for(ll i=0;i<10;i++){
        cout<<hash[i]<<endl;
    }
    return 0;
}

・STEP: 2 ハッシュテーブル(チェイン法)

paiza.jp

/*
paizaラーニング: C++による「ハッシュメニュー」問題集: ハッシュテーブルを使おう
STEP: 2 ハッシュテーブル(チェイン法)
https://paiza.jp/works/mondai/hash_problems/hash_problems__hashtable_step1
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll H(ll n){
    return (n%10);
}
int main(void){
    ll n;
    cin>>n;
    vector<vector<ll>> hash(10);
    vector<ll> x(n);
    for(ll i=0;i<n;i++){
        cin>>x[i];
        hash[H(x[i])].push_back(x[i]);
    }
    for(ll i=0;i<10;i++){
        ll hs=hash[i].size();
        if(hs==0){
            cout<<"\n";
        }else{
            for(ll j=0;j<hs;j++){
                cout<<hash[i][j]<<((j==hs-1) ? "\n" : " ");
            }
        }
    }
    return 0;
}

・FINAL問題: ハッシュテーブルを使おう

paiza.jp

/*
paizaラーニング: C++による「ハッシュメニュー」問題集: ハッシュテーブルを使おう
FINAL問題: ハッシュテーブルを使おう
https://paiza.jp/works/mondai/hash_problems/hash_problems__hashtable_boss
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll a,b;
ll H(ll x){
    return (a*x+b)%100;
}
int main(void){
    vector<vector<ll>> hash(100);
    ll q;
    cin>>a>>b>>q;
    for(ll i=0;i<q;i++){
        ll n,x;
        cin>>n>>x;
        if(n==1){
            hash[H(x)].push_back(x);
        }else{
            bool tf=false;
            for(ll j=0;j<100;j++){
                ll cnt=count(hash[j].begin(),hash[j].end(),x);
                if(cnt>=1){
                    tf=true;
                    break;
                }
            }
            if(tf){
                cout<<"Yes"<<endl;
            }else{
                cout<<"No"<<endl;
            }
        }
    }
    for(ll i=0;i<100;i++){
        ll hs=(ll)hash[i].size();
        for(ll j=0;j<hs;j++){
            cout<<hash[i][j]<<((j==hs-1) ? "" : " ");
        }
        cout<<endl;
    }
    return 0;
}

paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。