AtCoder C++リファレンス（茶コーダー向け）

## はじめに
茶コーダーが入緑するために習得中の知識をまとめています。
主にABC203以降に出題された問題と典型90問から習得しており、「出題」欄に出展を記載しています。

## C問題

### 繰り返し二乗法（べき乗の高速計算）
```C++
int rep_pow(int_ a, int_ b) {
    if (b == 0) return 1;
    auto ans = rep_pow(a * a % m, b / 2);
    if (b % 2 == 1) ans = ans * a % m;
    return ans;
}
```
出題：ABC178, 典型069

### 見かけ上の変化をメモ
シフトや反転が複数回行われる場合、愚直な実装では計算量がオーバーする。

```C++
bool flip_flag = false;
rep (i, Q) {
    int t, a, b;
    cin >> t >> a >> b;
    if (t == 1) {
        if (flip_flag) swap(S[(a + N) % (2 * N)], S[(b + N) % (2 * N)]);
        else swap(S[a], S[b]);
    } else {
        flip_flag = !flip_flag;
    }
}
```
出題：ABC199, 典型044

### 数字文字列の0埋め
```C++
ostringstream sout;
sout << setfill('0') << setw(4) << i;
auto s = sout.str()
```
出題：ABC201

### 文字の数値化
atoi, stoiはstringをintに変換する関数であり、char型には対応していない。
（char*型には対応しているが、1文字ずつ数値化したい時に後続の文字も一緒に数値化されて困る）

```C++
auto number = int(ch-'0')
```
出題：ABC201, ABC221

### 二重ループを一重ループ２回に分解
```C++
unordered_map<int, int> counts;
rep (j, N) counts[B[C[j] - 1]]++;

int ans = 0;
rep (i, N) ans += counts[A[i]];
```
出題：ABC202

### vector< pair >の入力とソート
一つ目の要素をkeyとしてソートされる

```C++
vector<pair<int_, int_>> seq(N);
for (auto& s: seq) cin >> s.first >> s.second;
sort(seq.begin(), seq.end());
```
出題：ABC203

### vectorをある値で埋める
```C++
fill(seq.begin(), seq.end(), value)
```
出題：ABC204

### DFS/BFS（行ける場所のカウント）
到着時刻を記録する必要はない。
flagsがそのまま、行ける場所のカウントに利用できる。

```C++
vector<vector<int>> roads_list;
vector<bool> flags;
void dfs(int s) {
    if (flags[s]) return;
    flags[s] = true;
    for (auto& v: roads_list[s]) dfs(v);
}
int main() {
    dfs(0);
    ans = count(flags.begin(), flags.end(), true);
}
```
```C++
void bfs(int s) {
    queue<int> q;
    q.push(s);
    flags[s] = true;
    while (!q.empty()) {
        auto v = q.front(); q.pop();
        // 全部キューに入れて通った場所の処理を飛ばすと
        // もっと簡単に書けるが、処理の無駄は多くなる
        for (auto& nv: roads_list[v]) if (!flags[nv]) {
            q.push(nv);
            flags[nv] = true;
        }
    }
}
```
出題：ABC204

### argsort
```C++
vector<int> indices(N);
iota(indices.begin(), indices.end(), 0);  // 連番
stable_sort(indices.begin(), indices.end(), [&](int i, int j) {return seq[i] < seq[j];});
```
出題：ABC208

### 順位付け(argsortされたindicesに対する処理)
```C++
vector<int> ranks(N);
rep (i, N) ranks[indices[i]] = i;
```
出題：ABC208

### 連想配列(Pythonのdict)
```C++
// カウント
unordered_map<int, int> counts;
rep (i, N) counts[colors[i]]++; // keyは自動で追加、int型valueのデフォルト値は0
```
```C++
// 重複チェック
unordered_map<string, int> names;
rep (i, N) {
    string name;
    cin >> name;
    if (names[name] == 0) {
        cout << i + 1 << endl;
        names[name] = 1;
    }
}
```
出題：ABC202, ABC210, 典型027

### 座標圧縮
```C++
set<int> seq_set(seq.begin(), seq.end());
vector<int> uniq_seq(seq_set.begin(), seq_set.end());
for (auto& elem : seq) elem = lower_bound(uniq_seq.begin(), uniq_seq.end(), elem) - uniq_seq.begin();
```
出題：ABC213

### argmin
```C++
int min_idx = distance(seq.begin(), min_element(seq.begin(), seq.end()));
```
出題：ABC214

### 順列生成
```C++
sort(seq.begin(), seq.end());
while (N > 0) {
    next_permutation(seq.begin(), seq.end());
    N--;
}
```
```C++
do {
    for (auto& c: seq) cout << c;
    cout << endl;
} while (next_permutation(seq.begin(), seq.end()));
```
```C++
vector<int> players(N);
iota(players.begin(), players.end(), 0);
int min_time = max_time;
do {
    int time = 0;
    rep (i, N - 1) time += times[players[i]][i];
    min_time = min(min_time, time);
} while (next_permutation(players.begin(), players.end()));
```
出題：ABC215, 典型002, 典型032

### bit全探索
```C++
rep (bit, 1<<seq.size()) {
    rep (i, seq.size()) {
        if (bit & 1<<i) cout << "hoge";
    }
}
```
出題：ABC221

### スワップ
配列内の要素も入れ替えられる。
```C++
swap(seq[p0], seq[p1);
```
出題：ABC199, ABC250

### 要素の位置の辞書
```C++
vector<ll> val(N+1), pos(N+1);
rep (i, N+1) val[i] = pos[i] = i;
rep (i, Q) {
    ll x;
    cin >> x;

    ll p0 = pos[x];
    ll p1 = p0 + 1;

    swap(pos[val[p0]], pos[val[p1]]);
    swap(val[p0], val[p1]);
}
```
出題：ABC250

### 順序付き多重集合
```C++
multiset<ll> seq;
rep (i, Q) {
    ll t;
    cin >> t;
    if (t == 1) {
        ll x;
        cin >> x;
        seq.insert(x);
    } else if (t == 2) {
        ll x, c;
        cin >> x >> c;
        while (c-- && seq.find(x) != seq.end()) {
            seq.erase(seq.find(x));
        }
    } else {
        cout << *seq.rbegin() - *seq.begin() << endl;
    }
}
```
出題：ABC253

## D問題

### deque(双方向連結リスト)
```C++
deque<char> deq;
rep (i, Q) {
    cin >> F >> c;
    if (F == 1) deq.push_front(c);
    else deq.push_back(c);
}
```
出題：ABC158, 典型061

### 累積和
```C++
vector<vector<int>> make_integral_img(vector<vector<int>> A, int_ th) {
    vector<vector<int>> S(N + 1, vector<int>(N + 1, 0));
    rep (i, N) rep (j, N) S[i + 1][j + 1] = S[i + 1][j] + S[i][j + 1] - S[i][j] + (A[i][j] >= th);
    return S;
}

bool isOK(vector<vector<int>> A, int th) {
    auto S = make_integral_img(A, th);
    rep (i, N - K + 1) {
        rep (j, N - K + 1) {
            if (S[i + K][j + K] - S[i + K][j] - S[i][j + K] + S[i][j] < K * K / 2 + 1) return false;
        }
    }
    return true;
}
```
出題：ABC203

### （めぐる式）二分探索
```C++
int binary_search(vector<vector<int>> A) {
    int_ ok = 0;
    int_ ng = 1000000001;
    while (abs(ok - ng) > 1) {
        int_ mid = (ok + ng) / 2;
        if (isOK(A, mid)) ok = mid;
        else ng = mid;
    }
    return ok;
}
```
出題：ABC203, 典型001

### 部分和問題（01ナップサックの特殊ケース）
部分和問題は01ナップサックの重さと価値が同じケース。
公式動画解説では一次元化＋bitset化してるが必須ではない。

```C++
vector<vector<int>> dp(N + 1, vector<int>(max_weight + 1, 0)); // 配列サイズ注意
rep (i, N) {
    rep (t, max_weight + 1) {
        if (weights[i] > t) dp[i + 1][t] = dp[i][t];
        // 01ナップサックだと最後のweights[i]がvalues[i]になる
        else dp[i + 1][t] = max(dp[i][t], dp[i][t - weights[i]] + weights[i]);
    }
}
```
出題：ABC204

### 二分探索
```C++
auto idx = upper_bound(seq.begin(), seq.end(), query) - seq.begin();
auto idx = distance(seq.begin(), upper_bound(seq.begin(), seq.end(), query));
auto iter = upper_bound(seq.begin(), seq.end(), query);
```
最初の要素より小さい場合と最後の要素より大きい場合に注意

```C++
rep (i, Q) {
    cin >> B;
    int diff;
    auto iter = upper_bound(classes.begin(), classes.end(), B);
    if (iter == classes.end()) diff = abs(*(classes.end() - 1) - B);
    else if (iter == classes.begin()) diff = abs(*classes.begin() - B);
    else diff = min(abs(*iter - B), abs(*(iter--) - B));
    cout << diff << endl;
}
```
出題：ABC205、典型007

### BFS（最短距離）
distancesをflagsの代わりとして利用できる。

```C++
vector<int_> distances;
void bfs(int_ s) {
    queue<int_> q;
    q.push(s);
    distances[s] = 0;
    while (!q.empty()) {
        auto v = q.front(); q.pop();
        for (auto& nv: roads_list[v]) {
            if (distances[nv] == -1) {
                q.push(nv);
                distances[nv] = distances[v] + 1;
            }
        }
    }
}
```
出題：ABC209, 典型003(木の直径)

### 優先度付きキュー
```C++
priority_queue<int, vector<int>, greater<int>> pq;
rep (i, Q) {
    int p;
    cin >> p;
    if (p == 1) {
        int x;
        cin >> x;
        pq.push(x);
    } else {
        auto num = pq.top(); pq.pop();
        cout << num << endl;
    }
}
```
出題：ABC212

### 木のDFS
flag管理は不要、一つ前にいた場所を引数としてもらえばよい。
木を戻っていく順番まで記録するなど、木を前提にしないと解けないケースあり？

```C++
void dfs(int crr, int pre) {
    history.emplace_back(crr);
    for (auto& next: roads_list[crr]) if (next != pre) {
        dfs(next, crr);
        history.emplace_back(crr);
    }
}
```
出題：ABC213

### sortのkey指定
key指定は面倒なので、keyにしたいものを最初の要素にしておく。

```C++
vector<tuple<int, int, int>> edge(N);
for (auto& [w, u, v] : edge) cin >> u >> v >> w;
sort(edge.begin(), edge.end());
```
出題：ABC214

### UnionFind
```C++
#include <atcoder/dsu>
atcoder::dsu dsu(N);
int ans = 0;
for (auto& [w, u, v] : edges) {
    ans += w * dsu.size(u) * dsu.size(v);
    dsu.merge(u, v);
}
```
```C++
if (!dsu.same(a, b)) dsu.merge(a, b);
```
出題：ABC206, ABC214

### 素因数分解
```C++
vector<int> factorize(int elem) {
    vector<int> primes;
    for (int i = 2; i * i <= elem; i++) {
        while (elem % i == 0) {
            elem /= i;
            primes.emplace_back(i);
        }
    }
    if (elem != 1) primes.emplace_back(elem);
    return primes;
}
```
出題：ABC215, 典型075

### 順序付き集合
途中で挿入・削除したり、参照したりを繰り返す場合に使う（クエリに種類があるケースなど）。
途中で挿入・削除する必要が無いならvectorをsortして二分探索した方が速い。
Pythonのbisectも同様の処理が可能だが、setよりかなり遅くLTEする。

```C++
set<int> cuts;
rep (i, Q) {
    int_ c, x;
    cin >> c >> x;
    if (c == 1) cuts.insert(x);
    else {
        auto upper = cuts.lower_bound(x);
        cout << *upper - *(--upper) << endl;
    }
}
```
```C++
ll ans = 0;
ll max_score = 0;
rep (i, N) {
    string S;
    ll T;
    cin >> S >> T;
    auto result = originals.insert(S);
    if (result.second && (T > max_score)) {
        ans = i;
        max_score = T;
    }
}
```
出題：ABC217, ABC228, ABC251(C)

### 尺取り法
```C++
int_ ans = 0, r = 0;
rep (l, S.size()) {
    while(r < S.size() && cnt[r + 1] - cnt[l] <= K) r++;
    ans = max(ans, r - l);
}
```
出題：ABC229