2019-12-08

筑波、阪大、京大の編入試験に合格した話

編入

はじめまして川本です。この記事では筑波大学情報学群情報科学類、大阪大学工学部電子情報工学科情報通信工学科目、京都大学工学部情報学科計算機科学コースの編入体験談を書きたいと思います。

ただの自己満足ポエムになりそうな気もしますが、誰かの役に立てると嬉しいです。

自己紹介

出身高専：舞鶴高専

学科：電気情報工学科

部活動：陸上部、プロコン部

趣味：競技プログラミング、お菓子作り、ピアノ（初心者）

席次：１位

ゲームはあまりしなくて、アニメもたまにしか見ないので周りからは勉強オタクと思われていました。実際に普段から勉強する習慣がついているほうだと思います。これが受験シーズンにも結構役立った気がする

受験結果

筑波情報学群情報科学類：合格

阪大電子情報工学科情報通信工学科目：合格

京大工学部情報学科計算機工学コース：合格

編入成功組です。結局阪大に進学することにしました。理由は後で書きますが、やはり２年次編入で京大と３年次編入で阪大を比較すると阪大が勝つでしょ。

志望動機

他の人たちみたいに研究がしたいなどかっこいい動機はありません。高専卒で就職するのが嫌だったことが大きいかなと思います。

１、２年のときからなんとなく大学に進学しようと考えていました。ただこのときは漠然と大学進学するほうが将来有利でしょぐらいにしか考えていませんでした。進学するために席次は１位を取ろうと思いかなりしっかり勉強していました。

３年のときに課外活動や学校の課題、資格試験が重なり試験勉強の時間が確保出来ませんでした。ここで初めて前日勉をしたのですが平均点がほぼ落ちませんでした（素点平均97→96だったと思う）。ここから優等生川本くんは消え去り授業を聞かなくなります。

この頃は授業聞かなくて席次１位取れるわ、プレコンでいきなり近畿優勝するわ、myRIO組み込みシステム開発コンテストで全国３位になるわと成功を重ねたせいで完全に天狗になります。

転機

４年の終わりに競技プログラミングをはじめました。初めて参加して全く歯が立ちませんでした。正直もっとできると思っていたのに3000人中2800位とかで大学生の圧倒的な強さを実感しました（競技プログラミングやってる人の多くは旧帝大の学生だったり旧帝大OBだったり、中高生はJOIレベルばかりの化物揃いなので勝てなくて当然ということをあとから知りました）。

ここで高専の狭さを実感し、今よりもっとレベルの高い世界へ行きたいと思い大学へ進学への思いがた固まりました（遅くないですか？）。漠然と進学勉強をしていたおかげでここから対策をしても十分間に合ったのが幸いです。

受験勉強について

３年の頃には高専の授業に見切りをつけたので授業中を自分の勉強に充てていました。聞きたい授業だけ聞いて他の時間は好きなことしたり、受験勉強したりしてました。（これが許される高専のゆるさに感謝）

３年の課外活動と課題と資格試験と色々重なっていた時期に徹夜耐性ができたので３年の後半から受験終わりまでずっと２日に１回４時間睡眠の生活をしてました。おかげで時間は無限にありました笑。※良い子は真似しないでください。

３年の間に編入数学徹底研究を一周しました。TOEICを２回受験し、580点、630点でした。

４年になってからは創造工学（研究室配属に関わる科目）、Yahooのハッカソン、研修旅行の英語発表、高専プレコン、高専プロコン、起業家甲子園、高専駅伝などイベントが盛り沢山で授業時間と深夜ぐらいしか勉強時間が確保出来ませんでした。

４年でTOEIC 765点、TOEFL 53点、を取得、編入数学徹底研究をほぼ全部解けるようにして、編入数学過去問特訓や物理の勉強にも手をつけていました。この頃に進学先を京大、阪大、筑波に決めて、第一志望を京大と考えていました。

４年の間はTOEICとTOEFLはぞれぞれ１回しか受けてないのですがボーダー以上のスコアを回収出来てよかったです。これが取れないと５年になってからしんどい。今思えばこの時点で合格レベルの数学力があったのもかなり強かったなと思います。

徹夜耐性があるとはいえ寝たいので、勉強の効率も大事にしてました。例えば、１度自力で解けた問題は復習しませんでした。苦手な問題だけ解くことで効率よく苦手を潰すことが出来たと思います。また、数学の問題は方針だけ考えて計算をしませんでした。答えと方針が同じなら解けるやろって安易な発想です。書かないので圧倒的に速いです。狙ったわけではありませんが副産物として謎の暗算力が身につきます。

４年の終わり頃から競技プログラミングを始めます。簡単に説明すると数学パズルをプログラムで解く競技です。直接受験に役立つわけではありませんが柔軟な思考力と簡単な問題の瞬殺力がつきます。京大受験にはかなり役立ったと思います（あくまで個人の感想）。

５年からは物理の問題をしたりもう少しレベルの高い数学の問題を解いたりしてました。それから阪大と筑波の過去問をときました。研究室の先生がお前は受験勉強しろと言ってくれたので実験以外の授業は受験勉強の時間になりました。今まで課外活動に充てていた時間を競技プログラミングに充てたので勉強時間はあまり変わりません。通学生になったので時間は増えました（深夜に魔剤買いにいけるの最高か？）。

筑波大学

TOEICと数学、専門だけなのでこんなにコスパいい滑り止めある？とか思いながら受験しました。

このころAtCoder水色になっていたので国内の同学年の中では100位以内に入れる強さで高専に絞ると10本指には入れるくらいだったので専門の心配はしていませんでした。TOEICは４年の秋に取った765から受験しに行っていません。

数学はしっかり対策しました。編入数学過去問特訓、編入数学徹底研究、数学／徹底演習、明快演習微分積分、明快演習線形代数をひととおりおさえました（明快演習シリーズは難しすぎるので半分くらいしか解けてません）。

個人的には受けた３校のなかで筑波が一番数学のレベルが高い大学だと思っていたのでオーバーなくらい勉強して確実に点数を取りました。逆にこれ以降ほとんど数学の勉強をしていません笑。

テストの出来

自己評価：専門、数学両方10割

結果：合格

大阪大学

電磁気をしっかり対策しました。コンピュータ工学は過去問を見たら出来たので対策していません。

数学は複素関数をさらっただけで、微積は筑波のまま成長していません。当日になって統計が出ることを知り焦りました（は？）。英語は前日に文法の問題集を眺めただけです。

テストの出来

数学は統計が5割、複素関数7割、残りは10割

英語は7〜8割

専門は電磁気5割コンピュータ工学10割って感じの感触。電磁気でケアレスミスしたのが残念過ぎて（10割取れる問題だった）反省

取れる問題を落としたのでだめだなと思いながら面接を受けた

面接は優しかった（どのサークル入りたい？とか）。

（学校説明会に阪大の教授が来てくださり、そのときに聞いた話では阪大は基本的に編入生を取る気がなくて、筆記試験でよっぽど優秀な人がいれば取るぐらいの気持ちらしいです。なので試験は難しめだそう。採点のために作問者と別の教授が解くらしいのですがこれで苦労すると言っていました。面接は合否に関係ないそうです。これは工学部の話で他の学部は知らないです）

結果：合格

京都大学

阪大以降勉強をしない。

京大の４日前に阪大の合格発表ここで合格したのでやる気も失う。

京大の３日前に日本最強プログラマー学生選手権予選に出場し全国決勝進出を決める（受験勉強とは？）。

京大の前日にホテルではじめて過去問を開く。

眺めると物理と数学は簡単で化学は何もわからんので物理と数学だけ解くことにする。

当日

物理と数学にやるだけが置かれていたのでやる（１０割）

化学はわからないなりにできそうなところだけ解く（０．５割）

まあどちらにしろ阪大行くしとか思いながら面接で適当に喋る

結果：合格

漸化式の問題は競プロっぽかったので楽勝でした。最後の証明は誘導に乗れませんでしたが、関数内積の問題だとわかるので別の方法で雑に証明しました。

受験テクニック

見直しのテクニックについて

微分方程式：解を代入して成立するか確認しましょう
逆行列：掛けて単位行列になるか確認しましょう
固有値：固有値の和がトレースと一致するか確認しましょう
固有ベクトル：掛けて固有値倍になるか確認しましょう
積分：お絵かきすると明らかな上界と下界がわかるので満たしているか確認しましょう

正直受験生のレベルに大きな差はないと思うのでケアレスミスを如何になくすかが勝負の決め手だと思います。なので、勉強のときからケアレスミス対策を意識して解ける問題を確実に解くことが大事だと思います。

解くテクニックについて

はじめから答案を作りません。まず問題を眺めながら簡単に方針や必要そうな公式を書きます（例：積分、やるだけ、帰納法？など）。同時に得点効率をなんとなく計算して時間効率が良さそうなところからときます。

これは受験勉強の段階で方針を立てる力を磨いたおかげでできるのかもしれませんが、問題を見た瞬間に方針が立てられるならおすすめです。

もともと定期試験を直前勉強で突破するためのテクニックなのですが、編入試験でも役立ちました。

（定期試験では朝になってから勉強を始めるのですが、記述や暗記問題に対応できません。はじめの５分で忘れます。逆に始まった瞬間はどんな問題でも解けるので、はじめの５分ぐらいで自分が後から正解を思い出せるキーワードをそれぞれの問題に書きます。すると時間が経っても解けるので最強です。これほど極端に効果は出ないですが、編入試験でもはじめの５分が一番賢い時間だと思うので答案を書く作業に時間を割かずに一番賢い時間に解き切るのが最善だと思います）

なぜ阪大？

競技プログラミングのレベルだけで見ても京大は僕にとってレベルが高すぎる

レベルが高い集団に入ることで圧倒的成長を得るパターンもあるけれど、僕は耐えられないと思うので京大は厳しいなと思いました。阪大なら僕のレベルでもそこそこ通用するっぽいので（あくまで競技プログラミングでは）阪大なら楽しみながらスキルアップできると思いました。
旧帝大の教授はほぼ持ち回り、授業のレベルはそう大差ないらしい（出典：弊研究室教授）

授業のレベルが同じならどちらでもいいかなというお気持ちになりませんか？
京大は２年次編入、阪大は３年次編入　

実質１年留年。阪大受かったとして１浪して京大行きますか？という問題に帰着出来てこれなら答えはわかりきっていると思います。
内部生とうまく馴染めないらしい

去年京大に進学した先輩が京大の内部生との温度差、距離間を感じていてうまく馴染めていないようでしんどそうに思いました。阪大は競プロ関係で知り合いが多いので大丈夫だと信じています。

以上です。

ここまで読んでいただきありがとうございます。

2019-11-10

部内勉強会（４）

部内勉強会

競プロライブラリ集

よく使うライブラリを紹介します

今回はライブラリの使い方だけ紹介して中身の実装の話はほとんどしません（難しいので）

Union Find Tree
Combination
DAG
セグメント木
遅延セグメント木

Union Find Tree

緑になるには必須のライブラリ

持っていると簡単に解ける問題が多数

集合を管理するデータ構想

できる操作は

同じ集合に属しているか判定　O(1)
集合の併合　O(1)
集合のサイズを取得　O(1)

集合を分離することは出来ないので注意！

#include <bits/stdc++.h>
using namespace std;

class UnionFindTree
{
    vector<int> parent;
    vector<int> depth;
    vector<int> cnt;

public:
    UnionFindTree(int n) : parent(n), depth(n), cnt(n)
    {
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            depth[i] = 0;
            cnt[i] = 1;
        }
    }

    //木の根を求める
    int find(int x)
    {
        if (parent[x] == x)
        {
            return x;
        }
        else
        {
            return parent[x] = find(parent[x]);
        }
    }

    //xとyの属する集合を併合
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (depth[x] < depth[y])
        {
            parent[x] = y;
            cnt[y] += cnt[x];
        }
        else
        {
            parent[y] = x;
            cnt[x] += cnt[y];
            if (depth[x] == depth[y])
                depth[x]++;
        }
    }
    // 同じ集合に属しているか判定
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
    // 集合のサイズを取得
    int size(int x)
    {
        return cnt[find(x)];
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    UnionFindTree utree(n + 10);
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        utree.unite(x, y);
    }
    map<int, int> fl;
    int ans = n;
    for (int i = 1; i <= n; i++)
    {
        if (!fl[utree.find(i)])
        {
            fl[utree.find(i)] = 1;
            ans -= utree.size(i) - 1;
        }
    }
    cout << ans << endl;
}

例題

https://atcoder.jp/contests/abc126/tasks/abc126_e

解答

https://atcoder.jp/contests/abc126/submissions/8376002

例題

https://atcoder.jp/contests/abc120/tasks/abc120_d

解答

https://atcoder.jp/contests/abc120/submissions/8376028

例題

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c

解答

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8374498

Combination

同じく緑になるには必須のライブラリ

mod上でのnCr, nPr, nHrを高速に計算する

前処理O(N)

計算O(1)

#include <bits/stdc++.h>
using namespace std;

class Combination
{
    vector<long long> fact;
    vector<long long> factinv;
    long long MOD = 1e9 + 7;
    long long modpow(long long a, long long n)
    {
        if (n == 0)
            return 1;
        if (n % 2 == 0)
        {
            long long t = modpow(a, n / 2);
            return t * t % MOD;
        }
        return a * modpow(a, n - 1) % MOD;
    }

    long long modinv(long long a)
    {
        // mod is prime
        return modpow(a, MOD - 2);
    }

public:
    Combination(int n) : fact(n), factinv(n)
    {
        fact[0] = 1;
        for (int i = 1; i < n; i++)
        {
            fact[i] = fact[i - 1] * i % MOD;
        }
        factinv[n - 1] = modinv(fact[n - 1]);
        for (int i = n - 2; i >= 0; i--)
        {
            factinv[i] = factinv[i + 1] * (i + 1) % MOD;
        }
    }

    long long ncr(long long n, long long r)
    {
        if (r < 0 || r > n)
            return 0;
        return fact[n] * factinv[r] % MOD * factinv[n - r] % MOD;
    }

    long long npr(long long n, long long r)
    {
        if (r < 0 || r > n)
            return 0;
        return fact[n] * factinv[n - r] % MOD;
    }

    long long nhr(long long n, long long r)
    {
        if (n == 0 && r == 0)
            return 1;
        return ncr(n + r - 1, r);
    }
};

例題

https://atcoder.jp/contests/abc132/tasks/abc132_d

解答

https://atcoder.jp/contests/abc132/submissions/8375997

例題

https://atcoder.jp/contests/abc066/tasks/arc077_b

解答

https://atcoder.jp/contests/abc066/submissions/7944298

DAG

水色になるにはほしいライブラリ

有効グラフを扱うライブラリ

有向グラフ考えるときはとりあえずトポロジカルソートしたくなる

トポロジカルソート　O(N)
ループ判定　O(N)
最長経路　O(N)

#include <bits/stdc++.h>
using namespace std;

class DAG
{
    int n;
    vector<vector<int>> adj;
    vector<int> visited;
    vector<int> dp;
    void dfs(int v)
    {
        if (visited[v] == 2)
        {
            is_acyclic = false;
            return;
        }
        else if (!visited[v])
        {
            visited[v] = 2;
            for (int s : adj[v])
            {
                dfs(s);
            }
            visited[v] = 1;
            sorted.push_back(v);
        }
    }

public:
    vector<int> sorted;
    DAG(int n) : n(n), adj(n), visited(n), dp(n, 0) {}
    bool is_acyclic = true;
    int longest_path = 0;

    //add directed link node a to node b
    void add_arc(int a, int b)
    {
        assert(0 <= a && a < n && 0 <= b && b < n);
        adj[a].push_back(b);
    }

    void tsort()
    {
        for (int i = 0; i < n; i++)
        {
            if (!visited[i])
                dfs(i);
        }
        reverse(sorted.begin(), sorted.end());
    }
    void build()
    {
        for (auto i : sorted)
        {
            for (auto j : adj[i])
            {
                dp[j] = max(dp[j], dp[i] + 1);
                longest_path = max(longest_path, dp[j]);
            }
        }
    }
};

例題

https://atcoder.jp/contests/dp/tasks/dp_g

解答

https://atcoder.jp/contests/dp/submissions/8198624

例題

https://atcoder.jp/contests/abc139/tasks/abc139_e

解答

https://atcoder.jp/contests/abc139/submissions/8079830

セグメント木

青になるまでにあると便利なデータ構造

僕は使わなくても青になれたけど使えたらもっと楽だったなってことが多かった

ある１点の更新　O(log N)
区間[L,R)での最小値の取得　O(log N)
前処理　O(N)

最小値だけでなく最大値や和など大抵の計算は扱える非常に汎用性の高いデータ構造

#include <bits/stdc++.h>
using namespace std;
// 引用http://tsutaj.hatenablog.com/entry/2017/03/29/204841
int N, Q;
int const INF = INT_MAX;

struct SegmentTree
{
private:
    int n;
    vector<int> node;

public:
    SegmentTree(vector<int> v)
    {
        int sz = v.size();
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1, INF);
        for (int i = 0; i < sz; i++)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            node[i] = min(node[2 * i + 1], node[2 * i + 2]);
    }

    void update(int x, int val)
    {
        x += (n - 1);
        node[x] = val;
        while (x > 0)
        {
            x = (x - 1) / 2;
            node[x] = min(node[2 * x + 1], node[2 * x + 2]);
        }
    }

    int getmin(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        if (r <= a || b <= l)
            return INF;
        if (a <= l && r <= b)
            return node[k];

        int vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};

int main()
{
    cin >> N >> Q;
    SegmentTree seg(vector<int>(N, INF));
    for (int i = 0; i < Q; i++)
    {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0)
            seg.update(x, y);
        else
            cout << seg.getmin(x, y + 1) << endl;
    }
}

例題

https://atcoder.jp/contests/dp/tasks/dp_q

解答

https://atcoder.jp/contests/dp/submissions/8211793

遅延セグメント木

黄色になるまでに使えると便利なデータ構造

セグメント木の上位互換

区間[L, R)の更新　O(log N)
区間[L, R)での最小値の取得　O(log N)
前処理　O(N)

最小値だけでなく最大値や和など大抵の計算は扱える

セグメント木より実装が大変なので脳死で遅延セグメント木を貼るのは危険

#include <bits/stdc++.h>
using namespace std;

class LazySegTree
{
    int n;
    vector<long long int> node, lazy;

public:
    LazySegTree(vector<long long int> v)
    {
        int s = int(v.size());
        n = 1;
        while (n < s)
        {
            n <<= 1;
        }
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);

        for (int i = 0; i < s; i++)
        {
            node[i + n - 1] = v[i];
        }
        for (int i = n - 2; i >= 0; i--)
        {
            node[i] = node[i * 2 + 1] + node[i * 2 + 2];
        }
    }

    void eval(int k, int l, int r)
    {
        if (lazy[k])
        {
            node[k] += lazy[k];
            if (r - l > 1)
            {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }

            lazy[k] = 0;
        }
    }

    void add(int a, int b, long long int x, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
        {
            return;
        }
        if (a <= l && r <= b)
        {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else
        {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }

    long long int rangeSum(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
        {
            return 0;
        }
        if (a <= l && r <= b)
        {
            return node[k];
        }
        long long int vl = rangeSum(a, b, 2 * k + 1, l, (l + r) / 2);
        long long int vr = rangeSum(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }

    void set(int a, long long int x)
    {
        add(a, a + 1, -get(a));
        add(a, a + 1, x);
    }

    long long int get(int a)
    {
        return rangeSum(a, a + 1);
    }
};

int main()
{
    int n;
    cin >> n;
    vector<long long int> as(n);
    LazySegTree seg(as);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        char c;
        cin >> c;
        if (c == 'A')
        {
            int id, x;
            cin >> id >> x;
            seg.set(id - 1, x);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << seg.rangeSum(l - 1, r) << endl;
        }
    }
}

例題

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d

解答

https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8374973

2019-10-15

部内勉強会（３）

部内勉強会

第3回　動的計画法入門編（１）

動的計画法：全探索する際にそれぞれの計算で値を記録しておくことによって繰り返し計算をなくすことによって高速化する手法．

いろいろ典型テクニックがあるけど今回は初歩的なDPとDPの計算量の見積もりについて勉強します．

簡単な例題

Typical Stairs

漸化式を立てる

漸化式を立てることがDPの基本です．DPは一度計算した結果を記録するので初項から順に計算すれば，それぞれの項を１回の計算で求めることができます．
状態遷移を考える

漸化式を立てれたら状態遷移を式にしてみましょう

今回の問題の場合は

dp[i] = i段目まで登る場合の数

a[i] ：壊れていると0，使えるなら1

とすると

dp[i] = dp[i-1]*a[i-1]+dp[i-2]*a[i-2]

となります
初期状態を決めて実装する

後は初期状態が決まればすべての段について到達できる場合の数を求められます

今回はdp[0] = 1として配るDPをしてみましょう

配るDPとは？

けんちょんさんの記事が分かりやすいです

貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題

配るDPは既に結果が分かっている部分から遷移先を計算していく方式です．結果を配っていくイメージ

貰うDPとはまだ結果が分からない部分を全ての遷移元の情報から計算する方式です．結果をもらってくるイメージ

今回はもらうDPを使用とするとdp[1]を計算するときに範囲外参照をしてしまうので配るDPで書いてみましょう．

解答

DPの基礎はこれだけ！難しいのに手を出すと１回の勉強会で終わらない．．．

類題で練習しよう

Frog 1 ほぼ同じです

解答

Frog 2 遷移が増えました

解答

Strange Bank けんちょんさんの記事の例題です

解答

Vacation 遷移を考えましょう

解答

Grid 1 次元が上がってもやることは変わりません

解答

Digits Parade 問題は難しそうですがDPしてみると簡単に解けます

解答

長くなるので今日はここまで

次回は蟻本初級編のDPをやります

2019-10-03

部内勉強会（２）

部内勉強会

第２回　全探索とSTL

全探索

全てのアルゴリズムの基本

アルゴリズムは全探索と貪欲法に大きく分けることができて，全探索は必ず答えを出すことができる．貪欲法は答えを出せるかわからないので証明が必要．

今回はA~B問題レベルの全探索をやってみよう．

普通に解いてもいいけど全探索の方が楽

STLのコンテナクラス

vector

可変長配列、push_backが便利

  #include <bits/stdc++.h>
  using namespace std;
  int main()
  {
      int n = 100;
      vector<int> v(n, 0); //サイズn、全要素を0で初期化
      for (int i = 0; i < 100; i++)
      {
          v[i] = i;
      }
      v.push_back(10);                                //末尾に10を挿入
      cout << v.size() << endl;                       //要素数
      reverse(v.begin(), v.end());                    //逆順
      sort(v.begin(), v.end(), greater<int>());       // 降順ソート
      sort(v.begin(), v.end());                       //　昇順ソート
      auto low = lower_bound(v.begin(), v.end(), 20); //二分探索 値以上の最小値を探索
      cout << *low << endl;
      auto up = upper_bound(v.begin(), v.end(), 20); //二分探索　値より大きい最小値を探索
      cout << *up << endl;
  }

set

集合を管理する．中の実装は二分探索木

挿入，探索，削除がすべてO(log N)

unordered_setはO(１)だが，内部がソート済みにならないので嬉しくない

multisetは重複を許可する

  #include <bits/stdc++.h>
  using namespace std;
  int main()
  {
      set<int> s;
      s.insert(10);             //挿入
      s.erase(10);              //削除
      cout << s.size() << endl; //集合のサイズ
      for (int i = 0; i < 100; i++)
      {
          s.insert(i);
      }
      if (s.find(10) != s.end()) //値の探索　見つからないなら末尾を返す　
          cout << *s.find(10) << endl;
      auto low = s.lower_bound(30); //値の探索　引数以上の値の最小値へのポインタを返す
      cout << *low << endl;
      auto up = s.upper_bound(30); //値の探索　引数より大きい値の最小値へのポインタを返す
      cout << *up << endl;
      for (auto it : s) //拡張for文　内容を前から走査
      {
          cout << it << ' ';
      }
  }

map

辞書、中はpairの二分探索木、アクセスはO(log N)

pairがsetで管理されていると思うと良い

unordered_mapはハッシュで管理される

  #include <bits/stdc++.h>
  using namespace std;
  int main()
  {
      map<string, int> m; //キーがstring 値がint
      m["ghi"] = 3;       //値の挿入
      m["def"] = 2;
      m["abc"] = 1;
      cout << m["def"] << endl;
      for (auto it : m) //拡張for、中身はペア、キーの昇順
      {
          cout << it.first << ' ' << it.second << endl;
      }
  }

priority_queue

ヒープ，集合の最小値 or 最大値を得たいときに有効

挿入O(log N)，最小値(最大値)の参照O(１)，最小値(最大値)の削除O(log N)

  #include <bits/stdc++.h>
  using namespace std;
  int main()
  {
      priority_queue<int> que;                             //最大値から出るヒープ
      priority_queue<int, vector<int>, greater<int>> que2; //最小値から出るヒープ
      vector<int> v = {10, 5, 1, 7, 21, 13};
      for (auto it : v)
      {
          que.push(it); //挿入
          que2.push(it);
      }
      while (!que.empty()) //空かどうか判定
      {
          int x = que.top(); //参照
          que.pop(); //　削除
          cout << x << ' ';
      }
      cout << endl;
      while (!que2.empty())
      {
          int x = que2.top();
          que2.pop();
          cout << x << ' ';
      }
      cout << endl;
  }

pair

値のペア，ペアで値を管理したい時がある

３つ以上はタプルを使うか，自分で構造体を作る方が便利

  #include <bits/stdc++.h>
  using namespace std;
  typedef pair<int,int> P;
  int main(){
      P p = P(1,2);
      cout << p.first << ' ' << p.second << endl;
  }

例題

map

set