C++で学んだことを書き留めておく場(競プロ向け)

　競技プログラミングをやっていく過程で学んだことをひたすら書き留めていくだけ

　自分用のメモ帳みたいな感覚で使っていきますが、折角なので記事として残して後世に語り継いで行こうと思いました。

　学べば学ぶほど随時追加していく予定です。筆者は現在緑へ向かっているところなので、記事の内容はC,D問題が解けない人向けだと思われます。

　間違いやアドバイス等があれば教えていただけると幸いです。

内容

・定数・マクロ定義
・emplace_back
・pair
・priority_queue
・補足

定数・マクロ定義

#define rep(i, n) for(int i=0; i<n; i++)  //defineでfor(int i=0; i<n; i++)をrep(i, n)と定義
#define PI 3.14159265359                  //3.14159265359をPIと定義
#define INF (1<<30)                       //(1<<30)をINFと定義

int main(void) {
    rep(i, 10) cout << i << " ";          //for(int i=0; i<10; i++) cout << i << " "; と同義
}

/*
出力
0 1 2 3 4 5 6 7 8 9 
*/

　競プロの解説見てるとほぼ必ずと言っていいほど使用される書き方。
　はじめにこれを覚えないと解説でrepを見るたびに混乱してしまうので、競プロガチ勢になりたいなら早めになれたほうがいいと私は思います。

　ここでは、for(int i=0; i<n; i++)をrep(i, n)と定義しています。
for(int i=0; i<n; i++)の代わりにrep(i, n)って書いたほうがコストかからないよねってことです。
　定数定義のサンプルコードを省略しましたが、使い方は普通の変数と変わらないと思われます。何か違いがあったら記述するかも。
　なお、この記事でもrepの書き方を使用していきます。皆さんも一緒に慣れていきましょう。決してめんどくさいからではありません。

emplace_back

#define rep(i, n) for(int i=0; i<n; i++)

int main(void) {
    vector<int> a {1, 2, 3};            //push_backの場合
    a.push_back(4);
    for( auto i : a ) cout << i << " ";
    
    cout << "\n";
    
    vector<int> b {1, 2, 3};            //emplace_backの場合
    b.emplace_back(4);
    for( auto i : a ) cout << i << " ";
}

/*
出力
1 2 3 4 
1 2 3 4 
*/

　挙動はpush_backと同じですが、効率がいいようです。
push_backは一時的にオブジェクトを作成し、それを利用して値を更新しているようですが、
emlpace_backは一時オブジェクトの作成をせずに追加しているようです。(以下の記事参照)

push_backでの追加は27.967msの処理時間だが、emplace_backは25.997ms。
emplace_backの方が処理時間は速い。
どちらも処理結果は同じだが、処理効率には差が出る。

　ただ、emplace_backはpusk_backより文字数が多いため、記述する際は効率的ではないかもしれません。計算量が膨大で実行時間が間に合うかどうかギリギリの際や、TLEが出てしまって少しでも早くコードを動かしたい際などに使用するといいかもしれません。

pair

pair<char, int> d {'a', 3};
cout << d.first << " " << d.second;

/*
出力
a 3
*/

　名前の通り二つの要素をペアで格納できます。
　配列と組み合わせてランレングス圧縮を格納したり、二次元リストの座標を格納したりと色々なことに使えます。
　値はfirst、secondで取得できますが、タプルのようにget<0>(d)、get<1>(d)でも取得できます。

priority_queue

vector<int> a{3, 5, 8, 1, 0};
priority_queue<int> q;

rep(i, 5) {
  q.push(a.at(i));  //要素を追加
}

while(!queue.empty()) {
    cout << q.top() << " ";  //最大の値を取得
    q.pop();  //最大の値を削除
}
/*
出力
8 5 3 1 0 
*/

　優先順位付きキューを作成できます。いわゆるヒープ構造です。
イメージとしては以下のような感じです。

      8                  8 <-親
    /   \              /   \
   3     5            3     5 <-子
  / \
 1   0

　親は子より大きな値を持つというルールがあります。したがって、最大の値が常に頂点に来るように整列されています。
　top()で頂点にアクセスでき、pop()で頂点の要素を取り出すことができます。頂点が取り出された場合は一つ下の要素の大きいほうが上に移動するので、常に最大の値が頂点に来ることになります。

priority_queue<int, vector<int>, greater<int> q;

　宣言を以上のように書き換えることにより、昇順のヒープを作成できます。

例題

解説

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
int main(void){
    long long q; cin >> q;
    priority_queue<long long, vector<long long>, greater<long long>> queue;
    rep(i, q) {
        long long a, h; cin >> a >> h;
        if (a == 1) queue.push(h);     //ヒープに要素を追加
        else  //h以下の要素を削除
        {
            while (!queue.empty() && queue.top() <= h) queue.pop();
        }
        //ヒープの要素数を出力
        cout << queue.size() << endl;
    }
}

　昇順のヒープを作成します。
　タイプ1の場合hをヒープに追加するだけで大丈夫です。自動的に昇順に並んでくれます。
　タイプ2の場合、「最小値がh以下かつ要素が空でない間」繰り返し、最小値を削除し続けます。
　クエリを処理した後にヒープの要素数を出力すると正解となります。

補足

　この記事の内容はあくまで一例に過ぎないので、自分に合った書き方をするのが一番だと思います。業務での実装と違い、他人に見せる必要が(ほとんど)ないのでめちゃくちゃ効率を重視した書き方をしてもいいのです。(repすらも省略してrにする等)
　色々な書き方を試しながら、一番しっくりくる書き方を探してみましょう！