貪欲法を学ぶ

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