寝癖頭の解法

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

アルゴ式(beta版): C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット

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

C++による「さまざまなデータ構造 (#毎日アルゴ式)」5章:バケット

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

Q1. 集計

algo-method.com

/*
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. 最頻値

algo-method.com

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

algo-method.com

/*
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. パングラム

algo-method.com

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

algo-method.com

/*
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. 一致する確率

algo-method.com

/*
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. 数列クエリ

algo-method.com

/*
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. 共円

algo-method.com

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

algo-method.com

/*
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. 倍数クエリ

algo-method.com

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