順列全探索, 二分探索

##前回の続き
[全探索：全列挙, 工夫して通り数を減らす全列挙, ビット全探索](https://qiita.com/RubyLrving/items/449048d8a8ce9ae14d7c)

##順列全探索
AOJで順列全探索のライブラリを勉強したので解き始めました。

###[Average Length](https://atcoder.jp/contests/abc145/tasks/abc145_c)

```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>> P(n);
    rep(i, n){
        cin >> P[i].first >> P[i].second;
    }
    sort(P.begin(), P.end());
    
    double sum = 0.0f;
    double c=0.0f;
    do{
        for(int i=1; i<n; i++){
            sum += sqrt(pow((P[i].first-P[i-1].first), 2) + pow((P[i].second-P[i-1].second), 2));
        }
        c++;
    }while(next_permutation(P.begin(), P.end()));
    
    cout << fixed << setprecision(10) << sum/c << endl;

    return 0;
}
```

###[C - Count Order](https://atcoder.jp/contests/abc150/tasks/abc150_c)

```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> P(n);
    vector<int> Q(n);
    rep(i, n){
        cin >> P[i];
    }
    rep(i, n){
        cin >> Q[i];
    }
    
    vector<int> A = vector<int>(P);
    sort(A.begin(), A.end());
    
    int first=0, last=0, c=0;
    do{
        if(A == P) first=c;
        if(A == Q) last=c;
        c++;
    }while(next_permutation(A.begin(), A.end()));
    
    cout << abs(last - first) << endl;
    return 0;
}
```

###[8クイーン問題](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/13/ALDS1_13_A)

順列全探索を使用します。
盤面のx軸をpに格納。
高さをiをして判定を行います。

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int k;
    cin >> k;

    vector<int> r(k);
    vector<int> c(k);
    rep(i, k){
        cin >> r[i] >> c[i];
    }

    vector<int> p(8);
    rep(i, 8) p[i] = i;

    do{
        bool is_queen = true;
        rep(j, k){
            if(p[r[j]] != c[j]){
                is_queen = false;
            }
        }
        if(!is_queen) continue;

        is_queen = false;
        for(int i=0; i<8; i++){
            int x1 = p[i]+1;
            int x2 = p[i]-1;
            for(int j=i+1; j<8; j++){
                if(p[j] == x1 ||  p[j] == x2){
                    is_queen = true;
                    break;
                }
                x1++;
                x2--;
            }
            if(is_queen) break;
        }
        if(!is_queen){
            break;
        }
    }while(next_permutation(p.begin(), p.end()));

    rep(i, 8){
        rep(j, 8){
            if(p[i] == j) cout << 'Q';
            else cout << '.';
        }
        cout << endl;
    }

    return 0;
}
```

##二分探索
AOJで二分探索のライブラリを勉強したので解き始めました。

###[Binary Search](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja)

```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>;

bool BinarySearch(int S[], int n, int key){
    
    int left=0;
    int right=n;
    
    while(right-left>0){
        int mid = (right+left)/2;
        if(S[mid]==key) return true;
        if(S[mid]>key) right = mid;
        else left = mid+1;
    }
    
    return false;
}

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

    int n;
    cin >> n;
    int S[100000]={0};
    rep(i, n){
        cin >> S[i];
    }
    int q;
    cin >> q;
    int T[50000]={0};
    rep(i, q){
        cin >> T[i];
    }
    
    int c=0;
    rep(i, q){
        if(BinarySearch(S, n, T[i])) c++;
    }
    
    cout << c << endl;

    return 0;
}
```

###[C - Snuke Festival](https://atcoder.jp/contests/abc077/tasks/arc084_a)

```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);
    vector<int> B(n);
    vector<int> C(n);
    
    rep(i, n) cin >> A[i];
    rep(i, n) cin >> B[i];
    rep(i, n) cin >> C[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    
    ll sum=0;
    rep(i, n){
        int key = B[i];
        vector<int>::iterator itr_a = lower_bound(A.begin(), A.end(), key);
        ll d_a = distance(A.begin(), itr_a);
        
        vector<int>::iterator itr_c = upper_bound(C.begin(), C.end(), key);
        ll d_c = distance(C.end(), itr_c);
        sum += d_a * abs(d_c);
    }
    
    cout << sum << endl;

    return 0;
}
```