AOJ 総当たり, マージソート, コッホ曲線, 反転数

##[ALDS1_5_A](https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_5_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, q;
    cin >> n;
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }

    cin >> q;
    vector<int> M(q);
    vector<bool> res(q);
    rep(i, q){
        cin >> M[i];
        res[i]=false;
    }

    for(int bit=0; bit<(1<<n); bit++){
        int sum=0;
        for(int a=0; a<n; a++){
            if(bit>>a&1){
                sum+=A[a];
            }
        }
        for(int m=0; m<q; m++){
            if(M[m] == sum) res[m] = true;
        }
    }
    
    for(int m=0; m<q; m++){
        if(res[m]) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}
```

再起処理で回答。

```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 dfs(int n, vector<int> A, int m, int index){
    if(m==0) return true;
    else if(m<0) return false;
    
    for(int i=index; i<n; i++){
        if(dfs(n, A, m-A[i], i+1)) return true;
    }
    
    return false;
}

int main(int argc, const char * argv[]) {
    
    int n, q;
    cin >> n;
    vector<int> A(n);
    rep(i, n) cin >> A[i];
    
    cin >> q;
    vector<int> M(q);
    rep(i, q) cin >> M[i];
    
    rep(i, q){
        if(dfs(n, A, M[i], 0)) cout << "yes" << endl;
        else cout << "no" << endl;
    }

    return 0;
}
```

##[ALDS1_5_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_B)
###マージソート

```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>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#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 cnt;
int L[500000];
int R[500000];

void merge(int A[], int left, int mid, int right){
    int INFTY = 1e9+1;
    int n1 = mid - left;
    int n2 = right - mid;
    rep(i, n1) L[i] = A[left + i];
    rep(i, n2) R[i] = A[mid + i];
      
    L[n1] = INFTY;
    R[n2] = INFTY;
    int i = 0;
    int j = 0;
    for(int k = left; k<right; k++){
        cnt++;
        if(L[i] <= R[j]){
            A[k] = L[i];
            i = i + 1;
        }else{
            A[k] = R[j];
            j = j + 1;
        }
    }
}

void mergeSort(int A[], int left, int right){
    if(left+1 < right){
        int mid = (left + right)/2;
        mergeSort(A, left, mid);
        mergeSort(A, mid, right);
        merge(A, left, mid, right);
    }
}

int main() {
    int n;
    cin >> n;
    
    int A[500000];
    rep(i, n) cin >> A[i];
     
    mergeSort(A, 0, n);
    rep(i, n-1) cout << A[i] << ' ';
    cout << A[n-1] << endl;
    cout << cnt << endl;
    
    return 0;
}
```

##[ALDS1_5_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_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>
#include<set>
#include<bitset>

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

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

vector<pair<double, double>> pos;

void kock(int n, pair<double, double> p1, pair<double, double> p2){
    if (n == 0) return;

    pair<double, double> s((2*p1.first+p2.first)/3.0f, (2*p1.second+p2.second)/3.0f);
    pair<double, double> t((p1.first+2*p2.first)/3.0f, (p1.second+2*p2.second)/3.0f);
    pair<double, double> u((t.first-s.first)*cos(60.0f*pai/180.0f)-(t.second-s.second)*sin(60.0f*pai/180.0f)+s.first, (t.first-s.first)*sin(60.0f*pai/180.0f)+(t.second-s.second)*cos(60.0f*pai/180.0f)+s.second);
    

    kock(n-1, p1, s);
    pos.push_back(s);
    kock(n-1, s, u);
    pos.push_back(u);
    kock(n-1, u, t);
    pos.push_back(t);
    kock(n-1, t, p2);
}

int main() {
    int n;
    cin >> n;
    
    pos.push_back(pair<double, double>(0, 0));
    kock(n, pair<double, double>(0, 0), pair<double, double>(100, 0));
    pos.push_back(pair<double, double>(100, 0));
    
    rep(i, pos.size()){
        cout << fixed_setprecision(10) << pos[i].first << ' ' << pos[i].second << endl;
    }
    
    return 0;
}
```

##[ALDS1_5_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_D)
###反転数
木構造の積み木の数から数える方式。

```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>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#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 L[500000];
int R[500000];

ll merge(int A[], int left, int mid, int right){
    int INFTY = 1e9+1;
    int n1 = mid - left;
    int n2 = right - mid;
    rep(i, n1) L[i] = A[left + i];
    rep(i, n2) R[i] = A[mid + i];
      
    L[n1] = INFTY;
    R[n2] = INFTY;
    int i = 0;
    int j = 0;
    ll cnt=0;
    for(int k = left; k<right; k++){
        if(L[i] <= R[j]){
            A[k] = L[i];
            i = i + 1;
        }else{
            A[k] = R[j];
            j = j + 1;
            cnt += n1 - i;
        }
    }
    return cnt;
}

ll mergeSort(int A[], int left, int right){
    if(left+1 < right){
        int mid = (left + right)/2;
        ll v1 = mergeSort(A, left, mid);
        ll v2 = mergeSort(A, mid, right);
        ll v3 = merge(A, left, mid, right);
        return v1+v2+v3;
    }else{
        return 0;
    }
}

int main() {
    int n;
    cin >> n;
    
    int A[500000];
    rep(i, n) cin >> A[i];
     
    ll cnt = mergeSort(A, 0, n);
    cout << cnt << endl;
    
    return 0;
}
```