AtCoderのレートが緑色になった |

昨年からまったりと競技プログラミングに取り組んでいたのですが、やっとのことでAtCoderのレートが緑色になりました。

AtCoderは国内で唯一（？）オンラインコンテストを開催している企業で、同社が開催しているコンテストは気軽に誰でも参加することが出来ます。

1. やったこと

せっかくなので緑色になるまでにやったことについて書き下したいと思います。

問題はC++で解いています。

1.1. 過去問を解く

とにかくこれに限るようです。

atcoder_scores_20190811 — レート変動とRated Point Sum

このグラフは、AtCoder Scoresという有志の方が運営しているサイトで出力したもので、レートとRated Point Sum(今までに解いたAtCoderの問題の得点の総和)の推移を示しています。

私の場合、最初は気まぐれでコンテストに出るだけで過去問をあまり解いていなかったのですが、途中でレートが全然上がらないことに気付き（それはそう）、相応に過去問を解き始めました。

AtCoderの過去問を中心に解きましたが、AOJにある問題を解いたりもしました。

競技プログラミングの問題を提供するサイトはたくさんありますが、それぞれで問題の特徴に傾向があります。

AtCoderで緑になる程度を目標にするのであれば、とりあえずAtCoderの過去問を解いていればよさそうです。

過去問を埋める際はAtCoder Probremsというサイトがとても便利で、色々とお世話になっています。

atcoder_problems_20190811 — 過去問の一覧の表示や統計情報の閲覧が出来ます

1.2. 問題の傾向を整理する

競技プログラミングではデータ構造に関わるアルゴリズムの知識が問われることが主となります。

たとえば、ABC(AtCoder Beginner Contest)の過去問を最近開催された順にひたすら解いていくだけでもレートは上がるかと思いますが、上記のようなアルゴリズムの知識をつけるにはやや効率が悪そうです。

これに関して、最近は先人の方がアルゴリズムの観点から問題をまとめてくださっていることが多いので、それらを参考にしていきました。

私の場合、@drken1215さんの以下の記事がとても参考になりました。

AtCoder 版！蟻本 (初級編)

蟻本とは競技プログラミングの入門書（？）として有名な書籍で、私も先日Kindle版を購入しました（半額セールが行われていたので）。

AtCoderでは、問題の点数が300点を超えたあたりから、計算量を見積もる能力や効率の良いアルゴリズムの知見がないと基本的に解答が通らない気がします。

1.3. ライブラリを作る

競技プログラミングでライブラリと言うと、よく使うデータ構造やアルゴリズムなどを関数やクラス、コード片として用意したものを指します。

問題の傾向を整理する際にライブラリも作っておくと後々便利です。

ライブラリはエディタのスニペット機能を利用して簡単に呼び出せるようにしておくと良いかと思います。

私はEmacsを使用しているのですが、yasnippet.elを使えば簡単に呼び出せますね。

緑になるまでに以下のライブラリを作りました。

bit全探索
GCD
- 今後、AtCoderがC++17に対応すれば不要になります
LIS
グラフ
- Union-Find木
- 最大流（Dinic法）
- 最小全域木（Kruskal法）
- Warshall-Floyd
組み合わせ計算
- 階乗の事前計算等
素数周り
- エラトステネスのふるい
- 素因数分解
- 約数の個数・総和の導出

と、作りましたが、正直なところ、緑色になるにあたってはあまり活用する機会がなかったので必須ではないかもしれません。

ただ、理解が深まるのは間違いない上に自分でライブラリを作るのは楽しいのでおすすめです。

せっかくなのでお気に入りのUnion-Find木のライブラリを載せておきます（コンテスト中に使う機会が未だに来ないので悲しんでいます…）。

```
class UnionFind {
```
```
    using ll = long long;
```
```
public:
```
```
    struct Node {
```
```
        ll parent, weight, size, rank;
```
```
        Node(const ll& _parent = 0,
```
```
             const ll& _weight = 0,
```
```
             const ll& _size   = 1,
```
```
             const ll& _rank   = 0) :
```
```
            parent(_parent),
```
```
            weight(_weight),
```
```
            size(_size),
```
```
            rank(_rank) { }
```
```
    };
```
```
 
```

    explicit UnionFind(const ll& num_node) {

```
        node_.reserve(num_node);
```

        for(ll i = 0; i < num_node; i++) {

```
            node_.emplace_back(i);
```
```
        }
```
```
    }
```
```
 
```

    const std::vector<Node>& getNode() const {

```
        return node_;
```
```
    }
```
```
 
```
```
    ll searchAndZipRoot(const ll& x) {
```
```
        if(node_[x].parent == x) {
```
```
            return x;
```
```
        }
```
```
        else {
```

            node_[x].weight += node_[node_[x].parent].weight;

            return node_[x].parent = searchAndZipRoot(node_[x].parent);

```
        }
```
```
    }
```
```
 
```
```
    void unite(const ll& x,
```
```
               const ll& y,
```
```
               const ll& weight = 0) {
```
```
        auto rx = searchAndZipRoot(x);
```
```
        auto ry = searchAndZipRoot(y);
```
```
        if(rx != ry) {
```

            auto yw = weight + calcWeight(x) - calcWeight(y);

            if(node_[rx].rank < node_[ry].rank) {

```
                std::swap(rx, ry);
```
```
                yw *= -1;
```
```
            }
```
```
            node_[ry].parent  = rx;
```
```
            node_[ry].weight  = yw;
```

            node_[rx].size   += node_[ry].size;

            if(node_[rx].rank == node_[ry].rank) {

```
                node_[rx].rank++;
```
```
            }
```
```
        }
```
```
    }
```
```
 
```
```
    ll calcWeight(const ll& x) {
```
```
        searchAndZipRoot(x);
```
```
        return node_[x].weight;
```
```
    }
```
```
 
```
```
    ll calcDiff(const ll& x,
```
```
                const ll& y) {
```

        return std::abs(calcWeight(x) - calcWeight(y));

```
    }
```
```
 
```
```
    ll calcSize(const ll& x) {
```

        return node_[searchAndZipRoot(x)].size;

```
    }
```
```
 
```
```
    template<class... A>
```

    bool checkWhetherRootIsSame(const A&... nodes) {

        auto node_list = std::initializer_list<ll>{nodes...};

        if(node_list.size() < 2) return false;

        auto v = searchAndZipRoot(*node_list.begin());

        for(size_t i = 1; i < node_list.size(); i++) {

            if(v != searchAndZipRoot(*(node_list.begin() + i))) return false;

```
        }
```
```
        return true;
```
```
    }
```
```
 
```
```
private:
```
```
    std::vector<Node> node_;
```
```
};
```

Union-Find木とは、集合の統合・要素の属する集合の判定を高速に行うことが出来るデータ構造で、AtCoderでは400点〜問題あたりで想定解のアルゴリズムに使用されていたりします。

以下のスライドが分かりやすかったです。

Union find(素集合データ構造) from AtCoder Inc.

少し脱線してしましましたが、ライブラリを貼るだけで解ける問題も多数ありますので積極的に作っていけばよいと思います。

1.4. その他

オンサイトのコンテストに参加したり、バーチャルコンテストに参加したりもしました。

これに関しては、ろーるまん(@rollman054)が色々と導いてくれました。心から感謝です。

ろーるまん最高！一番好きなキシリトールガムアイコンのツイタラです！

2. 今後の抱負

競技プログラミングはAtCoderで緑色になったらもういいかなと思っていたのですが、問題を解くのは存外楽しく、また、ライブラリを作るのも楽しいのでもう少し続けたいと思います。

まったり水色を目指して頑張ります。