C++ライブラリのテストを切り出している

C++ライブラリのストレステストを切り出しているという話

背景

プログラミングコンテストのライブラリには色々と要求されるが,一番重要なのはバグを少なくすることだと思う。 バグが無いだろうと信頼できればバグったときでもライブラリ以外の部分だけ疑えば良くなり,逆にライブラリを疑いだしたらもう実装を簡略化, 高速化するという目的に対し本末転倒ではないかと思う。

もちろんバグがないことを保証するのは不可能であるが,適切にテストを行えばバグが潜む可能性を十分下げることは可能だと思う。

テストの書き方

大きく分けて オンラインジャッジを活用する / リポジトリにテスト用のコードも書く の2種があると思う,両方一長一短

僕は後者のリポジトリにテスト用のコードも書く,のほうが好みで,自分のC++ライブラリ(https://github.com/yosupo06/Algorithm)にもある程度ストレステストを書いたりしていたのだが,ライブラリの長さが制限されているコンテスト用にライブラリをカスタマイズする必要が出てきた(個人的にこのルールに思うところはあるが)。

当然テストは流用できるのだが,どうせなら切り出して両方のライブラリから共通で使えるようにしてしまおうと思い,切り出している。

切り出したもの

https://github.com/yosupo06/algorithm-test

swap(v, v)は危ない?という話

-D_GLIBCXX_DEBUGを付けて以下のコードを実行するとアサートにひっかかります(https://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor)。

struct S {
    vector<int> a;
}
S s;
swap(s, s);

どうやらswap内部でs = std::move(s)が発生し、これがヤバイっぽい(UBを引き起す?)です。 競技プログラミングにおいては、ランダムな並び換え(これはshuffle使えばいいけど)や、ガウスの掃き出し法などでswap(s, s)を使うことが多いと思います。

対策1

swap(s, s)をしないようにする。

対策2

UBと言ってもどうせ動くのでアサート自体を無効化する(https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle)

#include <debug/macros.h>
#undef __glibcxx_check_self_move_assign
#define __glibcxx_check_self_move_assign(x)

struct S {
    vector<int> a;
}
S s;
swap(s, s);

KUPC 2018

たまには記事を書きます,優勝したし(イキリ)

最初

何はともあれ木や数列にクエリを投げている100,000を探します。2題もありました。

M

実家のような安心感

クエリ3は見たことない気がします,有名?

最初に実装を間違えてWA+MLEを貰いました。 理由はわからないんですが,なぜかbetaだとコンテスト中でもどのぐらいTL / MLを使ったか見えた(これバグじゃない?)ので,あとちょっとメモリを減らせば通ることを確信しました(不正か?)。

なのでバグを直して,TrieのNodeのサイズを2/3にしたら通りました。

f:id:yosupo:20181001150522p:plain (これはコンテスト後のスクショですが,コンテスト中もこういうふうに見えていた)

I

ちょっと考えたらlogたくさん解(SegtreeのNodeに2次元BITを乗せる)がわかったんですが,どう考えても間に合わないのでもう少し考えると,区間をsetで管理すればオーダーが落ちることがわかったので書きました(setが嫌いなのでsegtreeでごまかそうとしがち)。

解かれてるニム?に取り掛かりました。今考えると戦略を間違えていたと思います。

J

ただし、互いに 2 回目以降の手番では、 直前の自分の手番で宣言した整数よりも大きい x を宣言してはいけない。 と誤読して時間を溶かしました。これで実験すると規則性がありそうでなさそうでありそうなテーブルが作れます。

相手より大きい数を一度宣言してしまったらもう殆ど負けみたいなものじゃないか?と気づくと解けます。

順位表で前半からやってる人のスピードと後半の重さから考えて,後半を4題解く人は出ないだろうと予想しました。 400 500 500解く人が出たらどうしようもないのでその場合は諦めることにして,前半を始めることにしました。

A

うんうん

B

DP書いちゃった

C

全探索系で出そうだな〜と思いながら紙で考えて解いた

D

だいたい半分にできそうなことはわかったが,クエリをきっちり30回で抑えられる証明ができなかった。書いて実験したら30回ぴったりっぽかったので投げた

E

普通のDP,バグりそうだなーと思いながら書いたらバグらなかった,すごいので

F

グラフを2色に塗り分け + 辺に重み付き,というのは見たことがあった,確かIPSC

G

結構悩んだ結果,logを入れれば良くない?と気づいた。でも$2 \times 4 \times 8 \geq 16$だから$a_{16}$の値が負になるなあと悩んでいた(どういうハマりかた?)

順位表を眺めるとあと1個解かないと負けそう & 500を解かれると300取っても同点 ということでHとKのどっちに行くか悩む。

順位表を眺めるにHなら時間内に通せそうだったので,Hに行くことにする。今思うとKのほうが良かった気がする

H

ほうじょっぽい見た目をしていたのでほうじょをする。

大体実家DPっぽい?同色がなければ実家DPだね。

同色で完全に覆う区間があるとDPが破滅することでかなり悩んだ結果,よく考えるとそもそも抹消できたため解けた。と思ったら実装がなんかバグりまくってしまい…

運良くギリギリで通せたので良かったです。

JAG夏 2018 Day2 準備記

!!!解法のネタバレが含まれます!!!でも解説ではないです!!!

yosupo, sigma, sugim, maroonでJAGの夏合宿を1セット作りました

経緯

petrozavodsk(ロシア)では、毎年競プロの合宿が行われています。ロシアなので人外ばっかりいるので、セットもそれ相応の難易度になっています。 そこにyosupo, sigma, sugimでセットを作って送ろうという話があったのが始まりです。全部で11問作りました。

そのうち8題を選んで、最初に2題追加したのがAPC001です。残りの3題に、最初に問題を8題追加したのが今回のセットです。 逆に言うと、APC001から最初の2題抜いて、今回のセットの3題(Knapsack And Queries / Construct One Point / ADD DIV MAX(petrozavodskの時点ではRESTOREは無かった))を足したのがpetrozavodskに送ったセットです。

とんでもない難易度に思えますがpetrozavodskだと9問解かれるらしいです→(http://karelia.snarknews.info/index.cgi?data=macros/day&menu=index&head=index&sbname=2018w&class=2018w&round=03)。 ロシアはすごいですね(上のアルファベットにカーソルを合わせると問題名が見えます)。

夏合宿

箇条書き

  • maroonはなんか流れで巻き込みましたが、結果的には相当作問してくれました。ありがとうございます。

  • インターンシップを始めたら全然時間がとれなくなって、Fのデータ作成が炎上しました

  • ↑は諦めるという手法を取ることにより鎮火しました、実はケースがクソザコです(ごめんなさい…)

  • 突然数日前に英語をつけよう!という話になり、英語がつきました。maroonが大量の英語を書きました。

  • 前日の夜にJAGに英文校正頼む!って言ったらしてくれて、かなり大量の指摘をいただきました。JAGの方々本当にありがとうございます。(修正前に問題文は印刷されたので、合宿に来た方は見比べると指摘されたところがわかります)

  • 風船はやっぱり配りたいなってなって、FAだけ配ることにしました。D以降は全部行けそうだったので全部配りました。

問題の感想

自分が関わった問題の感想を述べます。

Knapsack And Queries

Q=1ならばなんの変哲もないDPです。 クエリに答えるために要素を分割したくなるのですが、DPテーブルのmergeにminの畳み込みみたいなのが欲しくなります。そしてこれは厳しいことで有名です。ですが実は、DPテーブルが2個に分割されていても、高速にクエリに答えられるという性質が有ります(3個以上だとだめです)。

よって2個までなら分割できて、queueを2個に分割というと知っている人は知っているテクニックになります。僕は大学の授業でやりました。

これは解法ドリブンで作りました。queueを2個に分割というのは昔から出したかったテクニックなのですが、うまく出題できたと思います。

Point Sequences

数ヶ月前にひたすら幾何精進をしていた時期があります。 その時期に、幾何問題のepsの設定を、雰囲気submit連打ではなく理論立てて設定できないか色々考えたことがあります。 その結果として、この問題の漸化式のような単純な操作をするだけでも爆発するから、深く考えても仕方がないという結論になりました。

ですが逆手に取って、この漸化式から問題を作れないか(そして普通にdoubleで計算すると爆発するんですよ〜ってイキれないか)考えました。 直線の交点は連立方程式という昔習った知識を思い出し、連立方程式ならmodで面白いことが出来ないかと思い、問題が出来ました。

一発ギャグみたいな問題で、どのぐらい解かれるか予想できずに不安だったのですが、思ってたのと同じぐらいの解かれ具合だったのでよかったです。

Construct One Point

三角形の内側の点を一点構成するだけというシンプルな問題です。よく考えるとピックの定理を検索できないという条件下だと厳しかったかもしれません。

これは3人でいたときに適当にみんなで問題設定を考えて、うまく解けたので出しました。

ADD DIV MAX RESTORE

petrozavodskに出したときはADD DIV MAXでした。ですがpetrozavodskの中国ミラーで11分で解かれた(!?)ので、何かと思ったらsegment tree beatsというテクニックで解けたようです。11分で解いたのはsegment tree beatsの記事を書いた人のチームでした。なのでRESTOREがつきました。

今回作った中で、一番好きな問題です。一見不可能にしか思えないんですが、実は物事がすべてうまくいって、結局普通の遅延伝播segtreeを書くだけになります。 「長さNの数列が与えられます。以下のクエリをQ個処理してください。type1: L, Rが与えられるので〜」みたいな問題文で、しかも考察がボス問級に難しいという問題はずっと作りたかったので、作れて満足です。

AB Sort

とりあえず適当に操作を考えた後、sigmaとこれのいい性質無いかな〜って考えたらsigmaが見つけました。で、その性質を活かすために、クエリを追加しました。

クエリは何も考えずにAB反転にしたんですが、もう少し簡単なクエリでよかったかもしれません。

問題案が十分だったこととか、データ構造が多かったこととか、なんか近い問題が直前に出たとかで、petrozavodskには送らずボツ担ってた問題です。 準備はしてあったので今回は使うことにしました。

遅延Segtree2

イロモノにしか見えないと思いきや案外いいのでは?

#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
template<class T> using V = vector<T>;

//template<class D, class L, auto op_dd, auto op_dl, auto op_ll> (since c++17)
template<class D, class L, D (*op_dd)(D, D), L (*op_dl)(D, L), L (*op_ll)(L, L)>
struct SegTree {
    int sz, lg; //(2^lgに拡張後の)サイズ, lg
    D e_d; V<D> d;
    L e_l; V<L> lz;

    SegTree(int n, D e_d, L e_l) : SegTree(V<D>(n, e_d), e_d, e_l) {}
    SegTree(V<D> first, D _e_d, L _e_l) : e_d(_e_d), e_l(_e_l) {
        int n = int(first.size());
        lg = 1;
        while ((1<<lg) < n) lg++;
        sz = 1<<lg;
        d = V<D>(2*sz, e_d);
        lz = V<L>(2*sz, e_l);
        for (int i = 0; i < n; i++) d[sz + i] = first[i];
        for (int i = sz-1; i >= 0; i--) {
            update(i);
        }
    }

    void all_add(int k, L x) {
        d[k] = op_dl(d[k], x);
        lz[k] = op_ll(lz[k], x);
    }
    void push(int k) {
        all_add(2*k, lz[k]); all_add(2*k+1, lz[k]);
        lz[k] = e_l;
    }
    void update(int k) { d[k] = op_dd(d[2*k], d[2*k+1]); }

    D sum(int a, int b, int l, int r, int k) {
        if (b <= l || r <= a) return e_d;
        if (a <= l && r <= b) return d[k];
        push(k);
        int mid = (l + r) / 2;
        return op_dd(sum(a, b, l, mid, 2*k), sum(a, b, mid, r, 2*k+1));
    }
    D sum(int a, int b) { return sum(a, b, 0, sz, 1); }

    void add(int a, int b, L x, int l, int r, int k) {
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            all_add(k, x);
            return;
        }
        push(k);
        int mid = (l + r) / 2;
        add(a, b, x, l, mid, 2*k); add(a, b, x, mid, r, 2*k+1);
        update(k);
    }
    void add(int a, int b, L x) { add(a, b, x, 0, sz, 1); }

};

int my_min(int a, int b) { return min(a, b); }
int add(int a, int b) { return a + b; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    auto seg = SegTree<int, int, my_min, add, add>(V<int>(n, 0), (1<<30) - 1000, 0);
    for (int i = 0; i < q; i++) {
        int ty, x, y;
        cin >> ty >> x >> y; y++;
        if (ty == 0) {
            int z;
            cin >> z;
            seg.add(x, y, z);
        } else {
            cout << seg.sum(x, y) << endl;
        }
    }
    return 0;
}

遅延SegTree

色々隠蔽の方法を考えています。

これはなんかごついね

#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
template<class T> using V = vector<T>;

template<class OP>
struct SegTree {
    using D = typename OP::D;
    using L = typename OP::L;
    static constexpr auto e_d = OP::e_d;
    static constexpr auto e_l = OP::e_l;
    static constexpr auto op_dd = OP::op_dd;
    static constexpr auto op_dl = OP::op_dl;
    static constexpr auto op_ll = OP::op_ll;

    int sz, lg; //(2^lgに拡張後の)サイズ, lg
    V<D> d;
    V<L> lz;

    SegTree(int n) : SegTree(V<D>(n, e_d())) {}
    SegTree(V<D> first) {
        int n = int(first.size());
        lg = 1;
        while ((1<<lg) < n) lg++;
        sz = 1<<lg;
        d = V<D>(2*sz, e_d());
        lz = V<L>(2*sz, e_l());
        for (int i = 0; i < n; i++) d[sz + i] = first[i];
        for (int i = sz-1; i >= 0; i--) {
            update(i);
        }
    }

    void all_add(int k, L x) {
        d[k] = op_dl(d[k], x);
        lz[k] = op_ll(lz[k], x);
    }
    void push(int k) {
        all_add(2*k, lz[k]);
        all_add(2*k+1, lz[k]);
        lz[k] = e_l();
    }
    void update(int k) {
        d[k] = op_dd(d[2*k], d[2*k+1]);
    }

    D sum(int a, int b, int l, int r, int k) {
        if (b <= l || r <= a) return e_d();
        if (a <= l && r <= b) return d[k];
        push(k);
        int mid = (l + r) / 2;
        return op_dd(sum(a, b, l, mid, 2*k), sum(a, b, mid, r, 2*k+1));
    }
    D sum(int a, int b) { return sum(a, b, 0, sz, 1); }

    void add(int a, int b, L x, int l, int r, int k) {
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            all_add(k, x);
            return;
        }
        push(k);
        int mid = (l + r) / 2;
        add(a, b, x, l, mid, 2*k); add(a, b, x, mid, r, 2*k+1);
        update(k);
    }
    void add(int a, int b, L x) { add(a, b, x, 0, sz, 1); }

};

//starry sky tree
struct OP {
    using D = int;
    using L = int;
    static constexpr D e_d() { return (1<<30) - 1000; }
    static constexpr L e_l() { return 0; }
    static int op_dd(D l, L r) { return min(l, r); }
    static int op_dl(D l, L r) { return l + r; }
    static int op_ll(D l, L r) { return l + r; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    auto seg = SegTree<OP>(V<int>(n, 0));
    for (int i = 0; i < q; i++) {
        int ty, x, y;
        cin >> ty >> x >> y; y++;
        if (ty == 0) {
            int z;
            cin >> z;
            seg.add(x, y, z);
        } else {
            cout << seg.sum(x, y) << endl;
        }
    }
    return 0;
}

一般化(抽象化?)Segtree

#include <bits/stdc++.h>
 
using namespace std;
using uint = unsigned int;
template<class T> using V = vector<T>;

template<class D, class OP>
struct SegTree {
    OP op; //f(data, data) -> data
    D e; //単位元
    int n, sz, lg; //サイズ, 2^lgに拡張後のサイズ, lg
    V<D> seg;
 
    SegTree(V<D> first, OP _op, D _e) : op(_op), e(_e) {
        n = int(first.size());
        lg = 1;
        while ((1<<lg) < n) lg++;
        sz = 1<<lg;
        seg = V<D>(2*sz, e);
        for (int i = 0; i < n; i++) seg[sz + i] = first[i];
        for (int i = sz-1; i >= 0; i--) {
            update(i);
        }
    }
 
    void update(int k) { seg[k] = op(seg[2*k], seg[2*k+1]); }
 
    D sum(int a, int b) {
        D sm_l = e, sm_r = e;
        a += sz; b += sz;
        while (a < b) {
            if (a & 1) sm_l = op(sm_l, seg[a++]);
            if (b & 1) sm_r = op(seg[--b], sm_r);
            a >>= 1; b >>= 1;
        }
        return op(sm_l, sm_r);
    }
 
    void single_set(int k, D x) {
        k += sz;
        seg[k] = x;
        for (int i = 1; i <= lg; i++) update(k>>i);
    }
};
//helper for c++11, 14
template<class D, class OP> SegTree<D, OP> make_segtree(V<D> first, OP op, D e) { return SegTree<D, OP>(first, op, e); }

使い方

RMQ

const int INF = 1000000007;
auto seg = SegTree(V<int>(n, INF), [&](int a, int b){ return min(a, b); }, INF); (since c++1z)
auto seg = make_segtree(V<int>(n, INF), [&](int a, int b){ return min(a, b); }, INF);

コード例

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3079917#1

速度

そこそこ