#AtCoder 版!蟻本 (初級編)
今日からAtCoder 版!蟻本 (初級編)の記事を読み進めましょう!
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。
#2-2 猪突猛進! "貪欲法"
###貪欲法とは
1つのルールにしたがって、その場で最善の選択肢を繰り返す方法。
##問題
###例題 2-2-1 硬貨の問題
問題文は蟻本を参照してください。
#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を参照してください。
金額の多い硬貨から判定を行う。
#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 区間スケジューリング問題
問題文は蟻本を参照してください。
終了時間の早い区間から判定を行う。
#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)
#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)
問題文は蟻本を参照してください。
先頭と末尾を比較していきます。
#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を参照してください。
from math import floor
from decimal import Decimal
A = input()
if A=='a': print(-1)
else: print('a')
###例題 2-2-4 Saruman's Army
問題文は蟻本を参照してください。
アームの範囲を判定していきます。
#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を参照してください。
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
問題文は蟻本を参照してください。
一番小さな値から組み合わせていきます。
#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;
}