LoginSignup
3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@RubyLrving(ruby lrving)

貪欲法を学ぶ

Last updated at Posted at 2020-06-04

#AtCoder 版！蟻本 (初級編)
今日からAtCoder 版！蟻本 (初級編)の記事を読み進めましょう！
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

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

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

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 - おつり
問題文はAtCoderを参照してください。

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

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++
#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
問題文はAtcoderを参照してください。

  • robotのx+lを基準にソート
  • 計算量はO(N)
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++
#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 - 辞書式順序
問題文はAtcoderを参照してください。

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++
#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
問題文はAtcoderを参照してください。

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++
#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;
}
3
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?