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

はじめに

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

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

見かけ上の変化をメモ

シフトや反転が複数回行われる場合、愚直な実装では計算量がオーバーする。

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埋め

ostringstream sout;
sout << setfill('0') << setw(4) << i;
auto s = sout.str()

出題：ABC201

文字の数値化

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

auto number = int(ch-'0')

出題：ABC201, ABC221

二重ループを一重ループ２回に分解

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としてソートされる

vector<pair<int_, int_>> seq(N);
for (auto& s: seq) cin >> s.first >> s.second;
sort(seq.begin(), seq.end());

出題：ABC203

vectorをある値で埋める

fill(seq.begin(), seq.end(), value)

出題：ABC204

DFS/BFS（行ける場所のカウント）

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

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);
}

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

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に対する処理)

vector<int> ranks(N);
rep (i, N) ranks[indices[i]] = i;

出題：ABC208

連想配列(Pythonのdict)

// カウント
unordered_map<int, int> counts;
rep (i, N) counts[colors[i]]++; // keyは自動で追加、int型valueのデフォルト値は0

// 重複チェック
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

座標圧縮

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

int min_idx = distance(seq.begin(), min_element(seq.begin(), seq.end()));

出題：ABC214

順列生成

sort(seq.begin(), seq.end());
while (N > 0) {
    next_permutation(seq.begin(), seq.end());
    N--;
}

do {
    for (auto& c: seq) cout << c;
    cout << endl;
} while (next_permutation(seq.begin(), seq.end()));

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全探索

rep (bit, 1<<seq.size()) {
    rep (i, seq.size()) {
        if (bit & 1<<i) cout << "hoge";
    }
}

出題：ABC221

スワップ

配列内の要素も入れ替えられる。

swap(seq[p0], seq[p1);

出題：ABC199, ABC250

要素の位置の辞書

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

順序付き多重集合

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(双方向連結リスト)

deque<char> deq;
rep (i, Q) {
    cin >> F >> c;
    if (F == 1) deq.push_front(c);
    else deq.push_back(c);
}

出題：ABC158, 典型061

累積和

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

（めぐる式）二分探索

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化してるが必須ではない。

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

二分探索

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);

最初の要素より小さい場合と最後の要素より大きい場合に注意

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の代わりとして利用できる。

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(木の直径)

優先度付きキュー

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

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にしたいものを最初の要素にしておく。

vector<tuple<int, int, int>> edge(N);
for (auto& [w, u, v] : edge) cin >> u >> v >> w;
sort(edge.begin(), edge.end());

出題：ABC214

UnionFind

#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);
}

if (!dsu.same(a, b)) dsu.merge(a, b);

出題：ABC206, ABC214

素因数分解

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する。

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;
    }
}

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)

尺取り法

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