挿入ソート, ユークリッドの互除法, 素数, 

AtCoderのパフォーマンスが上がらない。
問題に左右されながらパフォーマンスMAX７５０〜MIN５０の間を過ごしています。
コンテストに出てるだけでは一生パフォーマンスは上がらないと分かったので勉強します。

##[ALDS1_1_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_1_A)
###挿入ソート
先頭の要素をソート済みとする。
未ソートの部分がなくなるまで、以下の処理を繰り返す：

- 1.未ソート部分の先頭の要素を取り出しに記録する。
- 2.取り出した要素とソート済みの部分において比較し、より大きい要素を後方へ１つずつ移動する。
- 3.取り出した要素より大きい要素がない最後に空いた位置に「取り出した要素」を挿入する。 

計算量は、最大O（N＾２）

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

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

using namespace std;

int main(int argc, const char * argv[]) {
    int N;
    int A[1000] = {0};
    
    cin >> N;
    rep(i, N){
        cin >> A[i];
    }
    
    for(int k=0; k<N; k++){
        if(k<N-1) cout << A[k] << ' ';
        else cout << A[k] << endl;
    }
    
    for(int i=1; i<N; i++){
        int v = A[i];
        int j = i-1;
        while(j>=0 && A[j]>v){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        for(int k=0; k<N; k++){
            if(k<N-1) cout << A[k] << ' ';
            else cout << A[k] << endl;
        }
    }
    return 0;
}
```

##[ALDS1_1_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_B)
###ユークリッドの互除法
整数 a, b, q, rについてをa,bで割った商がq、余りがr、
a=bq+r
が成り立つとき、
「a,bの最大公約数」と「b,rの最大公約数」は一致します。

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

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

using namespace std;

int gcd(int x, int y){
    if(x < y) swap(x, y);
    while(y>0){
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main(int argc, const char * argv[]) {
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y) << endl;
    return 0;
}
```

##[ALDS1_1_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_C)
###素数
素数とは「1より大きい整数で、1と自分自身でしか割り切れない数」。
素数判定では、「合成数xはp≤√xを満たす素因子pをもつ」という性質を利用することができます。
素数ではない数を合成数と言います。

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

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

using namespace std;

bool isPrime(int x){
    if(x==2) return true;
    
    if(x<2 || x%2==0) return false;
    
    for(int i=3; i*i<=x; i+=2){
        if(x%i==0) return false;
    }
    return true;
}

int main(int argc, const char * argv[]) {
    int n, ans=0;
    cin >> n;
    
    rep(i, n){
        int x;
        cin >> x;
        if(isPrime(x)) ans++;
    }
    
    cout << ans << endl;
    return 0;
}
```

##[ALDS1_1_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D)
###最大利益
値を保持してO(N^2)から計算量を減らす問題。

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

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

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
    }
    
    int Min, d = NUM_MIN;
    rep(i, n){
        cin >> A[i];
        if(i==0) Min = A[i];
        else{
            d = max(d, A[i] - Min);
            Min = min(Min, A[i]);
        }
    }
    
    cout << d << endl;
    
    return 0;
}
```