貪欲！

区間スケジューリング問題

N個の仕事がある。各仕事は、時間s_iに始まり、時間[t_i]に終わる。仕事に参加するなら、その仕事のはじめから終わりまで参加しなければならない。参加する仕事の時間帯が重なってはいけない。最大何個の仕事に参加できるか。

これも貪欲法で解ける。選べる仕事の中で、終了時間が最も早いものを選ぶことを繰り返す。

```cpp
#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;
}
```
例題ABC103-D
東西一列に並んだ 
N個の島とN−1 本の橋があります。i 番目の橋は、西から i 番目の島と西から i+1
番目の島を接続しています。

ある日、いくつかの島同士で争いが起こり、島の住人たちから M個の要望がありました。要望 i: 西から ai番目の島と西から bi番目の島の間で争いが起こったために、これらの島をいくつかの橋を渡って行き来できないようにしてほしい

あなたは橋をいくつか取り除くことでこれら M個の要望全てを叶えることにしました。

取り除く必要のある橋の本数の最小値を求めてください.
前とほぼ同じで橋の右端が小さい順にソートする。

```cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////

int main() {
	int N, M;
	cin >> N >> M;
	vector<pii>Q(M);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		Q[i].first = b;
		Q[i].second = a;
	}
	sort(Q.begin(), Q.end());
	int ans = 1;
	int t = Q[0].first;
	for (int i = 1; i <M ; ++i) {
		if (Q[i].second >= t) {
			ans++;
			t = Q[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}
```
Best cow line

```cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int N;
char s[2010];
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) {
			cout << s[a];
			a++;
		}
		else {
			cout << s[b];
			b--;
		}
	}
	return 0;
}
```
ABC 076-C dubious documents

E869120 は、宝物が入ってそうな箱を見つけました。
しかし、これには鍵がかかっており、鍵を開けるためには英小文字からなる文字列 S が必要です。
彼は文字列 S' を見つけ、これは文字列 S の 0 個以上 |S| 個以内の文字が ? に置き換わった文字列であることも分かりました。
ただし、文字列 A に対して、|A| を「文字列 A の長さ」とします。

そこで、E869120 はヒントとなる紙を見つけました。

条件1：文字列 S の中に連続する部分文字列として英小文字から成る文字列 T が含まれている。
条件2：S は、条件1を満たす文字列の中で辞書順最小の文字列である。
そのとき、鍵となる文字列 S を出力しなさい。
ただし、そのような文字列 S が存在しない場合は代わりに UNRESTORABLE と出力しなさい。

```cpp
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////

int main() {
	string S, T;
	cin >> S >> T;
	bool flag = false;
	bool ok = true;
	for (int i = S.size()-T.size(); i >= 0; --i) {
		ok = true;
		if (S[i] == '?' || S[i] == T[0]) {
			for (int j = i; j < i + T.size(); ++j) {
				if (S[j] == '?' || S[j] == T[j - i]) {
					continue;
				}
				else {
					ok = false;
					break;
				}
			}
			if (ok) {
				for (int j = i; j < i + T.size(); ++j) {
					S[j] = T[j - i];
				}
				flag = true;
				break;
			}
		}
	}
	if (flag) {
		for (int i = 0; i < S.size(); ++i) {
		    if (S[i] == '?') {
				S[i] = 'a';
			}
		}
		cout << S << endl;
	}
	else {
		cout << "UNRESTORABLE" << endl;
	}
	return 0;
}
```
条件２は'?'を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;
}
```

例題
ABC083 C

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////

int main() {
	ll X, Y;
	cin >> X >> Y;
	ll ans = 0;
	while (X <= Y) {
		ans++;
		X *= 2;
	}
	cout << ans << endl;
	return 0;
}
```

ARC006-C

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////

int main() {
	int N;
	int w[51];
	int count = 1;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> w[i];
	}
	vector<int>W;
	W.push_back(w[0]);
	for (int i = 1; i < N; ++i) {
		if (W[W.size() - 1] < w[i]) {
			W.push_back(w[i]);
		}
		else {
			for (int j = 0; j < W.size(); ++j) {
				if (w[i] <= W[j]) {
					W[j] = w[i];
					break;
				}
			}
		}
		sort(W.begin(), W.end());
	}
	cout << W.size() << endl;
	return 0;
}
```
ABC005-C

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////

int main() {
	int T, N, M;
	cin >> T >> N;
	vector<int>A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
	cin >> M;
	vector<int>B(M);
	for (int i = 0; i < M; ++i)cin >> B[i];
	bool can = true;
	for (int i = 0; i < M; ++i) {
		bool k = false;
		for (int j = 0; j < A.size(); ++j) {
			if (A[j] <= B[i] && B[i] <= A[j] + T) {
				A.erase(A.begin(),A.begin() + j+1);
				k = true;
				break;
			}
		}
		if (!k)can = false;
	}
	if (can)cout << "yes" << endl;
	else cout << "no" << endl;
	return 0;
}
```
ザ・C問題という感じ。300なら時間さえあれば９割方通せるようになってきたような
けどこのvector使ってゴリ押す感じだといろいろ改善しなきゃいけない時がきそういずれ

ABC 091-D

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////

int main() {
	int N;
	cin >> N;
	vector<pii>X(N);
	vector<pii>Y(N);
	for (int i = 0; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		X[i].first = b;
		X[i].second = a;
	}
	for (int i = 0; i < N; ++i) {
		int a, b;
		cin >> a >> b;
		Y[i].first = a;
		Y[i].second = b;
	}
	sort(X.begin(), X.end(), greater<pii>());
	sort(Y.begin(), Y.end());
	int count = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < Y.size(); ++j) {
			if (X[i].first < Y[j].second&&X[i].second < Y[j].first) {
				count++;
				Y.erase( Y.begin() + j );
				break;
			}
		}
	}
	cout << count << endl;
	return 0;
}
```