寝癖頭の解法

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

アルゴ式(beta版): C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例

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

C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例

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

Q1-1. 1 円玉と 5 円玉

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例
Q1-1. 1 円玉と 5 円玉
https://algo-method.com/tasks/359
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int ans=0;
    ans+=n/5;
    ans+=n%5;
    cout<<ans<<endl;
    return 0;
}
・Q1-2. お菓子 (1)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例
Q1-2. お菓子 (1)
https://algo-method.com/tasks/362
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int ans=0,snack=n;
    while(snack!=0){
        if(snack%2==0){
            snack/=2;
            ans++;
        }else{
            snack-=1;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
・Q1-3. コイン問題

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例
Q1-3. コイン問題
https://algo-method.com/tasks/360
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int x;
    cin>>x;
    vector<int> a(4);
    for(int i=0;i<4;i++){
        cin>>a[i];
    }
    int coin[4]={50,10,5,1};
    int ans=0;
    for(int i=0;i<4;i++){
        int c=x/coin[i];
        c=min(c,a[i]);
        ans+=c;
        x-=coin[i]*c;
    }
    cout<<ans<<endl;
    return 0;
}
・Q1-4. 荷物と箱

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例
Q1-4. 荷物と箱
https://algo-method.com/tasks/361
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    vector<int> b(m);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    int ans=0;
    vector<bool> tf(n,false);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(tf[j]){
                continue;
            }
            if(a[j]<=b[i]){
                ans++;
                tf[j]=true;
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
・Q1-5. お菓子 (2)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例
Q1-5. お菓子 (2)
https://algo-method.com/tasks/364
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int ans=0;
    while(n!=0){
        if(n%3==0){
            n/=3;
            ans++;
        }else{
            n-=1;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
・Q1-6. 巡回セールスマン問題 (貪欲法)

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例
Q1-6. 巡回セールスマン問題 (貪欲法)
https://algo-method.com/tasks/365
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
double f(vector<int> x,vector<int> y,int i,int j){
    return sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
}
int main(void){
    int n;
    cin>>n;
    vector<int> x(n),y(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    double ans=0.0;
    vector<bool> tf(n,false);
    tf[0]=true;
    int rnext=0;
    for(int i=0;i<n-1;i++){
        int point=-1;
        double dis=1000000.0;
        for(int j=0;j<n;j++){
            if(tf[j]){
                continue;
            }
            double ndis=f(x,y,rnext,j);
            if(dis>ndis){
                dis=ndis;
                point=j;
            }
        }
        tf[point]=true;
        ans+=dis;
        rnext=point;
    }
    ans+=f(x,y,rnext,0);
    cout<<setprecision(20)<<ans<<endl;
    return 0;
}
・Q1-7. 区間スケジューリング問題

algo-method.com

/*
C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例
Q1-7. 区間スケジューリング問題
https://algo-method.com/tasks/363
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> s(n),t(n);
    for(int i=0;i<n;i++){
        cin>>s[i]>>t[i];
    }
    vector<int> v(n);
    for(int i=0;i<n;i++){
        v[i]=i;
    }
    sort(v.begin(),v.end(),[&](int i,int j){return t[i]<t[j];});
    int ans=0;
    int endt=0;
    for(int i=0;i<n;i++){
        if(s[v[i]]<endt){
            continue;
        }
        ans++;
        endt=t[v[i]];
    }
    cout<<ans<<endl;
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com