寝癖頭の解法

学習中の覚え書きを投稿、更新していきます。

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

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

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

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

Q2-1. 方程式を解く

algo-method.com

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

algo-method.com

/*
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. 最小の添字

algo-method.com

/*
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. 小さい数の個数

algo-method.com

/*
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 以上のペア

algo-method.com

/*
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. 重さは何番目?

algo-method.com

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

algo-method.com

/*
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. ひもを切る

algo-method.com

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

algo-method.com

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

algo-method.com

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