抽象化非再帰セグ木のシンプルな実装（C++）

この記事は

  • 非再帰セグ木、再帰セグ木よりもシンプルに書けるよ
  • 抽象化、怖くないよ

という記事です。セグ木の初歩についてはあまり触れていません。
ですので、まず最初に、私がセグ木の勉強をした際に大変参考になった記事・スライド・動画をご紹介します。まだセグ木に関して何も知らないという方は、それらで勉強してから改めてこの記事を読んでいただけると嬉しいです。

セグ木入門資料

  • ふるやんさんのセグメントツリー入門
    会話形式でするするっと頭に入ってきます。セグ木の初めの一歩におすすめです。 ただし、ノードのindexの振り方は本記事と異なり、また再帰による実装なので、本記事を読む際に混乱しないよう注意してください。

  • えびちゃんさんのスライド
    https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf
    非再帰セグ木について詳しく書かれています。図が綺麗で、とても分かりやすいです。私の本記事を読むに当たってはこのスライドの入門編までの理解で十分ですが、セグ木に慣れてきた頃に応用編を読むとより理解が深まります。

  • かつっぱさんの「Segment木ってなに〜？」シリーズ
    https://www.youtube.com/watch?v=LjhVy1ZJTMc
    百聞は一見に如かず派の人におすすめです。セグ木の種類から仕組み、実装まで丁寧に解説されています。 私はこの動画で、各種セグ木の違いについて初めて理解しました。

とりあえず非再帰セグ木のコードを見てみよう

onlinejudge.u-aizu.ac.jp
まずはRMQ（Range Minimum Query）を解きます。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct segment_tree {
    int n;
    vector<int> node;
    segment_tree(int n) : n(n), node(n<<1, INT_MAX) {}
    void set(int i, int x) {
        node[i += n] = x;
        while (i >>= 1) node[i] = min(node[i<<1|0], node[i<<1|1]);
    }
    int fold(int l, int r) {
        int res = INT_MAX;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = min(res, node[l++]);
            if (r & 1) res = min(node[--r], res);
        }
        return res;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    segment_tree seg(n);
    while (q--) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com) cout << seg.fold(x, y+1) << '\n';
        else seg.set(x, y);
    }
}

解けました。
セグ木部分についてはなんとたったの17行です。こんなにも簡単に書けちゃうんですね。

もう一つ解きましょう。次はこちら。
onlinejudge.u-aizu.ac.jp
RSQ（Range Sum Query）です。

#include <iostream>
#include <vector>

using namespace std;

struct segment_tree {
    int n;
    vector<int> node;
    segment_tree(int n) : n(n), node(n<<1, 0) {} // 初期値が0になりました
    // i番目の要素そのものにアクセスできる機能をつけました
    int operator[](int i) { return node[i + n]; } 
    void set(int i, int x) {
        node[i += n] = x;
        while (i >>= 1) node[i] = node[i<<1|0] + node[i<<1|1]; // 和になりました
    }
    int fold(int l, int r) {
        int res = 0; // 初期値が0になりました
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = res + node[l++]; // 和になりました
            if (r & 1) res = node[--r] + res; // 和になりました
        }
        return res;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    segment_tree seg(n);
    while (q--) {
        int com, x, y;
        cin >> com >> x >> y;
        x--;
        if (com) cout << seg.fold(x, y) << '\n';
        else seg.set(x, seg[x] + y); // 元々の値にyを足した値で更新します
    }
}

解けました。
（これはどうでもよいのですが、なぜRMQは0-indexedで、RSQは1-indexedなのでしょうか…）
RMQから変化した部分にコメントを付けましたが、全体的なコードの見た目はほとんど変わらないことが分かるかと思います。

抽象化しよう

ただ、クエリの種類に応じてセグ木の中身をちまちま書き換えるのは面倒ではありませんか？ そこで有用なのが「抽象化」です。

「抽象化」とは「具体性を捨て、共通の概念を抜き出すこと」だと私は理解しています。

上の2つの問題を例にとって、セグ木の抽象化について考えましょう。
RMQは「区間の最小値を求める」クエリ
RSQは「区間の和を求める」クエリでしたが、
「区間の〇〇を求める」という部分は共通しています。
まさにこの共通部分の抜き出しこそ、抽象化です。

それでは、

  1. 〇〇に相当する、区間の結合を行う演算
  2. minでいえば \infty （RMQのコードではINT_MAX）、加法でいえば 0 のような、
    他のどんな値とその演算を行っても、相手を変化させないような値（数学の言葉でいうと「単位元」というもの）

の2つをセグ木に渡してあげることで、「区間の〇〇を求める」ことができる汎用的な設計のセグ木へと進化させましょう。

上記の私なりの表現は、数学的な厳密性には欠けた記述ですので、数学的にどのような性質が成り立っているものならばセグ木に載るのかということに関しては、beetさんのブログをお読みください。
セグメント木について - beet's soil

また、演算の渡し方には以下のnoshi91さんのブログに書かれている通り様々な設計がありますが、今回は私の主観で一番理解しやすいと思われる、「A: std::function で関数オブジェクトを持つ」書き方で実装しました。ここは個人の趣味・趣向に応じて適宜改変してください。
代数的構造を乗せるデータ構造の設計について - noshi91のメモ

それでは、抽象化セグ木で、最初に解いたRMQを改めて解き直したコードがこちら。

#include <iostream>
#include <vector>
#include <climits>
#include <functional>

using namespace std;

template<typename T>
struct segment_tree {
    using F = function<T(T, T)>; // 型Tの値を2つ受け取って型Tの値を返すような関数型

    int n;
    vector<T> node;
    F combine; // 区間の結合を行う演算
    T identity; // 単位元

    segment_tree(int n, F combine, T identity)
        : n(n), node(n<<1, identity), combine(combine), identity(identity) {}

    T operator[](int i) { return node[i + n]; }

    void set(int i, T x) {
        node[i += n] = x;
        // combine関数により、2つの子ノードを結合した結果を親ノードに記録
        while (i >>= 1) node[i] = combine(node[i<<1|0], node[i<<1|1]); 

    }

    T fold(int l, int r) {
        T res = identity; // 初期値は単位元
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            // 区間内のものを左右から結合
            if (l & 1) res = combine(res, node[l++]); 
            if (r & 1) res = combine(node[--r], res);
        }
        return res;
    }
};


int main() {
    int n, q;
    cin >> n >> q;
    // ラムダ式でcombine関数を定義
    auto combine = [](int a, int b) { return min(a, b); };
    segment_tree<int> seg(n, combine, INT_MAX); // 要素数、演算、単位元をセグ木に渡す
    while (q--) {
        int com, x, y;
        cin >> com >> x >> y;
        if (com) cout << seg.fold(x, y+1) << '\n';
        else seg.set(x, y);
    }
}

RSQを解いたコードがこちら。
（セグ木部分は上と全く同じなので省略）

int main() {
    int n, q;
    cin >> n >> q;
    auto combine = [](int a, int b) { return a + b; }; // 変わったのはここと
    segment_tree<int> seg(n, combine, 0); // ここくらい
    while (q--) {
        int com, x, y;
        cin >> com >> x >> y;
        x--;
        if (com) cout << seg.fold(x, y) << '\n';
        else seg.set(x, seg[x] + y);
    }
}

抽象化をすることによって、演算が変わってもセグ木内部のコードを書き換える必要がなくなります。
抽象化、美しくありませんか？私は魅了されてしまいました。

まだセグ木の抽象化をしたことのない方、なんとなく敬遠されていた方が、
この記事を読んで「思っていたより簡単だな」と感じていただければ嬉しいです。

最後の抽象化非再帰セグ木をそのまま使用されてももちろん構わないのですが、私個人としては未完成なセグ木だと考えています。

読者への課題として

  • \Theta(N) でのセグ木の初期化
  • foldで可換則を要求しない
  • O(\log(N)) のセグ木上の二分探索を実装

などをあえて書かずに残しておきました。ぜひチャレンジしてみてくださいね。

区間に辺を張るテクの実装例（Dijkstra法セット）と使用例


このテクニックの私なりのC++での実装例です。ご参考までに。
何か改善点がありましたらお教えいただければ幸いです。

全体像

ノードのindexは以下の図のように持っています。0 と 2n は欠番になります。

f:id:Rorent:20200724165809p:plain:w400
ノードのindex（n=8のとき）

以下、コードです。非再帰セグ木を理解しておく必要があるかと思います。
（非再帰セグ木未履修の方はこちらのスライドがおすすめです。）

時間計算量
頂点数を N 、辺の追加回数を Q とする。
グラフの初期化：\Theta(N)
辺の追加：O(\log(N))
Dijkstra法：多重辺がない場合、 O\left({(N+Q\log(N)) \log(N)}\right)

#include <vector>
#include <queue>
#include <limits>

using namespace std;

template<typename W>
struct range_edge_graph {
    int n;
    struct edge { int to; W weight;};
    vector<vector<edge>> g;
    
    range_edge_graph(int n) : n(n) {
        g.resize(4*n);
        for (int i = 1; i < n; ++i) {
            int cl = i<<1|0, cr = i<<1|1;
            g[i].push_back({cl, 0});
            g[i].push_back({cr, 0});
            g[cl+2*n].push_back({i+2*n, 0});
            g[cr+2*n].push_back({i+2*n, 0});
        }
        for (int i = n; i < 2*n; ++i) g[i].push_back({i+2*n, 0});
    }

    // from [l1, r1) to [l2, r2)
    void add_edge(int l1, int r1, int l2, int r2, W w) {
        int idx = g.size();
        for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
            if (l1 & 1) g[l1+2*n].push_back({idx, 0}), l1++;
            if (r1 & 1) --r1, g[r1+2*n].push_back({idx, 0});
        }
        vector<edge> node;
        for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
            if (l2 & 1) node.push_back({l2++, w});
            if (r2 & 1) node.push_back({--r2, w});
        }
        g.push_back(node);
    }

    vector<W> dijkstra(int s) {
        s += n;
        vector<W> dist(g.size(), numeric_limits<W>::max());
        dist[s] = 0;
        using P = pair<W, int>;
        priority_queue<P, vector<P>, greater<P>> que;
        que.emplace(0, s);
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (dist[v] < p.first) continue;
            for (edge& e : g[v]) {
                if (dist[e.to] > dist[v] + e.weight) {
                    dist[e.to] = dist[v] + e.weight;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
        vector<W> res(dist.begin() + n, dist.begin() + 2*n);
        return res;
    }
};



コンストラクタについて

range_edge_graph(int n) : n(n) {

    // 1つのセグ木のサイズが2*n
    // 2つのセグ木をもつので4*n
    g.resize(4*n);

    // 辺を張る

    // まずは各セグ木内の辺から
    for (int i = 1; i < n; ++i) {

        // clは左の子の番号, crは右の子の番号
        int c1 = i<<1|0, c2 = i<<1|1;

        // 上のセグ木には根→葉方向に重み0の辺を張る
        g[i].push_back({cl, 0});
        g[i].push_back({cr, 0});

        // 下のセグ木には葉→根方向に重み0の辺を張る
        // 下のセグ木を操作したいときは +2*n すればよい
        g[cl+2*n].push_back({i+2*n, 0});
        g[cr+2*n].push_back({i+2*n, 0});
    }

    // 上のセグ木と下のセグ木の向かい合う葉同士に重み0の辺を張る
    for (int i = n; i < 2*n; ++i) g[i].push_back({i+2*n, 0});
}



区間に辺を張る部分について

// from [l1, r1) to [l2, r2)
void add_edge(int l1, int r1, int l2, int r2, W w) {

    // 下のセグ木から上のセグ木に向けて辺を持つノードを追加する

    // 追加するノードの番号
    int idx = g.size();

    // 下のセグ木の[l1, r1)に対応するノード → 追加するノード  に重み0の辺を張る
    for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
        if (l1 & 1) g[l1+2*n].push_back({idx, 0}), l1++;
        if (r1 & 1) --r1, g[r1+2*n].push_back({idx, 0});
    }
    
    // 追加するノードの隣接リスト 
    vector<edge> node;

    // 追加するノード → 上のセグ木の[l2, r2)に対応するノード  に重みwの辺を張る
    for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
        if (l2 & 1) node.push_back({l2++, w});
        if (r2 & 1) node.push_back({--r2, w});
    }

    // ノードを追加
    g.push_back(node);
}



使用例

※以下、解法のネタバレを含みます。

例1

第二回全国統一プログラミング王決定戦予選 D - Shortest Path on a Line
atcoder.jp

問題概要

N 頂点からなる無向グラフがあり、存在する辺の情報が M 個、以下の形式で与えられる。

  • 1 以上 N 以下の整数 L_i, R_i 及び正整数 C_i について、 L_i\leq s \lt t \leq R_i を満たすすべての整数の組 (s, t) に対し、頂点 s と頂点 t の間に長さ C_i の辺が存在する。

このグラフ上で、頂点 1 から頂点 N までの最短路の長さを求めよ。

解法

与えられる辺の情報をわかりやすく言い換えると、区間 [L_i, R_i+1) 内であればどの頂点間もコスト C_i で移動できるということになりますね。
よって、上記のライブラリを用いて、区間 [L_i, R_i+1) から区間 [L_i, R_i+1) に重み C_i の辺を張ってDijkstra法で最小コストを求めればおしまいです。このテクさえ知っていれば、何も考えずにできます。
（実はもっと賢い解法があるのですが、それに関しては解説PDFをご参照ください。）

私の提出コードです。
atcoder.jp

例2

Codeforces Round #406 (Div. 1) B. Legacy
codeforces.com

問題概要

n 頂点からなる有向グラフがあり、存在する辺の情報が q 個、以下の3つの形式で与えられる。

  1. 頂点 v_i から頂点 u_i を結ぶ、重み w_i の辺
  2. 頂点 v_i から区間 [l_i, r_i] のすべての頂点を結ぶ、重み w_i の辺
  3. 区間 [l_i, r_i] のすべての頂点から頂点 v_i を結ぶ、重み w_i の辺

このグラフ上で、頂点 s から各頂点への最小コストを求めよ。

解法

  1. 頂点 v_i から頂点 u_i　→　区間 [v_i, v_i+1) から区間 [u_i, u_i+1)
  2. 頂点 v_i から区間 [l_i, r_i]　→　区間 [v_i, v_i+1) から区間 [l_i, r_i+1)
  3. 区間 [l_i, r_i] から頂点 v_i　→　区間 [l_i, r_i+1) から区間 [v_i, v_i+1)

と言い換えてしまえば、おしまいです。

私の提出コードです。
codeforces.com

他にこのテクが使えそうな問題を随時募集しています。

追記（2020/08/23）

beetさん(@beet_aizu)より、上下のセグ木の葉をくっつけてしまえばセグ木部分を 3n にできるというアイデアをいただきました。ありがとうございます。

range_edge_graph(int n) : n(n) {
    g.resize(3*n);
    for (int i = 1; i < n; ++i) {
        int cl = i<<1|0, cr = i<<1|1;
        add_edge(i, cl, 0);
        add_edge(i, cr, 0);
        add_edge(cl+2*n, i+2*n, 0);
        add_edge(cr+2*n, i+2*n, 0);
    }
}

// map [3n, 4n) -> [n, 2n)
void add_edge(int u, int v, W w) {
    if (3*n <= u) u -= 2*n;
    g[u].push_back({v, w});
}

// from [l1, r1) to [l2, r2)
void add_edge(int l1, int r1, int l2, int r2, W w) {
    int idx = g.size();
    for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
        if (l1 & 1) add_edge(l1+2*n, idx, 0), l1++;
        if (r1 & 1) --r1, add_edge(r1+2*n, idx, 0);
    }
    vector<edge> node;
    for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
        if (l2 & 1) node.push_back({l2++, w});
        if (r2 & 1) node.push_back({--r2, w});
    }
    g.push_back(node);
}

PythonでTwitterのプロフィールを自動更新

AtCoderとCodeforcesのユーザー名を入力するだけでTwitterのプロフィールを更新できるスクリプトの作り方についての記事です。
例えばこんなことが簡単にできるようになります。

1. 現在のRatingを取得

import re

import requests
from bs4 import BeautifulSoup

ac_username = input('AtCoder username : ')
ac_url = 'https://atcoder.jp/users/' + ac_username
ac_response = requests.get(ac_url)
ac_soup = BeautifulSoup(ac_response.text, 'lxml')
ac_rating = int(ac_soup.select('table.dl-table')[1].span.get_text())

cf_username = input('Codeforces username : ')
cf_url = 'https://codeforces.com/profile/' + cf_username
cf_response = requests.get(cf_url)
cf_soup = BeautifulSoup(cf_response.text, 'lxml')
cf_rating = int(cf_soup.find_all('span', class_=re.compile('^user'))[1].get_text())

RequestsでHTMLを取得、BeautifulSoupでパースして、現在のRatingを抜き出します。
Ratingを抜き出す部分のコードは、ブラウザの開発モード等でHTMLとにらめっこしながら、Pythonのinteractive modeで実験しつつ、いい感じに抜き出せるように頑張ります。
（ちなみに私はスクレイピング超初心者なので、これがいい感じなのかよく分かりませんが、とりあえず取ってこれたのでヨシ！です。）

2. AtCoderのRatingグラフの画像を取得

import time

from selenium import webdriver
from selenium.webdriver.chrome.options import Options

options = Options()
options.add_argument('--headless')
driver = webdriver.Chrome(options=options)
driver.get(ac_url)
driver.set_window_size(1920, 1080) # 気分でFull HD sizeにしました
time.sleep(3)
img_png = driver.get_screenshot_as_png()
driver.quit()

このパート、割と難儀でした。
JPEGやPNGなどの画像ファイルならBeautiful Soupを使って簡単にダウンロードできるのですが、AtCoderのRatingグラフはJavaScriptで描画されているようなので一筋縄ではいきません。 そこで、SeleniumでAtCoderのUserページにアクセスしてスクリーンショットを撮影する方針にしました。

まずheadless mode（ブラウザを陽に表示しないモード）でdriverを開きます。headless modeでないと、スクリーンショットのサイズが使っているディスプレイの解像度等に影響を受けてしまうそうです。
（この際PATHの通っているところに、開くブラウザのdriverをダウンロードしておく必要があります。詳しくはここを参照してください。）

あとはAtCoderのUserページにアクセスして、画面サイズを調節した上でスクリーンショットを撮ります。撮影前にtime.sleep(3)をしているのは、読み込みが完了していない状態で撮影をしてしまい失敗したことがあったためです。劣悪なネット環境のせいかも。

ここまでで、このような画像が取得できました。 f:id:Rorent:20200611134153p:plain

3. 画像を加工

import io

from PIL import Image

dir_name = '----------' # 適当に設定してください

gray = (217, 217, 217)
brown = (218, 198, 182)
green = (190, 217, 185)
cyan = (196, 236, 237)
blue = (177, 188, 255)
yellow = (237, 236, 187)
orange = (255, 218, 186)
red = (255, 187, 186)
color = { 0:gray, 1:brown, 2:green, 3:cyan, 4:blue, 5:yellow, 6:orange, 7:red }

color_id = min(ac_rating // 400, 7)

img_io = io.BytesIO(img_png)
img = Image.open(img_io)
cropped_img = img.crop((1400, 600, 2700, 1500))
header_img = Image.new(header_img.mode, (2700, 900), color[color_id])
header_img.paste(cropped_img, (700, 0))
header_img.save(dir_name + 'rating_graph.png')

Twitterのヘッダ画像サイズが1500×500なので、その比に合わせて切り貼りします。
横に引き伸ばしてみたらあまり見た目がよくなかったので、左右の余白部分を今のRatingの色で塗りつぶすことにしました。

Rating色のRGB値はこのサイトで手動で抽出しました。（ここはもっと賢く取得できる気がします。）

既に取得したuserページのスクリーンショットをPillowに渡して、img.crop((left, upper, right, lower))でうまくRatingグラフの部分を切り取ります。試行錯誤の末、上記の値でうまくいきました。 横が1300px、縦が900pxなので、比を3:1に合わせるため両サイドに幅700pxの余白を取ると考えて、横が700 + 1300 + 700 = 2700px、縦が900pxでRatingの色のベタ塗り画像を作り、その上に先程切り取った画像をペタっと貼り付けます。

完成した画像はこちら。上の画像だと左右の余白がありすぎるように見えますが、TweetDeckで見るとこのくらいがちょうど良さそうです。

f:id:Rorent:20200611134611p:plain f:id:Rorent:20200611134712p:plain

右に若干寄っているのが気になる？いえ、知らない子ですね。
（数値的には合っていそうなのに何故ずれるのか、私も疑問です…。もし分かったら教えて下さい。）

4. Twitter APIでプロフィールを更新

import twitter

# API keys
CK = '----------'
CS = '----------'
AT = '----------'
AS = '----------'

api = twitter.Api(CK, CS, AT, AS)
api.UpdateBanner(dir_name + 'rating_graph.png')
description = 'B5/AtCoder({})/Codeforces({})/第3回PAST70点中級\n{}\n{}'.format(ac_rating, cf_rating, ac_url, cf_url)
api.UpdateProfile(description=description)

ここまできたら、あとは更新するだけです。 Twitter API申請がお済みでない方は、解説記事が無数に転がっていますのでそれらを読んで頑張ってください。簡単な英作文課題を解くだけです。
初めはtweepyというライブラリを使ってプロフィールを更新しようと試みたのですが、どうもAPI.update_profile_background_image(filename)という関数がうまく動きませんでした。色々調べましたが原因不明でしたので、python-twitterという別のライブラリを使うことで、無事その問題を間接的に解決することができました。

ソースコード全体

import io
import re
import time

import requests
import twitter
from bs4 import BeautifulSoup
from PIL import Image
from selenium import webdriver
from selenium.webdriver.chrome.options import Options

# 画像を保存するdirectoryを指定
dir_name = '----------' 

ac_username = input('AtCoder username : ')
ac_url = 'https://atcoder.jp/users/' + ac_username
ac_response = requests.get(ac_url)
ac_soup = BeautifulSoup(ac_response.text, 'lxml')
ac_rating = int(ac_soup.select('table.dl-table')[1].span.get_text())

cf_username = input('Codeforces username : ')
cf_url = 'https://codeforces.com/profile/' + cf_username
cf_response = requests.get(cf_url)
cf_soup = BeautifulSoup(cf_response.text, 'lxml')
cf_rating = int(cf_soup.find_all('span', class_=re.compile('^user'))[1].get_text())
 
options = Options()
options.add_argument('--headless')
driver = webdriver.Chrome(options=options)
driver.get(ac_url)
driver.set_window_size(1920, 1080)
time.sleep(3)
img_png = driver.get_screenshot_as_png()
driver.quit()

gray = (217, 217, 217)
brown = (218, 198, 182)
green = (190, 217, 185)
cyan = (196, 236, 237)
blue = (177, 188, 255)
yellow = (237, 236, 187)
orange = (255, 218, 186)
red = (255, 187, 186)
color = { 0:gray, 1:brown, 2:green, 3:cyan, 4:blue, 5:yellow, 6:orange, 7:red }

color_id = min(ac_rating // 400, 7)

img_io = io.BytesIO(img_png)
img = Image.open(img_io)
cropped_img = img.crop((1400, 600, 2700, 1500))
header_img = Image.new(cropped_img.mode, (2700, 900), color[color_id])
header_img.paste(cropped_img, (700, 0))
header_img.save(dir_name + 'rating_graph.png')

# Twitter API keys
CK = '----------'
CS = '----------'
AT = '----------'
AS = '----------'

api = twitter.Api(CK, CS, AT, AS)
api.UpdateBanner(dir_name + 'rating_graph.png')

# 以下は適宜変更してください
description = 'B5/AtCoder({})/Codeforces({})/第3回PAST70点中級\n{}\n{}'.format(ac_rating, cf_rating, ac_url, cf_url) 
api.UpdateProfile(description=description)

【色変】全完黄パフォで入水しました！

一昨日5/3(日)のABC166で初の全完を果たし、さらに黄パフォで入水いたしました！

f:id:Rorent:20200504165346p:plain

そこで、他の競プロerもすなる色変記事というものを、私もしてみむとてするなり、です。

ただし、読んでいただく前に一つ注意書きを。
この色変記事を書くにあたって、十数人の方の色変記事を読ませていただいたのですが、
そうして思ったのは「精進の仕方は十人十色」だということです。
ですので、以下に書かれている内容は、「おすすめの精進法」ではなく、あくまでも「精進の仕方の一つ」として読んでいただければ幸いです。

私自身のことに関しては、前回の記事で書きましたので、もしご興味のある方はそちらも読んでいただけると嬉しいです。

各種精進データ

入水した現在の精進の状況については以下の通りです。

f:id:Rorent:20200504172510p:plain f:id:Rorent:20200504172526p:plain f:id:Rorent:20200504172558p:plain f:id:Rorent:20200504172625p:plain f:id:Rorent:20200505141705p:plain f:id:Rorent:20200504172651p:plain

入水までに勉強したアルゴリズム

はい、色変記事あるあるです。
書き漏れがないようにプログラミングコンテストチャレンジブック（通称：蟻本）やAtCoder Tagsのカテゴリ分類を眺めながら、自分の知っているかつ使えるアルゴリズムを全列挙しておきます。
そしてそれらを、水色になるために重要そう（Lorent調べ）な順に並べ直したいと思います。
また、自分がそのアルゴリズムを初めて勉強したときに読んだ記事、見た動画の中で特にわかりやすかったもののリンクを貼っておきます。

☆☆☆：入緑でも確実に必要になるはず
☆☆★：まあまあよく使う
☆★★：数回使ったことがある
★★★：コンテストではまだ一度も使ったことがない

前提として

☆☆☆：入緑でも確実に必要になるはず

☆☆★：まあまあよく使う

☆★★：数回使ったことがある

  • Warshall-Floyd法

    • 全点対最短路問題を解くアルゴリズム。つまり任意の点から任意の点までの最短路を求めることができる。ただし計算量はO(|V|^3)（Vは頂点集合）。
    • 実装がめちゃくちゃ軽いので、計算量が間に合うなら、他のアルゴリズム使うべきであろうときもこれで済ませてしまうことも。
    • 蟻本2-5

  • Bellman-Ford法

    • 負辺があるときの単一始点最短路問題に使える。負閉路の検出にも使える。実装もまあまあシンプル。
    • Bellman-Ford法の解説 - Qiita

  • 桁DP

    • 未満フラグという状態変数を理解することが重要。
    • 「未満フラグが立っている」＝「どんな数字を選んでもよい」
    • xorの問題でもよく使われる。
    • まだサクサクとは書けない。
    • Digit DP 入門 - torus711 のアレ

  • Fenwick Tree（BIT）

    • 区間和を高速に計算できる、かつ、ある要素にある数字を加えていくことができる。
    • 今のところSegment Treeの軽量版、累積和の強いやつみたいなイメージ。あっているかは不明。
    • ABC136Fの解説放送
    • 蟻本3-3

  • bitDP

    • 例題として、巡回セールスマン問題という有名問題が用いられることが多い。
    • 状態集合を添字として持つDP（定義は人によって曖昧らしい）。
    • 蟻本3-4

  • 三分探索

    • 連続関数の極値を求める手法。二分でダメなら三分すればいいじゃない。
    • 通称「さぶたん」（嘘です、聞いたことありません）。
    • 三分探索 - 忘れても大丈夫

★★★：コンテストではまだ一度も使ったことがない

精進の内容

これは私の精進グラフです。

f:id:Rorent:20200504172110p:plain

不思議なグラフの形ですね。経緯が気になる方は自己紹介記事をどうぞ。

以下、2020年3月から入水するまでに行った精進の内容についてです。

  • APG4b3章まで + 4.04.イテレータ

    • 以前は主にPythonで書いていたのですが、3月からC++を勉強し始めました。競プロをやるためにC++を学びたいなら間違いなく最適な教材です。

  • 蟻本の購入

    • 全競プロerが購入すべきだと思います。個人的には前から順に読むものではないと思っていて（DPあたりで心が折れる）、自分のレート帯の問題を解いている際に解説で知らないアルゴリズムが出てき始めたら、蟻本の対応するページを開いて読むとよいです。
    • 一度読んで全く理解できなかったところも、あとから読むとなぜかスッと理解できることがあります。不思議すぎて、書き換えられたのではないかと思うくらいです。

  • AtCoderProblemsのBootCamp全埋め

    • ものすごく力になりました。ひたすら全探索をする問題が多かったです。これを通して「まず全探索を考えてみる」という発想が自然と身についたように感じます。

  • あさかつ、よるかつに毎日参加する

    • AtCoderProblemsで、有志の方が毎日（よるかつはAtCoderのコンテストがない日以外で）企画してくださっているVirtual Contest。
    • Twitterで交流している他の競プロerさんと競い合えて、よい刺激を受けます。

  • けんちょんさんの蟻本記事

    • これは手元に蟻本あってこその記事です。私は蟻本を買う前にこの記事を読んだとき、挙げられているキーワードをヒントに以下の問題を解け、という記事だと勘違いしておりました。
    • そもそも蟻本が前から難易度順に並んでいるかと言われると、そうではないような気がするので、この記事もきっと、前から順に解いていくといったことはしない方がよいと思われます。私はそうして心が折れました。
    • 蟻本を勉強した際に、そのアルゴリズムについて理解を深めたいとき、この記事ほど有用なものはありません。

  • E869120さんの精選100問

    • 水色コーダーになるために解くべき100問をまとめてくださっています。
    • 7割くらい埋めました。個人的にはナップサックDP以外のDP、最小全域木、その他のテクニックあたりは余裕のある方が手をつければよいと思います。私はやれていません。

  • AtCoderProblems Recommendation Medium

    • 私の最近の精進のメインコンテンツです。自分のレート帯なら約50%の確率で解けると推定された問題が表示されます。素晴らしい機能です。
    • 疲れたときはEasyを進めます。Hardは無謀です。

精進のTips

解説ACは悪ではない

解説ACとは、分からなかった問題の解説を読んでからACすることを指します。

「解説ACをできる限りしたくない。解けないのはまだ私の実力が足りていないからだ。」
→気持ちは大変分かります。私もその一人でした。しかし一度見た問題をわからないままにしておくことの方が私にとっては気持ち悪いのです。その問題を解説ACしておくことで実力を高めましょう。

「わからない問題があったら解説を見て理解し、次に出会ったときに解けるようにしておく」
→それができたら一番よいと思います。解説ACしてしまった問題は区別できませんもんね…。ただ、解説を読んで理解しただけで、今後その問題と再び出会った時にACを取れる実装ができるでしょうか。少なくとも私にはできません。せっかく解説を読んで理解したならば、その流れで実装までしてしまった方がお得ではありませんか。

私の実践方法についてです。

青diffまでの問題は、一目見てしまったら、何が何でもACを取っておくようにしています。なぜ青diffまでと決めているかといいますと、自分の理解度的に、それ以上のdiffの問題は解説を読んでも理解し難く感じたのと、継続的にあさかつやよるかつに参加していれば、解説ACをした問題とも再び出会える可能性が高いからです。最近は復習キューをToDoアプリで管理するようにしています。

また、解説ACをする際に、写経は絶対にしません。初めから終わりまで自分で書いたコードでACできるようになることを重視しています。解説を読んで十分に理解したと思っても、実際にコードを書き始めると、意外と書けないという経験はありませんか？自分で書けない部分＝理解し切れていない部分なので、改めてその部分の解説を重点的に、しっかり理解できるまで読みましょう。写経しないと分からない問題が多く感じたら、解説ACの閾値diffを下げればよいかと思います。

解けた問題の復習もしっかり行う

解けた問題についても、解説pdfや解説放送、また他の競プロerさんが書かれている解説ブログを見たりして、実装上より簡潔に書けそうなテクニック等を探すということを意識して行っています。

また、自分の解き方とは異なる解法があれば、それも理解して書けるようにしています。一つの問題を多面的に見る力を養うことで、考察力も上がります。

考察パートと実装パートはしっかり分ける

ある程度難しい問題になってくると、曖昧な考察のままコードを書き始めたところで、うまくいくことは少ないです。 手元に紙とペンを用意して、しっかりと考察しましょう。
考察で行き詰まった時は、

  • 小さいケースでシミュレーションして特徴を捉える

  • 全探索をすることを考えたときに、どの部分で計算量が落とせそうかを考える

とうまくいく場合が多いかと思います。
また、最後にコーナーケースが通るかは確認しておくようにしましょう。

そしてどう実装するかというイメージが固まってきた段階で、やっと実装パートに入るようにしています。きちんと考察できていれば、実装にはそれほど時間はかかりません。

考察が詰め切れていないまま実装し始めると、最悪の場合、実装途中に方針そのものが間違っていることに気付き、全部書き直しになってしまうということにもなりかねません。

Twitterを始めよう

もしこの記事を読まれている競プロerさんで、Twitterをされていない方がいたら、すぐにでも始めましょう。

多くの競プロerはTwitterをしています。特にコンテスト前後のタイムラインはとてつもない流速です。競プロ界隈で話題となったワードがトレンド入りすることもしばしばあります。 また、AtCoder公式情報もTwitterが最速です。

Twitterをしていると、同レート帯の競プロerがどういう精進をしているのか、その日のコンテストに出た問題の多種多様な解法、実装のちょっとしたテクニック、など競プロに関する様々な情報が自然と得られます。
わからないことをTwitterに投げると大抵優しい競プロerさんが丁寧に教えてくださります。
競プロタイムラインは温かいです。

「あなたがTwitterをしている間にライバルは競技プログラミングの問題を解いています。」 と言われて焦ってしまうこともあるとは思いますが、私はTwitterも精進の一貫と考えます。

おわりに

この色変記事で、多くの競プロerさんにとって少しでも役に立つ情報をお伝えできれば幸いです。
最後までお読みいただきありがとうございました。
これからもぜひお互いに切磋琢磨していきましょう。

【初投稿】自己紹介です。

初めまして、Lorentと申します。
今日から、主に競技プログラミングに関するブログを始めようと思いますので、
まずは自分を知ってもらうことから、と思い、この記事を執筆いたしました。
ブログを書くこと自体初めてなので、稚拙な文章ですが、最後まで読んでいただけると嬉しいです。

自己紹介

私は22歳の大学5年で、医学を専攻しています。

趣味は料理・お菓子作り、楽器演奏、ルービックキューブです。
あとはなんといっても競技プログラミングです。

料理・お菓子作りは、「産物が美味しく食べられる化学実験のようなもの」という感覚で楽しんでいます。
火加減、分量等、忠実にレシピに従って作るので、私の料理が美味しくなかったときは全てレシピの責任です。 （はい！？）

楽器演奏についてですが、ピアノ🎹を弾いたりサックス🎷を吹いたりします。
ピアノは小2から中3まで習っていて、サックスは中高と吹奏楽部で吹いていました。
どちらも決してうまくはありませんが、気の向くままに演奏して楽しめればいいのです。
趣味でやる音楽とはそういうものです。

ルービックキューブは小4の頃からハマったり冷めたりを1000000007回ほど繰り返しています。（ちなみに現在、冷め期です。）
20秒台ほどで揃えられますが、これは界隈の人からしたらとても遅いです。
世界記録を知っていますか？私は知っています。3.47秒です。
目隠しでも揃えられます。ただ、これもとても遅く、暗記スタートから揃え終わるまで5分ほどかかります。目隠しの世界記録は18.32秒とのことです。頭おかしいですね。

さて、ここまで長くなってしまいましたが、競プロ系ブログですので、ここからは私とプログラミングについて書きたいと思います。

プログラミングとの出会いから今まで

高校時代

初めてプログラミングという世界と触れ合ったのは、高校生の頃です。

高校生の頃、学校と部活以外の時間はほとんど地元の図書館で勉強していたのですが（『青春』？私の知らない単語ですね。）、毎日通っていると、座席のポジションが大体定まってくるのです。そこで私のポジションに最も近い本棚に並んでいたのが、プログラミング関連の本でした。
勉強で疲れた時に、ふと目についた『やさしいJava』（今思うと、『やさし』くはなかった）を手にとって読んでみると、そこには私の知らない世界が広がっていました。大変興味深く、わくわくした覚えがあります。
しかし、私はそこで思いました。「ここでプログラミングをし始めたらのめり込んでしまい、勉強が疎かになってしまうのではないか……」と。医者になるために必死に受験勉強をしていたので、その時点でプログラミングをし始めることを諦めました。今思えば、私にとってこれは英断でした。

大学生になって

無事大学に合格してからは、音楽系のサークルに入って夜遅くまで活動したり、毎週レポートに追われたり、家庭教師のバイトを始めたり、自動車学校に通ったりと、まあまあ忙しい毎日を送っていたため、高校生の頃抱いたプログラミングへの興味は忘れかけていました。

転機は大学2年の春休みでした。

大学生の長期休みって、本当に長いんですね。1月下旬〜2月上旬に試験や最終レポートの提出を終えると、課題も何もない状態で4月の2週目あたりまで完全にフリーです。私の場合、サークル活動と家庭教師バイトが定期的にあったものの、それ以外は大変暇で怠惰な生活を送っておりました。

私は無駄な時間を過ごすことほど嫌いなものはありません。忙しいときは忙しいときでしんどく思うときもあるのですが、忙しいこと（やりたいことがあること）ほど幸せなことはないとつくづく思います。 理不尽な忙しさに関してはあまり経験したことがないのでなんとも言えませんが…。

なので、怠惰な春休み生活に耐えられず、「何か始めなければ……堕落してしまう……！」というある種の強迫観念に駆られ、何かやりたいことはなかったか、と考えました。
そこでふと思い出したのが、高校生の頃に抱いたプログラミングへの興味です。 大学生になってから、my new gear…（MacBook）も手に入れたことですし、これはもうやり始めるしかありません。

初めて実際に書いてみたプログラミング言語は、Swiftです。

SwiftはApple社が2014年に作った言語であり、iOSやmacOS上で動くアプリの開発などに特に優れた言語です。ちょうどMacBookを使っていることもあり、簡単なアプリの開発を目標にSwiftを勉強してみようと思いました。
（はい、「プログラミング言語を始めるなら『Swift』」 「『Swift』を学ぶべき3つの理由」 「今、『Swift』が熱い！」みたいな記事に踊らされていました。）

ただ、勉強して文法的なところは理解できたものの、実際のアプリ開発となると、プログラミングの本質的な面白さというよりはGUIの細かな調整などが多く、これは私の勉強したかったことじゃないな…と感じてしまいました。

そこで次に出会った言語はRubyです。

Swiftに飽きてしまったので、例の地元の図書館に行き懐かしのポジションあたりで改めてプログラミング本を漁っていた際に、気になる本を見つけました。それが『Rubyで数独（AIプログラミング入門）』 という本です。著者の佐藤理史先生が、私の所属する大学の工学部にある、自然言語処理を専門とする研究室の教授であったことから興味が湧きました。

競プロを嗜まれる皆さんでしたら、「数独なんて再帰で余裕www」と思われるかもしれません。しかしこの本のすごいところは、「数独はもちろん再帰で一瞬で解けてしまうのだが、できる限り人間が数独を解くときの思考をプログラムに落としてみよう」というスタンスで書かれているところです。最終的には、どういった根拠の元に、どういった順序で空きマスが埋まっていくのか、まで出力してくれる数独ソルバーが完成します。これは再帰で解いたら決してできないことですね。

Rubyの文法を前提知識として求められる本ではあったのですが、その本を読み切りたい一心で、Rubyの入門本と一緒に、プログラムを理解しつつ写経しながら読み進めました。この本のおかげでアルゴリズムの面白さに目覚めたといっても過言ではありません。名著です。自信を持ってお勧めできます。

競プロとの出会い、そして別れ

そこから競技プログラミングに出会うまでに、時間はかかりませんでした。アルゴリズムを楽しく学べるサイトとしてAtCoderが紹介されていたのをブログ記事か何かで読んだのだと思います。
ここでめでたい私の初ACのリンクを貼っておきます。

atcoder.jp

この時期は今よりも確実にRatingが上がりやすく、アルゴリズムの知識は何もありませんでしたが、adhocに問題を解くだけでグングン伸びてあっという間に緑色になれました。
このグラフの2018年3月〜5月あたりの話です。

f:id:Rorent:20200504155947p:plain

（この時期からコツコツと続けていたら今は何色になれているのだろうか…。）

また、どうやら競プロerはC++で書くことが多く、私の書いていたRubyで競プロについて解説されている記事は大変少なかったので、勉強はしにくく感じました。 そこで、次点で人気のあったPythonに目をつけました。Rubyと文法が似ている部分も多く、スッと身に付けることができました。

ただ、そんなこんなしているうちに大学が再開します。忙しい毎日が戻ってきてしまいました。上述の通り、それはそれで幸せなことなのですが、競プロからは2年ほど離れていました。
その間もプログラミングは細々と続けており、興味から『Pythonではじめる機械学習』や『ゼロから作るDeep Learning』、『作って動かすALife』などを写経しながら読み進めたりしていました。
また、私の学部に医療系データを解析する研究室があり、大学3年の後期に半年間ほど通い勉強させていただいたりもしました。（このとき、Rの勉強もしました。）

競プロとの復縁

最近になり改めて競技プログラミングに興味を持つきっかけとなったのは、サークルの後輩である情報学部の子も、競技プログラミングをやっているということを知ったことです。
新型コロナウイルス感染拡大の影響により、人と会うことも憚られ、臨床実習も行えない今、自宅で何をして過ごそうかと考えている真っ最中であったので、2020年3月、とりあえず競プロを再開してみることにしました。

以前から「PythonはC++より遅くて不利だ」と言われていることは知っていましたし、できればC++で書きたい思いはありましたが、言語を変えたその移行期間中に、実力以外の問題でRatingが落ちてしまうことを危惧していました。
しかし、これだけ期間が空いてしまえば、移行期間も何も関係ないではありませんか！
しかも、APG4bという競プロのためのC++入門記事も、AtCoder公式から出されているではありませんか！
というわけで、C++の勉強をしつつ、それと並行して競プロに必要なアルゴリズムの勉強も始めました。

再開してみると、2年前に理解できなかったことも、いつの間にかなんとなく理解できるようになっていることに気付きました。機械学習やDeep Learningの勉強をしている際に、疑似コードなどをたくさん読んで考えたりしたので、そのおかげかもしれません。

私の精進の仕方については、色変ブログで書きます。

今や、競プロにハマりにハマっています。朝起きたらまずあさかつ（リアタイで参加はほとんどできていません）、次に復習キューの消化、新しいアルゴリズムの勉強、Twitterで交流のある人がバチャしていたらふらっとお邪魔する、コンテストのない日はよるかつ、コンテストのある日はたとえAtCoderとCodeforcesのRatedが同じ日にあろうと必ずどちらも参加、Codeforcesが夜中にある日は生活リズムをCodeforcesに合わせるために昼寝、等々…。
これだけ存分に競プロにのめり込めるのも、今のうちだと思うので、本業である医学の勉強を疎かにしない範囲で、これからも全力で取り組んでいきたいです。

将来について

私は昔から医者になりたいという夢があったので、必死に受験勉強をして医学部に入学しました。
ただ、これは入学してから気づいたことなのですが、医学という学問は、基本的には最終的な目標が「病を治すこと」にあるので、「作用機序はよく分からないが、この薬を使うと治った」とか、「悪い部分を切ってつなげたら治った」というところから進歩していく部分も多いのです。また、疾患一つとってみても、「なぜこの疾患がこのような症状を引き起こすのかは不明」と言われることもかなり多いです。ですので、必然的にただ暗記しなければいけないことも多くなってしまいます。
高校時代は数学や物理に特に魅せられていた私には、この学問体系がもしかしたらあまり合っていないのかもしれません。

その点、競プロの勉強においては、アルゴリズムの正当性の証明は必ず為されますし、一度理解してしまえばその理解のもとに実装すればよいので、闇雲に暗記しようとする必要はありません。学んでいてとても気持ちの良い学問です。

本当に学問的な興味で言えば、私はもしかしたら医学部に入るべきではなかったかもしれません。ただし、医者になりたいという思いは今でも変わっていません。

ですので将来的には、医学とITをもっと結び付けたい という思いが漠然とあります。 このような分野でしたら、私の興味をどちらも活かせるのではないかと考えています。

と、まあこんな大層なこと言ってますが、今の時点で具体的なビジョンは何もありません。 今は、プログラミングを学んでおくことで、将来医療現場に出た際に、IT技術が活かせるチャンスを見つける嗅覚が育つのではないかといったモチベーションで勉強しています。

おわりに

競プロ界隈でTwitter上で交流してくださる方、いつもありがとうございます。
精進に関してはもちろん、他にも多種多様な方面で努力されている方が多く、良い刺激を受けています。
今現状、こういった社会状況なので、オンサイト等でお会いできる機会はありませんが、もし今後そのような機会がありましたら、ぜひお会いしてお話してみたいユニークな方たちでいっぱいです。
これからもどうぞよろしくお願いいたします。

この記事を気に入っていただけましたら、ぜひスターもよろしくお願いします！
今後の執筆の励みになりますヽ(´▽｀)/
↓