アルゴ式（beta版）の「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
C++による「設計技法とデータ構造 (#毎日アルゴ式)」貪欲法の解答例
僕が作成、提出したコードは、以下のとおりです。
Q1-1. 1 円玉と 5 円玉
/* 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)
/* 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. コイン問題
/* 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. 荷物と箱
/* 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)
/* 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. 巡回セールスマン問題 (貪欲法)
/* 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. 区間スケジューリング問題
/* 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
