【第6回】はじめての競技プログラミング

stack

stackは後入れ先出しのデータ構造
最後に追加したものを取り出すことができる
縦に積まれた本のイメージ

使い方

関数	機能	計算量
`stack<型> s;`	stack型の変数`s`を宣言する	$O(1)$
`s.push(x);`	stack型の変数`s`に`x`を追加する	$O(1)$
`s.top()`	stack型の変数`s`の最後の要素にアクセスする	$O(1)$
`que.pop()`	stack型の変数`s`の最後の要素を削除する	$O(1)$
`que.size()`	stack型の変数`s`の要素数を取得する	$O(1)$
`que.empty()`	stack型の変数`s`が空かどうかを調べる	$O(1)$
`s1 = s`	stack型の変数`s`をstack型の変数`s1`に代入する	$O(N)$

#include <bits/stdc++.h>
using namespace std;
int main() {
    stack<int> s,s1;
    cout << boolalpha;
    cout << s.empty() << endl;  // true
    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.empty() << endl;  // false
    cout << s.size() << endl;   // 3
    cout << s.top() << endl;    // 3
    s.pop();
    cout << s.size() << endl;   // 2
    cout << s.top() << endl;    // 2
    s1=s;
    cout << s1.size() << endl;  // 2
    cout << s1.top() << endl;   // 2
    s.pop();
    s.pop();
    cout << s.size() << endl;   // 0
    cout << s.empty() << endl;  // true
}

cout << boolalpha;とは、.empty()などを0/1ではなくtrue/falseで出力するようにするものです

例題

ヒント

まずクエリの数を受け取り、その回数分だけfor文を回してクエリをそれぞれ処理していきましょう
行列の現在の状態をstackで管理してみましょう

解答例

#include <bits/stdc++.h>
using namespace std;
int main() {
    int q;
    cin >> q;
    stack<string> s;
    for (int i = 0; i < q; i++) {
        int a;
        cin >> a;
        if (a == 1) {
            string x;
            cin >> x;
            s.push(x);
        }
        else if (a == 2) {
            cout << s.top() << endl;
        }
        else if (a == 3) {
            s.pop();
        }
    }
}

queue

queueは先入れ先出しのデータ構造
値を追加した順に取り出すことができる
順番待ちの行列のイメージ

使い方

関数	機能	計算量
`queue<型> que;`	queue型の変数`que`を宣言する	$O(1)$
`que.push(x);`	queue型の変数`que`に`x`を追加する	$O(1)$
`que.front();`	queue型の変数`que`の先頭の要素にアクセスする	$O(1)$
`que.back()`	queue型の変数`que`の最後の要素にアクセスする	$O(1)$
`que.pop()`	queue型の変数`que`の先頭の要素を削除する	$O(1)$
`que.size()`	queue型の変数`que`の要素数を取得する	$O(1)$
`que.empty()`	queue型の変数`que`が空かどうかを調べる	$O(1)$
`q1 = que`	queue型の変数`que`をqueue型の変数`q1`に代入する	$O(N)$

#include <bits/stdc++.h>
using namespace std;
int main() {
    queue<int> que, q1;
    cout << boolalpha;
    cout << que.empty() << endl;    // true
    que.push(1);
    que.push(2);
    que.push(3);
    cout << que.empty() << endl;    // false
    cout << que.size() << endl;     // 3
    cout << que.front() << endl;    // 1
    cout << que.back() << endl;     // 3
    que.pop();
    q1 = que;
    cout << q1.size() << endl;      // 2
    cout << q1.front() << endl;     // 2
    cout << que.size() << endl;     // 2
    cout << que.front() << endl;    // 2
    cout << que.back() << endl;     // 3
    que.pop();
    que.pop();
    cout << que.empty() << endl;    // true
}

例題

ヒント

まずクエリの数を受け取り、その回数分だけfor文を回してクエリをそれぞれ処理していきましょう
行列の現在の状態をqueueで管理してみましょう

解答例

#include <bits/stdc++.h>
using namespace std;
int main() {
    int q;
    cin >> q;
    queue<string> que;
    for (int i = 0; i < q; i++) {
        int query;
        cin >> query;
        if (query == 1) {
            string x;
            cin >> x;
            que.push(x);
        }
        else if (query == 2) {
            cout << que.front() << endl;
        }
        else if (query == 3) {
            que.pop();
        }
    }
}

priority_queue

優先度付きキューとも呼ばれる
追加した値のうち大きい順に取り出すことができる
priority_queue<型, vector<型>, greater<型>> 変数名;と書くことで小さい順に取り出されるように宣言できる。

使い方

関数	機能	計算量
`priority_queue<型> pq;`	priority_queue型の変数`pq`を宣言する	$O(\log N)$
`pq.push(x);`	priority_queue型の変数`pq`に`x`を追加する	$O(1)$
`pq.top()`	priority_queue型の変数`pq`の中で最大の要素にアクセスする	$O(1)$
`pq.pop()`	priority_queue型の変数`pq`中で最大の要素を削除する	$O(\log N)$
`pq.size()`	priority_queue型の変数`pq`の要素数を取得する	$O(1)$
`pq.empty()`	priority_queue型の変数`pq`が空かどうかを調べる	$O(1)$

#include <bits/stdc++.h>
using namespace std;
int main() {
    priority_queue<int> pq, pq1;
    cout << boolalpha;
    cout << pq.empty() << endl;    // true
    pq.push(1);
    pq.push(2);
    pq.push(3);
    cout << pq.empty() << endl;     // false
    cout << pq.size() << endl;      // 3
    cout << pq.top() << endl;       // 3
    pq.pop();
    pq1 = pq;
    cout << pq1.size() << endl;      // 2
    cout << pq1.top() << endl;       // 2
    cout << pq.size() << endl;      // 2
    cout << pq.top() << endl;       // 2
    pq.pop();
    pq.pop();
    cout << pq.empty() << endl;     // true
}

問題

ヒント

まずクエリの数を受け取り、その回数分だけfor文を回してクエリをそれぞれ処理していきましょう
商品をpriority_queueで管理してみましょう

解答例

#include <bits/stdc++.h>
using namespace std;
int main() {
    int q;
    cin >> q;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < q; i++) {
        int a;
        cin >> a;
        if (a == 1) {
            int x;
            cin >> x;
            pq.push(x);
        }
        else if (a == 2) {
            cout << pq.top() << endl;
        }
        else if (a == 3) {
            pq.pop();
        }
    }
}

deque

両端キューとも呼ばれる
前からでも後ろからでも出し入れできるができる　~~上位互換?~~
vectorのように.at(i)やeraseもできる
vectorに比べてメモリを圧迫することに注意

使い方

関数	機能	計算量
`deque<型> d;`	deque型の変数`d`を宣言する	$O(1)$
`d.at(i)`, `d[i];`	deque型の変数`d`の`i`番目の要素にアクセスする	$O(1)$
`d.push_back(x);`	deque型の変数`d`の最後に`x`を追加する	$O(1)$
`d.push_front(x);`	deque型の変数`d`の先頭に`x`を追加する	$O(1)$
`d.insert(d.begin()+i, j)`	deque型の変数`d`の`i`番目と`1+1`番目の間に`j`を挿入する	$O(N)$
`d.pop_back()`	deque型の変数`d`中で最後の要素を削除する	$O(1)$
`d.pop_front()`	deque型の変数`d`中で最初の要素を削除する	$O(1)$
`d.size()`	deque型の変数`d`の要素数を取得する	$O(1)$
`d.empty()`	deque型の変数`d`が空かどうかを調べる	$O(1)$
`d.clear()`	deque型の変数`d`の中の全ての要素を削除する	$O(N)$
`d1 = d`	deque型の変数`d`をdeque型の変数`d1`に代入する	$O(N)$

#include <bits/stdc++.h>
using namespace std;
int main() {
    deque<int> d, d1;
    cout << boolalpha;
    cout << d.empty() << endl;  // true
    d.push_back(2);
    d.push_back(4);
    d.push_front(1);
    d.insert(d.begin()+2,3);
    cout << d.empty() << endl;  // false
    cout << d.size() << endl;   // 4
    cout << d.front() << endl;  // 1
    cout << d.at(1) << endl;    // 2
    cout << d[2] << endl;       // 3
    cout << d.back() << endl;   // 4
    d.pop_back();
    d.pop_front();
    cout << d.size() << endl;   // 2
    cout << d.front() << endl;  // 2
    cout << d.back() << endl;   // 3
    d1 = d;
    cout << d1.size() << endl;  // 2
    cout << d1.front() << endl; // 2
    cout << d1.back() << endl;  // 3
    d.clear();
    cout << d.empty() << endl;  // true
}

問題

ヒント

dequeに数値を入れていってソートして前後 $n$ 個を削除しましょう
vectorと同じ形でソートできます
小数点以下まで出力する必要があるのでdouble型を使いましょう
小数点以下15桁を出力したい場合は出力の前にcout << fixed << setprecision(15);を書けばよいです

解答例1

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    deque<int> d;
    for (int i = 0; i < 5 * n; i++) {
        int x;
        cin >> x;
        d.push_back(x);
    }
    sort(d.begin(),d.end());
    for (int i = 0; i < n; i++) {
        d.pop_back();
        d.pop_front();
    }
    double ans = 0;
    for (int i = 0; i < 3 * n; i++) {
        ans += d.at(i);
    }
    cout << fixed << setprecision(15);
    cout << ans / (3 * n) << endl;
}

解答例2

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    deque<int> d;
    double ans = 0;
    for (int i = 0; i < 5 * n; i++) {
        int x;
        cin >> x;
        d.push_back(x);
        ans += x;
    }
    sort(d.begin(),d.end());
    for (int i = 0; i < n; i++) {
        ans -= d.front();
        ans -= d.back();
        d.pop_back();
        d.pop_front();
    }
    cout << fixed << setprecision(15);
    cout << ans / (3 * n) << endl;
}

【第6回】はじめての競技プログラミング

stack

使い方

例題

queue

使い方

例題

priority_queue

使い方

問題

deque

使い方

問題

問題集

stack

queue

deque

【第5回】はじめての競技プログラミング

【第7回】計算量