貪欲法を学ぶ

#AtCoder 版！蟻本 (初級編)
今日から[AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44)の記事を読み進めましょう！
[蟻本](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068)とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

#2-2 猪突猛進！ "貪欲法"
###貪欲法とは
1つのルールにしたがって、その場で最善の選択肢を繰り返す方法。

##問題
###例題 2-2-1　硬貨の問題
問題文は蟻本を参照してください。

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

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

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

const int V[6] = {1, 5, 10, 50, 100, 500};

int main(int argc, const char * argv[]) {
    int C[6];
    int A;
    
    rep(i, 6){
        cin >>  C[i];
    }
    cin >> A;
    
    int ans=0;
    for(int i=5; i>=0; i--){
        int t=min(A/V[i], C[i]);
        A-=t*V[i];
        ans+=t;
    }
    
    cout << ans << endl;
    
    return 0;
}
```

###[A - おつり](https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_a)
問題文はAtCoderを参照してください。

金額の多い硬貨から判定を行う。

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

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

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

const int V[6] = {500, 100, 50, 10, 5, 1};

int main(int argc, const char * argv[]) {
    
    int a;
    cin >> a;
    
    a=1000-a;
    
    int ans=0;
    rep(i, 6){
        int t=a/V[i];
        ans+=t;
        if(a%V[i]==0) break;
        else a=a%V[i];
    }
    cout << ans << endl;

    return 0;
}
```

###例題 2-2-2　区間スケジューリング問題
問題文は蟻本を参照してください。

終了時間の早い区間から判定を行う。

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

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

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

#define MAX_NUM 100000

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    vector<int> S(n, 0);
    vector<int> T(n, 0);
    
    rep(i, n){
        cin >> S[i] >> T[i];
    }
    
    P p[MAX_NUM];
    rep(i, n){
        p[i].first = T[i];
        p[i].second = S[i];
    }
    
    sort(p, p + n);
    
    int ans=0;
    int t=0;
    rep(i, n){
        if(t<p[i].second){
            t=p[i].first;
            ans++;
        }
    }
    
    cout << ans;

    return 0;
}
```
###[B - Robot Arms](https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b)
問題文はAtcoderを参照してください。

- robotのx+lを基準にソート
- 計算量はO(N)

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

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

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

#define MAX_NUM 100000

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    P p[MAX_NUM];
    rep(i, n){
        int x, l;
        cin >> x >> l;
        p[i].first = x+l;
        p[i].second = x-l;
    }
    sort(p, p+n);
    
    int res=0;
    int x=p[0].first;
    for(int i=1; i<n; i++){
        if(x>p[i].second){
            res++;
        }else{
            x=p[i].first;
        }
    }
    
    cout << n - res << endl;
    
    return 0;
}
```

###例題 2-2-3　Best Cow Line (POJ No.3617)
問題文は蟻本を参照してください。

先頭と末尾を比較していきます。

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

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

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

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    int a=0;
    int b=n-1;
    
    while(a<=b){
        bool left=false;
        for(int i=0; a+i<=b; i++){
            if(s[a+i]<s[b-i]){
                left=true;
                break;
            }else if(s[a+i]>s[b-i]){
                left=false;
                break;
            }
        }
        
        if(left) putchar(s[a++]);
        else putchar(s[b--]);
    }

    return 0;
}
```

###[B - 辞書式順序](https://atcoder.jp/contests/abc007/tasks/abc007_2)
問題文はAtcoderを参照してください。

```python:python
from math import floor
from decimal import Decimal
 
A = input()
 
if A=='a': print(-1)
else: print('a')
```

###例題 2-2-4　Saruman's Army
問題文は蟻本を参照してください。

アームの範囲を判定していきます。

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

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

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

#define MAX_X 1000

int main(int argc, const char * argv[]) {
    int n, r;
    cin >> n >> r;
    
    int x[MAX_X];
    rep(i, n){
        cin >> x[i];
    }
    sort(x, x+n);

    int i=0;
    int ans=0;
    while(i<n){
        int s = x[i++];
        while(i<n&&x[i]<=s+r) i++;
        int p = x[i-1];
        while(i<n&&x[i]<=p+r) i++;
        ans++;
    }
    
    cout << ans << endl;
    
    return 0;
}
```

###[C - Multiple Gift](https://atcoder.jp/contests/abc083/tasks/arc088_a)
問題文はAtcoderを参照してください。

```python:python
from math import floor
from decimal import Decimal

A, B = list(map(int, input().split()))

num = A
c = 0
while num <= B:
    num *= 2
    c+=1

print(c)
```

###例題 2-2-5　Fence Repair
問題文は蟻本を参照してください。

一番小さな値から組み合わせていきます。

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

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

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

#define MAX_L 50000

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    
    int L[MAX_L];
    rep(i, n){
        cin >> L[i];
    }
    
    ll ans=0;
    while(n>1){
        int mii1=0;
        int mii2=1;
        if(L[mii1]>L[mii2]) swap(mii1, mii2);
        
        for(int i=2; i<n; i++){
            if(L[i]<L[mii1]){
                mii2=mii1;
                mii1=i;
            }else if(L[i]<L[mii2]){
                mii2=i;
            }
        }
        
        int t=L[mii1]+L[mii2];
        ans+=t;
        
        if(mii1==n-1) swap(mii1, mii2);
        L[mii1]=t;
        L[mii2]=L[n-1];
        n--;
    }
    
    cout << ans << endl;
    
    return 0;
}
```