Aizu Online Judge in C++ #ITP2_11_A ~ ITP2_11_D

Aizu Online Judge（AOJ）の過去問から、その提出コードの解答例です。

Aizu Online Judge in C++ #ITP2_11_A ~ ITP2_11_D

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

・問題 "Enumeration of Subsets I"
https://onlinejudge.u-aizu.ac.jp/problems/ITP2_11_A

/*
Aizu Online Judge in C++ #ITP2_11_A : Enumeration of Subsets I
https://onlinejudge.u-aizu.ac.jp/problems/ITP2_11_A
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    for(int i=0;i<1<<n;i++){
        cout<<i<<":";
        for(int j=0;j<n;j++){
            if(i>>j&1){
                cout<<" "<<j;
            }
        }
        cout<<endl;
    }
    return 0;
}

・問題 "Enumeration of Subsets II"
https://onlinejudge.u-aizu.ac.jp/problems/ITP2_11_B

/*
Aizu Online Judge in C++ #ITP2_11_B : Enumeration of Subsets II
https://onlinejudge.u-aizu.ac.jp/problems/ITP2_11_B
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int k,m=0;
    cin>>k;
    while(k--){
        int b;
        cin>>b;
        m|=1<<b;
    }
    for(int i=m;i<1<<n;i=i+1|m){
        cout<<i<<":";
        for(int j=0;j<n;j++){
            if(i>>j&1){
                cout<<" "<<j;
            }
        }
        cout<<endl;
    }
    return 0;
}

・問題 "Enumeration of Subsets III"
https://onlinejudge.u-aizu.ac.jp/problems/ITP2_11_C

/*
Aizu Online Judge in C++ #ITP2_11_C : Enumeration of Subsets III
https://onlinejudge.u-aizu.ac.jp/problems/ITP2_11_C
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int k,m=0;
    cin>>k;
    while(k--){
        int b;
        cin>>b;
        m|=1<<b;
    }
    for(int i=0;i<1<<n;i++){
        if(i&~m){
            continue;
        }
        cout<<i<<":";
        for(int j=0;j<n;j++){
            if(i>>j&1){
                cout<<" "<<j;
            }
        }
        cout<<endl;
    }
    return 0;
}

・問題 "Enumeration of Combinations"
https://onlinejudge.u-aizu.ac.jp/problems/ITP2_11_D

/*
Aizu Online Judge in C++ #ITP2_11_D : Enumeration of Combinations
https://onlinejudge.u-aizu.ac.jp/problems/ITP2_11_D
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<1<<n;i++){
        if(__builtin_popcount(i)-k){
            continue;
        }
        cout<<i<<":";
        for(int j=0;j<n;j++){
            if(i>>j&1){
                cout<<" "<<j;
            }
        }
        cout<<endl;
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/

Aizu Online Judge in C++ #ALDS1_4_D : Binary Search

Aizu Online Judge（AOJ）の過去問から、その提出コードの解答例です。

・問題 "Allocation"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_D

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

Aizu Online Judge in C++ #ALDS1_4_D : Allocation

/*
Aizu Online Judge in C++ #ALDS1_4_D : Allocation
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_D
 提出コードの解答例
 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 w[n];
    ll sum=0;
    for(ll i=0;i<n;i++){
        cin>>w[i];
        sum+=w[i];
    }
    ll l=0,r=sum;
    while(l+1<r){
        ll mid=(l+r)/2;
        ll t=0,num=0;
        bool tf=false;
        for(ll i=0;i<n;i++){
            tf|=w[i]>mid;
            if(num+w[i]>mid){
                num=w[i];
                t++;
            }else{
                num+=w[i];
            }
        }
        if(num){
            t++;
        }
        if(tf==false && t<=k){
            r=mid;
        }else{
            l=mid;
        }
    }
    cout<<r<<endl;
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/

Aizu Online Judge in C++ #ALDS1_4_C : Dictionary

Aizu Online Judge（AOJ）の過去問から、その提出コードの解答例です。

・問題 "Dictionary"
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_C

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

Aizu Online Judge in C++ #ALDS1_4_C : Dictionary

/*
Aizu Online Judge in C++ #ALDS1_4_C : Dictionary
https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_C
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    set<string> s;
    int n;
    cin>>n;
    while(n--){
        string str,c;
        cin>>str>>c;
        if(str=="insert"){
            s.insert(c);
        }else{
            cout<<((s.find(c)!=s.end()) ? "yes" : "no")<<endl;
        }
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/