貪欲法

貪欲にその場での最善を選択することを繰り返すというアルゴリズム設計技法
硬貨の問題
１円玉、５円玉、１０円玉、５０円玉、１００円玉、５００円玉がそれぞれC1,C5,C10,C50,C100,C500枚ずつあります。できるだけ少ない枚数の硬貨でＡ円を支払いたいと考えています。何枚の硬貨を出す必要があるでしょうか？なお、そのような支払い方は少なくとも１つは存在するとします。
大きな額の硬貨をできるだけ多く使う直感の通りに。

# include<iostream>
# include<algorithm>
using namespace std;

const int V[6] = { 1,5,10,50,100,500 };
int C[6];
int A;
int main() {
	cin >> A;
	for (int i = 0; i < 6; ++i)
		cin >> C[i];
	int ans = 0;
	for (int i = 5; i >= 0; i--) {
		int t = min(A / V[i], C[i]);
		A -= t * V[i];
	1	ans += t;
	}
	cout << ans;
}

区間スケジューリング問題
Ｎ個の仕事がある。各仕事は時間Ｓｉに始まり、時間Ｔｉに終わる。あなたは各仕事について、参加するか参加しないかを選ばなければなりません。仕事に参加するならばその仕事の始めから終わりまで参加しなければなりません。また、参加する仕事の時間帯が重なってはいけません。
できるだけ多くの仕事に参加したいです。何個の仕事に参加することができるでしょうか。
1<=N<100000
1<=Si<Ti<=10**9
これも貪欲法で解ける。選べる仕事の中で、終了時間が最も早いものを選ぶことを繰り返す。

# include<iostream>
# include<algorithm>
using namespace std;

const int MAX_N = 100000;
int N, S[MAX_N], T[MAX_N];
pair<int, int>itv[MAX_N];
int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> S[i] >> T[i];
	}
	//pairは辞書順で比較される
	//終了時間の早い順にしたいため、Tをfirstに、Sをsecondに入れる。
	for (int i = 0; i < N; ++i) {
		itv[i].first = T[i];
		itv[i].second = S[i];
	}
	sort(itv, itv + N);
	//tは最後に選んだ仕事の終了時間
	int ans = 0, t = 0;
	for (int i = 0; i < N; i++) {
		if (t < itv[i].second) {
			ans++;
			t = itv[i].first;
		}
	}
	cout << ans;
	return 0;
}

Best Cow Line
Ｎ文字の文字列Ｓが与えられ、Ｎ文字の文字列Ｔを作ります。はじめはＴは長さ０の文字列で、次にいずれかの操作が行えます。
・Ｓの先頭を１文字削除し、Ｔの末尾に追加する。
・Ｓの末尾を１文字削除し、Ｔの末尾に追加する。
辞書順比較でできるだけ小さくなるようにＴを作ってください。

これも貪欲法でとける。Ｓの先頭と末尾の、より小さいほうの文字をＴの末尾に付け加えることを繰り返す。が一見よさそうに思えるが、Ｓの先頭と末尾が同じの文字の場合が定義されていません。そのような場合、その文字の後にできるだけ良い文字を早く使いたいので次の文字を比較する必要がある。次の文字も一致しているかもしれない。よって、次のようにします。
・ＳとＳを反転させた文字列Ｓ‘を辞書順比較する。
・Ｓが小さいのであれば、Ｓの先頭を１文字削除し、Ｔの末尾に追加する。
・Ｓが大きいのであれば、Ｓの末尾を１文字削除し、Ｔの末尾に追加する。
（同じならばどちらでもよい）

# include<iostream>
using namespace std;

const int MAX_N = 2010;
int N;
char S[MAX_N + 1];
int main() {
	cin >> N;
	cin >> S;
	int a = 0, 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--]);
	}
	putchar('\n');
}

賢いな。putchar(a)はaを出力する。今知った。

Saruman`s Army
N個の点が直線状にあります。点iの位置はXiです。N個のうちのいくつかの点を選び、それらの点に印をつけます。N個のすべての点について、距離がR以内の場所に印を付けられた点がなければなりません。（自分に印が付いていれば、距離が０のところにあると考えます）。条件を満たすようにしながら、できるだけ印を付ける点を少なくしたいです。何個の点に印を付ける必要があるでしょうか。
・1<=N<=1000
・0<=R<=1000
・0<=Xi<=1000

# include<iostream>
# include<algorithm>
using namespace std;
int N, R;
const int MAX_N = 1010;
int X[MAX_N];
int main() {
	cin >> N >> R;
	for (int i = 0; i < N; i++)
		cin >> X[i];
	sort(X, X + N);
	int i = 0, ans = 0;
	while (i < N) {
		//sはカバーされていない一番左の点の位置
		int s = X[i++];
		//sから距離Rを超える点まで進む
		while (i < N && X[i] <= s + R)i++;
		//pは新しく印を付ける点の位置
		int p = X[i - 1];
		//pから距離Rを超える点まで進む
		while (i < N && X[i] <= p + R)i++;
		ans++;
	}
	cout << ans;
}