# 初級編
[蟻本（全体ページ）](/itAw-_j4TMi910lu1pznDA)

[Qiita記事](https://qiita.com/drken/items/e77685614f3c6bf86f44)
**例題 1-1-1　(ハードルの上がった) くじびき ＜難問！！！！！＞**
未回答
**例題 1-6-1　三角形**
割愛
**例題 1-6-2　Ants (POJ No.1852)**
難しい。ありにゼッケンを着せるとわかるという発想が賢い。結局n秒たった時にすれ違った蟻の数を数えれば良い
**例題 2-1-1　部分和問題**
<details><summary>bit全探索を行う。bit全探索はほとんど雛形に当て嵌めるだけ</summary><div>

for (int bit = 0; bit < (1<<n); bit++) {
    for (int i = 0; i < n; i++) {
        if (bit & (1<<i)) //bitがオンの時の動作
        else //bitがオフの時の動作
    }
    //bitごとの動作
}

</div></details>

**例題 2-1-2　Lake Counting (POJ No.2386)**
<dl><dt>再帰関数の注意点</dt>
<dd>添字を逆方向にもずらすときは行ったり来たりして無限ループにならないように訪れたかをmemoする</dd>
<dd>memoの更新を忘れない（trueにする)</dd>
<dd>配列外参照しないように、添字チェックは最初に行う</dd>
</dl>

**例題 2-1-3　迷路の最短路**

<dl><dt>bfs注意点</dt>
<dd>costを持って遷移させるときはきちんと更新する</dd>
<dd>受け取った入力の添字を０からに合わせるときはデクリメントするとわかりやすい</dd>
<dd>

**bfsは広げていくので、すでに探索したところを２重３重に調べてしまう。そこで、２次元配列なりを用意してmemoし、比較して枝切りする<-これ本質ぽい**
</dd>
<dd>dx[4]={0,0,1,-1}のようなものを用意しておいてループを回すと便利</dd>
</dl>

**例題 2-1-4　特殊な状態の列挙**
next_permutationを使う。計算量O(n!)
要素nの順列を辞書順で全て取得する、**sortされた**配列を用意しておいて使うと、配列の要素を並び替えてくれる。
<details><summary>サンプルコード</summary><div>

//sortしておく
sort(vec.begin(), vec.end());
do {
    //順列に対する操作
} while(next_permutation(vec.begin(), vec.end()));

</div></details>

**例題 2-2-2　区間スケジューリング問題**
結論を言うと、区間の終点が小さい順に取っていく貪欲。考え方の基本として持っておくべき。

**なお[プレゼント](https://atcoder.jp/contests/abc038/tasks/abc038_d)についてはLISなので貪欲から発想を飛ばすのは困難な気がする**
解説を読むとセグ木やらなんやら書いてあるので以下を参考にすると良い

* [LISについて](https://tutuz.hateblo.jp/entry/2018/06/18/214827)
* [lowerbound](https://qiita.com/ganyariya/items/33f1326154b85db465c3)
* wiの降順に並べると、先にdpの値が計算された箱を含むような入
れ方はないため、hが同じ箱で入れ子になることがなく、正しい答
えが得られる(プレゼントの解説から引用)
* [ラムダ式](https://o-treetree.hatenablog.com/entry/2020/05/23/004152)

<details><summary>ACコード</summary><div>

const int INF = 2147483647;
int main() {
    int n; cin >> n;
	vector<pair<int, int>> hw(n, {0,0});
	vector<int> lis(n, INF);
	for (int i = 0; i < n; i++) {
		cin >> hw[i].first >> hw[i].second;
	}
	sort(hw.begin(), hw.end(), [](auto l, auto r) {
				if (l.first != r.first) return l.first < r.first;
				else return l.second > r.second;
			});
	for (int i = 0; i < n; i++) {
		int index = lower_bound(lis.begin(), lis.end(), hw[i].second) - lis.begin();
		lis[index] = hw[i].second;
	}
	cout << lower_bound(lis.begin(), lis.end(), INF) - lis.begin() << endl;
 
	return 0;
}

</div>
</details>