octoの勉強記録

普段の勉強について気が向いたら書きます

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

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

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

自己紹介

出身高専舞鶴高専

学科:電気情報工学

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

趣味:競技プログラミング、お菓子作り、ピアノ(初心者)

席次:1位

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

受験結果

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

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

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

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

志望動機

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

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

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

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

転機

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

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

受験勉強について

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

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

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

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

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

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

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

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

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

筑波大学

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

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

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

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

テストの出来

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

結果:合格

大阪大学

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

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

テストの出来

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

英語は7〜8割

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

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

面接は優しかった(どのサークル入りたい?とか)。

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

結果:合格

京都大学

阪大以降勉強をしない。

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

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

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

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

当日

物理と数学にやるだけが置かれていたのでやる(10割)

化学はわからないなりにできそうなところだけ解く(0.5割)

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

結果:合格

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

受験テクニック

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

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

解くテクニックについて

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

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

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

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

なぜ阪大?

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

    レベルが高い集団に入ることで圧倒的成長を得るパターンもあるけれど、僕は耐えられないと思うので京大は厳しいなと思いました。阪大なら僕のレベルでもそこそこ通用するっぽいので(あくまで競技プログラミングでは)阪大なら楽しみながらスキルアップできると思いました。

  • 旧帝大の教授はほぼ持ち回り、授業のレベルはそう大差ないらしい(出典:弊研究室教授)

    授業のレベルが同じならどちらでもいいかなというお気持ちになりませんか?

  • 京大は2年次編入、阪大は3年次編入 

    実質1年留年。阪大受かったとして1浪して京大行きますか?という問題に帰着出来てこれなら答えはわかりきっていると思います。

  • 内部生とうまく馴染めないらしい

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

以上です。

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

部内勉強会(4)

競プロライブラリ集

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

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

  1. Union Find Tree
  2. Combination
  3. DAG
  4. セグメント木
  5. 遅延セグメント木

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

セグメント木

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

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

  • ある1点の更新 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

部内勉強会(3)

第3回 動的計画法入門編(1)

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

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

簡単な例題

Typical Stairs

  1. 漸化式を立てる

    漸化式を立てることがDPの基本です.DPは一度計算した結果を記録するので初項から順に計算すれば,それぞれの項を1回の計算で求めることができます.

  2. 状態遷移を考える

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

    今回の問題の場合は

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

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

    とすると

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

    となります

  3. 初期状態を決めて実装する

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

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

    配るDPとは?

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

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

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

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

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

解答

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

類題で練習しよう

Frog 1 ほぼ同じです

解答

Frog 2 遷移が増えました

解答

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

解答

Vacation 遷移を考えましょう

解答

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

解答

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

解答

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

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

部内勉強会(2)

第2回 全探索とSTL

全探索

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

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

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

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

Takahashi Calendar

解答

Uneven Numbers

解答

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(1)だが,内部がソート済みにならないので嬉しくない

    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(1),最小値(最大値)の削除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

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

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

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

例題

vector

Divide the Problems

解答

Christmas Eve

解答

map

Double Helix

解答

Guidebook

解答

set

Second Sum(難問)

解答

priority_queue

Powerful Discount Tickets

解答

部内勉強会(1)

概要

競技プログラミング勉強会をしました

勉強会の目標は参加者が半年で緑になること.全員緑というのはそこそこレベルが高いので多分無理そう(?)

コンテスト参加回数を稼げないときついので、緑パフォ出せたらOKとします.

今回は第1回ということで各種コンテストサイトの紹介とAtCoderのアカウント作成,AtCoder Virtual Contestのアカウント作成を行い、実際にバーチャルコンテストをして参加者の能力を測定してみました.

40分7問でABCのA B B C C D E(は?)

もうちょっとレベル低めでもよかったかなと思います

各種コンテストサイトの紹介

日本語のものは

  • AtCoder

    毎週コンテストを開催している.日本最大手.講習会の問題は基本的にAtCoderから引用します.

  • yukicoder

    有志で運営されているコンテストサイト.問題数が多いので勉強する際に便利です.

  • AOJ

    同じく日本語のコンテストサイト.教育コンテンツが充実しているなぁという印象.大きなコンテストで使用されることもある

海外のものは

  • CodeForces

    世界最大手.競技時間が深夜なのでこどふぉに出ると生活が破綻する

  • TopCoder

    世界的に有名.過疎化が進んでいる.上位陣はほんとに強い

  • LeetCode

    企業のコーディング試験問題が無断転載されているサイト.違法.UIはきれい.面接対策に使われる.

などなど

各種サービスの紹介

  • AtCoder Scores

    自分のレートと勉強量を可視化できる.綺麗

  • AtCoder Virtual Contest

    コンテスト形式で練習ができる.今日の勉強会でもしようするのでアカウントを作ってください

  • AtCoder Ploblems

    AtCoderの過去問が整理されているサイト.それぞれの問題の難易度が分かるため、自分に合った問題を解くことができる.

これらの3つのサイトは勉強の際によく使うことになるのでブックマークすることをお勧めします

  • ACpredictor

    コンテストのパフォーマンスとレート変動を予測してくれます.コンテストに出る前に絶対入れましょう.

    proxyにはじかれるようです…

コンテストやってみよう

今回取り組む問題はこれ

Tenki

Kagami-mochi

Buffet

Otoshidama

GCD on Blackboard

Digits Parade

Hopscotch Addict

解説の時間もあるので40分でバチャります

なるべくDifficultyが単調増加になるように選びました

だいぶやりすぎた感がある

解説

Tenki

文字列を比較してあっている数をカウントします

簡単な問題はPythonで実装すると楽です

解答

Kagami-mochi

種類数を見てやりましょう

バケットを使って重複を消すかsetでかんりすると楽です.

解答

Buffet

Bは順番に関係なく得られるのであらかじめ足しておきます

Cを足すかどうか判定して足してあげればいいです

解答

Otoshidama

全探索することを考えます

愚直に実装するとO(N3)なので間に合いませんが最後のループは一意なのでO(N2)にできます

解答

GCD on Blackboard

GCDはユークリッド互除法で得られます.

GCDは順番に関係ないので双方から前計算しておくと求められます.

解答

Digits Parade

全探索するには間に合いません.全探索を効率的に行うためにDPをします

DP[i][j]=i桁目で余りがjとして計算していきましょう

解答

Hopscotch Addict

BFSをしてあげるとよさそうです

各頂点ごとに一回目で到達、二回目で到達、三回目で到達の状態があるので3*n頂点考えてBFSすると解けます.

解答