# 競プロ班 講義第五回
今日学ぶ機能のいくつかは使うのに特定のファイルのインクルードが必要です。
手元でプログラムを実行する場合、以下のテンプレートを使ってください。
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;
int main() {
}
```
## 計算量
[W - 2.06.計算量](https://atcoder.jp/contests/apg4b/tasks/APG4b_w)
#### ポイント
- プログラムの実行時間には制限がある。1回あたりの実行が2秒以内に終了するようなプログラムを作る必要がある。実行に2秒以上かかるようなプログラムを提出すると、TLE（Time Limit Exceeded）となってしまい、不正解扱いになってしまう。
- 計算量が評価できたら、あとはその計算量に最大のNを代入して$10^8$以下になるならば十分高速で、実行時間は2秒以内に収まる
**例**)
- 計算量がO($N^2$)だとわかって、制約でN <= $10^3$が与えられている場合、N = $10^3$を代入すると$10^6$となり、十分高速にプログラムは実行される
- 計算量がO(N + M)だとわかって、制約でN <= $10^5$, M <= $10^5$が与えられている場合、N = $10^5$, M = $10^5$を代入すると2*$10^5$となり、十分高速
- 計算量がO($N^2$)だとわかって、制約でN <= $10^5$が与えられている場合、N = $10^5$を代入すると$10^{10}$となり、これでは実行に2秒以上かかってしまい、TLEとなる
- プログラムを組む時はTLEにならないように、効率の良い（計算量の良い）プログラムを組むようにしよう
---
#### 計算量を意識する必要性（講義では飛ばします）
次の問題を題材にして、計算量を意識して問題を解く必要性について考えてみましょう。（ちょっと難しい話です。完全に理解する必要はなく、計算量を意識することが大事であることを感じてもらえればそれで十分です）
[C - Max Even](https://atcoder.jp/contests/abc272/tasks/abc272_c)
自然に思いつく解法としては、「Aの異なる2要素の和を全て列挙し、そのうちの最大値を答える」というものが挙げられる。
この解法を実装すると次のようになる
```cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using ll = long long;
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
int ans = -1;
// 異なる2要素をの選び方を全て試す
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
//異なる2要素でない
if (i == j) continue;
//異なる2要素の和が偶数
if ((A[i] + A[j]) % 2 == 0) {
ans = max(ans, A[i] + A[j]);
}
}
}
cout << ans << endl;
}
```
プログラム内で2重ループを回しているので計算量はO($N^2$)となる。
制約はN <= $2*10^5$であったから、このプログラムを提出するとTLEとなる
--> より計算量の良い解法を考える必要がある
実はより良い計算量の解法が存在する！
和が偶数になるのは、足される2要素がどちらも偶数である場合と足される2要素がどちらも奇数である場合の2通りであることに着目すると、答えは「Aの偶数の要素の内の最大の2要素」と「Aの奇数の要素の内の最大の2要素」の大きい方になる。
「Aの偶数の要素の内の最大の2要素」や「Aの奇数の要素の内の最大の2要素」はいずれもO(N)で求められる。（求め方は省略。よかったら考えてみてください）
よって、この解法の計算量はO(N)となり、N <= $2*10^5$であるので十分高速であり、ACが得られる。
<br>
C問題以降はこんな感じで工夫して計算量を落とすことが必要になったりする。工夫して計算量を落とすのは競プロの醍醐味の1つだと言われている。
ちなみにA問題、B問題では計算量を気にする必要のある問題はほぼ出題されないので、計算量への理解が現状浅かったとしても問題はないと思うのでそこまで心配する必要はありません。まずはA問題、B問題を安定して解けるようになることを目指しましょう
## pair/tuple
[Z - 3.02.pair／tupleとauto](https://atcoder.jp/contests/apg4b/tasks/APG4b_z)
#### 補足
- autoは比較的新しい機能なので手元でプログラムを実行している場合、コンパイラのバージョンによってはautoを使ったプログラムのコンパイルができないかもしれません
windowsの人は問題ないはず。macの人で```g++ --version```を実行したときに```Apple clang version ~```のように出る人は```g++ std=c++14 〇〇.cpp```のようにコンパイルするといいです
-
```cpp
using ll = long long
```
以前ちらっと触れたこれも型エイリアスを利用して、long long型に別名をつけている
## STLのコンテナ
内容が非常に多いです。一回で全て頭に入れるのは無理なので使いながら徐々に覚えていきましょう
[AA - 3.03.STLのコンテナ](https://atcoder.jp/contests/apg4b/tasks/APG4b_aa)
#### 補足
- mapの操作について紹介されているところで、```.at(key)```と```[]```の2種類のアクセスの記法が紹介されていますが、```[]```推奨です。
- forループ内で毎回O(log N)の操作をする場合、計算量はO(Nlog N)となりますが、$log_2 N$の値はN = $10^5$でも16.6程度なので、N <= $10^5$程度であれば実行時間制限には余裕を持って間に合います
## 演習
pairやSTLのコンテナにまつわる問題を解きましょう。
[B - 投票](https://atcoder.jp/contests/abc231/tasks/abc231_b)
[B - Count Distinct Integers](https://atcoder.jp/contests/abc240/tasks/abc240_b)
[B - Booby Prize](https://atcoder.jp/contests/abc213/tasks/abc213_b)
(選手のスコア, 選手の番号)を表すpairの配列を考えてみましょう
[B - Do you know the second highest mountain?](https://atcoder.jp/contests/abc201/tasks/abc201_b)
一個前と同じような感じで解くことができます
[C - gacha](https://atcoder.jp/contests/abc164/tasks/abc164_c)
[C - Poll](https://atcoder.jp/contests/abc155/tasks/abc155_c)
[C - Route Map](https://atcoder.jp/contests/abc236/tasks/abc236_c)
急行列車が止まる駅名の集合を表すsetを作りましょう
[C - Counting 2](https://atcoder.jp/contests/abc231/tasks/abc231_c)
難しいです。lower_boundを使います
Sign in with Wallet
Connect another wallet