AOJ プログラミング応用 トピック#4, トピック#5, トピック#6

#トピック#4
##[ITP2_4_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/4/ITP2_4_A)
###Reverse

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, q;
    cin >> n;
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }

    cin >> q;
    rep(i, q){
        int b, e;
        cin >> b >> e;
        reverse(A.begin()+b, A.begin()+e);
    }
    
    rep(i, n){
        if(i<n-1) cout << A[i] << ' ';
        else cout << A[i] << endl;
    }

    return 0;
}
```

##[ITP2_4_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/4/ITP2_4_B)
###Rotate(ローテート)
要素を回転させます。
Rotate(first, middle, last)
0 以上 last - first 未満の整数 i について、first + i の要素を first + (i + (last - middle)) % (last - first) の位置へ移動させる。

何に使うか全く分からない！

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, q;
    cin >> n;
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }

    cin >> q;
    rep(i, q){
        int b, m, e;
        cin >> b >> m >> e;
        rotate(A.begin()+b, A.begin()+m, A.begin()+e);
    }
    
    rep(i, n){
        if(i<n-1) cout << A[i] << ' ';
        else cout << A[i] << endl;
    }

    return 0;
}
```

##[ITP2_4_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/4/ITP2_4_C)
###swap_ranges
swap_ranges(first1, last1, first2)
0 以上 last1 - first1 以下のそれぞれの n について swap(*(first1 + n), *(first2 + n)) を行う
何に使うか全く分からない！

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, q;
    cin >> n;
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }

    cin >> q;
    rep(i, q){
        int b, e, t;
        cin >> b >> e >> t;
        swap_ranges(A.begin()+b, A.begin()+e, A.begin()+t);
    }
    
    rep(i, n){
        if(i<n-1) cout << A[i] << ' ';
        else cout << A[i] << endl;
    }

    return 0;
}
```

##[ITP2_4_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/4/ITP2_4_D)
###Unique
iterator = Unique(first, last)
erase(iterator, last)
重複した値を削除。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }

    vector<int>::iterator itr = unique(A.begin(), A.end());
    A.erase(itr, A.end());
    
    rep(i, A.size()){
        if(i<A.size()-1) cout << A[i] << ' ';
        else cout << A[i] << endl;
    }

    return 0;
}
```

#トピック#5
##[ITP2_5_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/5/ITP2_5_A)
###Sorting Pairs

pair<int,int>をソート関数する。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;
    vector<pair<int, int>> point(n);
    
    rep(i, n){
        cin >> point[i].first >> point[i].second;
    }
    
    sort(point.begin(), point.end());
    
    rep(i, n){
        cout << point[i].first << ' ' << point[i].second << endl;
    }

    return 0;
}
```

##[ITP2_5_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/5/ITP2_5_B)
###Sorting Tuples

vectorとtupleの組み合わせ

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

typedef tuple<int, int, char, ll, string> mytuple;

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;
    vector<mytuple> vec(n);
    
    rep(i, n){
        int u, w;
        char t;
        ll d;
        string s;
        cin >> u >> w >> t >> d >> s;
        
        vec[i] = make_tuple(u, w, t, d, s);
    }
    
    sort(vec.begin(), vec.end());
    
    rep(i, n){
        cout << get<0>(vec[i]) << ' ' << get<1>(vec[i]) << ' ' << get<2>(vec[i]) << ' ' << get<3>(vec[i]) << ' ' << get<4>(vec[i]) << endl;
    }

    return 0;
}
```

##[ITP2_5_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/5/ITP2_5_C)
###Permutation

順列で使用するライブラリです。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;
    vector<int> vec(n);
    
    rep(i, n){
        cin >> vec[i];
    }
    
    vector<int> cp = vector<int>(vec);
    
    if( prev_permutation(cp.begin(), cp.end()) ){
        rep(i, n){
            if(i<n-1) cout << cp[i] << ' ';
            else cout << cp[i] << endl;
        }
    }
    
    rep(i, n){
        if(i<n-1) cout << vec[i] << ' ';
        else cout << vec[i] << endl;
    }
    
    if(next_permutation(vec.begin(), vec.end()) ){
        rep(i, n){
            if(i<n-1) cout << vec[i] << ' ';
            else cout << vec[i] << endl;
        }
    }

    return 0;
}
```

##[ITP2_5_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/5/ITP2_5_D)
###Permutation Enumeration

順列全探索の基本です！

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;
    vector<int> vec(n);
    
    rep(i, n){
        vec[i] = i+1;
    }
    
    do{
        rep(i, n){
            if(i<n-1) cout << vec[i] << ' ';
            else cout << vec[i] << endl;
        }
    }while(next_permutation(vec.begin(), vec.end()));

    return 0;
}
```

#トピック#6
##[ITP2_6_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/6/ITP2_6_A)
###Binary Search

二分探索！

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, q;
    cin >> n;
    vector<int> vec(n);
    rep(i, n){
        cin >> vec[i];
    }
    
    cin >> q;
    rep(i, q){
        int k;
        cin >> k;
        if(binary_search(vec.begin(), vec.end(), k)) cout << 1 << endl;
        else cout << 0 << endl;
    }

    return 0;
}
```

##[ITP2_6_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/6/ITP2_6_B)
###Includes

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, m;
    cin >> n;
    vector<int> a(n);
    rep(i, n){
        cin >> a[i];
    }
    cin >> m;
    vector<int> b(m);
    rep(i, m){
        cin >> b[i];
    }
    
    if(includes(a.begin(), a.end(), b.begin(), b.end())) cout << 1 << endl;
    else cout << 0 << endl;
    
    return 0;
}
```

##[ITP2_6_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/6/ITP2_6_C)
###Lower Bound

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, q;
    cin >> n;
    vector<int> vec(n);
    rep(i, n){
        cin >> vec[i];
    }
    cin >> q;
    rep(i, q){
        int k;
        cin >> k;
        vector<int>::iterator itr  = lower_bound(vec.begin(), vec.end(), k);
        ll d = distance(vec.begin(), itr);
        cout << d << endl;
    }
    
    return 0;
}
```

##[ITP2_6_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/6/ITP2_6_D)
###Equal Range

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n, q;
    cin >> n;
    vector<int> vec(n);
    rep(i, n){
        cin >> vec[i];
    }
    cin >> q;
    rep(i, q){
        int k;
        cin >> k;
        vector<int>::iterator itr_lower  = lower_bound(vec.begin(), vec.end(), k);
        ll ld = distance(vec.begin(), itr_lower);
        vector<int>::iterator itr_upper  = upper_bound(vec.begin(), vec.end(), k);
        ll ud = distance(vec.begin(), itr_upper);
        cout << ld << ' ' << ud << endl;
    }
    
    return 0;
}
```