アルゴ式(beta版)の「設計技法とデータ構造 (#毎日アルゴ式)」二分探索からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。
C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例
僕が作成、提出したコードは、以下のとおりです。
Q2-1. 方程式を解く
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-1. 方程式を解く https://algo-method.com/tasks/368 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ld=long double; ld f(ld n){ return n*(n*(n+1)+2)+3; } int main(void){ ld n; cin>>n; ld left=0.0,right=100.0; while(right-left>0.00001){ ld mid=(left+right)/2; if(f(mid)<n){ left=mid; }else{ right=mid; } } cout<<left<<endl; return 0; }
・Q2-2. 貯金 (1)
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-2. 貯金 (1) https://algo-method.com/tasks/367 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ld=long double; ld f(ld n,ld x){ ld r=n+1; for(int i=0;i<5;i++){ r*=x; r+=1; } return r; } int main(void){ ld n,m; cin>>n>>m; ld left=0.0,right=100.0; while(right-left>0.00001){ ld mid=(left+right)/2; if(f(n,mid)<m){ left=mid; }else{ right=mid; } } cout<<left<<endl; return 0; }
・Q2-3. 最小の添字
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-3. 最小の添字 https://algo-method.com/tasks/370 提出コードの解答例 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),b(m); for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i<m;i++){ cin>>b[i]; } for(int i=0;i<m;i++){ int left=0,right=n-1; while(left!=right){ int mid=(left+right)/2; if(a[mid]>=b[i]){ right=mid; }else{ left=mid+1; } } cout<<left<<endl; } return 0; }
・Q2-4. 小さい数の個数
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-4. 小さい数の個数 https://algo-method.com/tasks/382 提出コードの解答例 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),b(m); for(int i=0;i<n;i++){ cin>>a[i]; } for(int i=0;i<m;i++){ cin>>b[i]; } sort(a.begin(),a.end()); for(int i=0;i<m;i++){ int left=0,right=n; while(left!=right){ int mid=(left+right)/2; if(a[mid]>b[i]){ right=mid; }else{ left=mid+1; } } cout<<left<<endl; } return 0; }
・Q2-5. 和が K 以上のペア
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-5. 和が K 以上のペア https://algo-method.com/tasks/381 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,k; cin>>n>>k; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } sort(a.begin(),a.end()); ll cnt=0; for(ll i=0;i<n;i++){ ll left=0,right=n; while(left!=right){ ll mid=(left+right)/2; if(a[mid]>=k-a[i]){ right=mid; }else{ left=mid+1; } } cnt+=(n-left); } cout<<cnt<<endl; return 0; }
・Q2-6. 重さは何番目?
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-6. 重さは何番目? https://algo-method.com/tasks/399 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<int> w(n),w2(n); for(int i=0;i<n;i++){ cin>>w[i]; w2[i]=w[i]; } sort(w.begin(),w.end()); for(int i=0;i<n;i++){ int left=0,right=n-1; while(left!=right){ int mid=(left+right)/2; if(w[mid]>=w2[i]){ right=mid; }else{ left=mid+1; } } cout<<left<<endl; } return 0; }
・Q2-7. 貯金 (2)
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-7. 貯金 (2) https://algo-method.com/tasks/366 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll ms(ll n){ return (n*(n+1))/2; } int main(void){ ll n; cin>>n; vector<ll> x(n); for(ll i=0;i<n;i++){ cin>>x[i]; } for(int i=0;i<n;i++){ ll left=0,right=2000000000; while(left!=right){ ll mid=(left+right)/2; if(ms(mid)>=x[i]){ right=mid; }else{ left=mid+1; } } cout<<left<<endl; } return 0; }
・Q2-8. ひもを切る
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-8. ひもを切る https://algo-method.com/tasks/369 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; ll f(ld n,vector<ld> l){ ll r=0; for(auto a : l){ r+=(int)a/n; } return r; } int main(void){ ll n,k; cin>>n>>k; vector<ld> l(n); for(ll i=0;i<n;i++){ cin>>l[i]; } ld left=0.0,right=200000.0; while(right-left>0.0000001){ ld mid=(left+right)/2; if(f(mid,l)>=k){ left=mid; }else{ right=mid; } } cout<<setprecision(20)<<left<<endl; return 0; }
・Q2-9. 九九の表 (1)
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-9. 九九の表 (1) https://algo-method.com/tasks/406 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n,k; cin>>n>>k; ll ans=0; for(ll i=0;i<n;i++){ ans+=min(n,k/(i+1)); } cout<<ans<<endl; return 0; }
・Q2-10. 九九の表 (2)
/* C++による「設計技法とデータ構造 (#毎日アルゴ式)」二分探索の解答例 Q2-10. 九九の表 (2) https://algo-method.com/tasks/407 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll f(ll n,ll k){ ll r=0; for(ll i=0;i<n;i++){ r+=min(n,k/(i+1)); } return r; } int main(void){ ll n,x; cin>>n>>x; ll left=0,right=n*n; while(left!=right){ ll mid=(left+right)/2; if(f(n,mid)>=x){ right=mid; }else{ left=mid+1; } } cout<<left<<endl; return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com