KUPC 2018

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

最初

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

M

実家のような安心感

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

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

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

(これはコンテスト後のスクショですが，コンテスト中もこういうふうに見えていた)

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

速度

そこそこ

CF #500

A

数列を2個に割って(l_max - l_min) * (r_max - r_min)をminimize
→arc073.contest.atcoder.jp

B

0, 1が書かれたグリッドなのでなにはともあれ二部グラフ
→連結なら完全グラフにできそう
　→連結成分の個数

C

とりあえずどこを使うか決まってたら？ →各場所についてするべき高さは簡単に決まる 　→自分自身を使うかどうかと、隣の要素を使うかどうかのみに依存する

→2個以上離れた要素は関係がない
　→左から順に決めていくDP、キーを減らすのがちょっとテクニカル

D

観察すればなんとなく良さそうな戦略はわかるが、色々な場合があり、とても実装できるものではない
→物事を考えやすく
　→先頭と最後に'a', 'b'をつけてもいいという天啓が降ってくる
　　→常に先頭と最後の文字が異なるため、扱いやすく

全体を一気にシミュレーションすると人が死ぬので、どうにか小さい部分問題に落とすような思考を出来ないか
→数列の(3, 1)個目を繋げば良さそう

ICPC Domestic G: 数式探し

a * b + c * d * eみたいに+と*のみからなる式が与えられた時に，いろんな部分文字列を高速に評価するのが本質です。

こういう変なのはad-hocにやろうとすると大体大変だしバグると詰むんですが，SegTreeで強引にやってしまえばノード2個のマージに落とせるため，(SegTreeが思考停止で書けるという前提のもとでは)思考停止で掛けてそこまでバグりません

↓頑張ってコメントを足したコードです

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

//こういうのはenumを使ったほうがいいのかもしれません
const int PLUS = -1; 
const int MUL = -2;

const ll INF = TEN(9) + TEN(4);


// 数式の情報を表すノードです
struct D {
    // 数式の中に+が入っていないかのフラグです。これがtrueだと a * b * c * ... * z みたいに単一の項であることを表します    
    bool f = true;

    // この数式は l + m + rですよという値です。f = trueの場合mに値が入っていて，l, rは0です
    ll l = 0, m = 0, r = 0;
};


// 根性
D merge(D l, D r, int op) {
    D d;
    if (op == PLUS) {
        d.f = false;
        if (l.f && r.f) {
            d.l = l.m;
            d.r = r.m;
            d.m = 0;
        } else if (l.f) {
            d.l = l.m;
            d.m = min(INF, r.l + r.m);
            d.r = r.r;
        } else if (r.f) {
            d.l = l.l;
            d.m = min(INF, l.m + l.r);
            d.r = r.m;
        } else {
            d.l = l.l;
            d.m = min(INF, l.m + l.r + r.l + r.m);
            d.r = r.r;
        }
    } else {
        assert(op == MUL);
        d.f = l.f && r.f;
        if (l.f && r.f) {
            d.l = 0;
            d.m = min(INF, l.m * r.m);
            d.r = 0;
        } else if (l.f) {
            d.l = min(INF, l.m * r.l);
            d.m = r.m;
            d.r = r.r;            
        } else if (r.f) {
            d.l = l.l;
            d.m = l.m;
            d.r = min(INF, l.r * r.m);
        } else {
            // 両方単一項ではなくて，l * rとやる場合です。
            // l.l + l.m + l.r * r.l + r.m + r.r なので，l.m ~ r.mが圧縮できて以下のようになります
            d.l = l.l;
            d.m = min(INF, l.m + l.r * r.l + r.m);
            d.r = r.r;
        }
    }
    return d;
}


// SegTreeです，僕は定数倍が必要ないならポインタベースのほうが書きやすいと強硬に主張しています
// このSegTreeの要素数は数字の個数で，葉以外のノードがそれぞれopを持っています
struct Node {
    using NP = Node*;
    NP l, r; int sz;
    D d; // そのノードの数式の値
    int op; // 葉以外が持っていて，PLUSかMULです

    Node(int _sz, const V<ll> &v, int off = 0) : sz(_sz) {
        if (sz == 1) {
            assert(v[off] > 0);
            d = D{true, 0, v[off], 0};
            return;
        }
        int lsz = sz/2;
        l = new Node(lsz, v, off);
        r = new Node(sz-lsz, v, off + 2*lsz);
        op = v[off + 2*lsz-1];//
        assert(op == MUL || op == PLUS);
        d = merge(l->d, r->d, op);
    }

    // a番目の数字からb-1番目の数字までの数式を取り出して，評価します
    D get(int a, int b) {
        // 単位元が無いので単位元がないタイプのsegtreeを書きましょう
        if (b <= 0 || sz <= a) assert(false);
        if (a <= 0 && sz <= b) return d;
        if (b <= sz/2) return l->get(a, b);
        if (sz/2 <= a) return r->get(a-sz/2, b-sz/2);
        D ld = l->get(a, b);
        D rd = r->get(a-sz/2, b-sz/2);
        return merge(ld, rd, op);
    }
};


ll n;
string s;
int p;

ll ans; // グローバル変数で，答えはここにどんどん足しこまれていきます


// vは{数字, op, 数字, op, 数字, op, 数字, ..., 数字}みたいになっています
// 副作用として答えをansに足しこんで，最後に数式全体を評価した値を返します
ll solve2(V<ll> v) {
    assert(v.size() % 2);
    int m = int(v.size()) / 2 + 1; // 数字の個数
    auto tr = new Node(m, v);

    //a番目の数字からb-1番目の数字を評価して返す
    auto eval = [&](int a, int b) {
        auto d = tr->get(a, b);
        return min(INF, d.l + d.m + d.r);
    };
    for (int i = 0; i < m; i++) {
        int l, r, a, b;
        l = i, r = m+1;
        while (r-l > 1) {
            int md = (l+r)/2;
            if (eval(i, md) < n) {
                l = md;
            } else {
                r = md;
            }
        }
        a = r;
        l = i; r = m+1;
        while (r-l > 1) {
            int md = (l+r)/2;
            if (eval(i, md) <= n) {
                l = md;
            } else {
                r = md;
            }
        }
        b = r;
        ans += b-a;
    }
    return eval(0, m);
}

// 数式全体を評価した値を返します，最後に呼んでいるsolve2(v)の内側でansに答えが足し込まれます
ll solve() {
    V<ll> v;
    while (p != int(s.size()) && s[p] != ')') {
        char c = s[p];
        if (c == '(') {
            p++;
            v.push_back(solve());
            assert(s[p] == ')'); p++;
            continue;
        }
        if (isdigit(c)) {
            p++;
            v.push_back(c - '0');
            continue;
        }
        if (c == '*') {
            p++;
            v.push_back(MUL);
            continue;
        }
        if (c == '+') {
            p++;
            v.push_back(PLUS);
            continue;
        }
        assert(false);
    }
    return solve2(v);
}

bool first() {
    cin >> n;
    if (!n) return false;
    cin >> s; p = 0;

    ans = 0;
    solve();
    cout << ans << endl;
    return true;
}

int main() {
    while (first()) {}
}