はまやんはまやんはまやん

hamayanhamayan's blog

2018年ニッチな競プロ典型ネタ

競技プログラミング

この記事は Competitive Programming (2) Advent Calendar 2018 の 8 日目の記事です。
前日はたたもさんの「コマンドラインツールatcoder-cliを公開しました」です。

あまり見る機会は多くないけど、典型化できそうなニッチなネタを書いていきます。
対象は黄色くらいです。
この前出た「November Circuits '18」が典型度が高くて、ほぼそれです。
紹介テクは3つです。

  • クエリの小さい方で全探索 + メモ化することで間に合う
  • SuperVector
  • 貪欲で確かめる要領で数え上げる

クエリの小さい方で全探索 + メモ化することで間に合う

HR Gary and Subsequence Queries

問題概要

N個の文字列Sが与えられる。
Q個のクエリを答える。
「S[a]がS[b]の部分列またはS[b]がS[a]の部分列ならYes, そうでないならNoを出力」
Sの総和≦10^6
Q≦10^5

テク

総和が決まっている配列らのクエリは要素数が小さい方で全探索し、かつ、計算結果をメモ化すると間に合う

解説

一発目からテクがむっちゃわかりにくいが、問題自体はシンプル。
ある1つのクエリについてどのように処理するかを考えよう。
solve(a,b) := S[a]とS[b]についてYes,Noを返す
この関数は、以下のことが成り立つ。

  • solve(a,b)=solve(b,a)であるので、|S[a]|≧|S[b]|と考えて良い
  • solve(a,b)は何度やっても同じ結果になるはずなので、メモ化することができる

さて、この関数をO(min(|S[a]|,|S[b]|))で計算する方法を考えよう。
　
│S[a]│≧│S[b]│なので、S[b]がS[a]の部分列であることを確かめればいい。
これは貪欲法で解ける。
つまり、S[b]の文字をS[a]の先頭から貪欲に探していけばいい。
具体的には以下のような感じ

S[a] = aabbcc
S[b] = abc

aabbcc
a b c
S[a] = asrewtegadfgggf
S[b] = stgf

asrewtegadfgggf
 s   t g  f

この貪欲法を高速化するために、以下の配列を用意する。
nxt[i][c][j] := S[i]のj文字目以降で最初に文字cが出てくるのは何番目か
これは累積minで構築することができる。
この配列を使うことで、nxt[i][c][j]で一番近い文字にO(1)で遷移できる。
そのため、|S[b]|回遷移することで、S[a]の任意の文字で終了できるなら、答えはYesになる。
これで各クエリO(min(|S[a]|,|S[b]|))を実現できた。

ここからが典型の使い所なのだが、各クエリについて文字列の短い方の長さをnとしたときに1クエリO(n)でメモ化すれば、全体で間に合う。
具体的にはO(Qsqrt(sumS))で解ける。
　
なぜ間に合うか考えてみる。
ここの部分は正直雰囲気で書いているので、違ってたら教えてほしいです。
すべて異なる組み合わせであって、短い方の長さを和を最大化するためには、すべて同じ長さの文字列を用意すればいい。文字列をn個用意したなら、n(n-1)/2組できるため、Q=n(n-1)/2で、大体n=sqrt(Q)=500くらい。
文字列の総和は10^6なので、文字列は10^6/500=2000文字にする。
すると、クエリ数の最大数が10^5で小さい方の文字列は2*10^3なので、全体の計算量は2*10^8となる。
これはギリギリ間に合う。
　
この典型は「総和が決まっている配列らのクエリ」について有効である。

int N, Q;
string S[101010];
vector<int> nxt[101010][26];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
map<int, string> memo[101010];
string solve(int a, int b) {
    if (S[a].length() < S[b].length()) swap(a, b);
    if (memo[a].count(b)) return memo[a][b];
 
    int cur = 0;
    fore(_c, S[b]) {
        int c = _c - 'a';
        cur = nxt[a][c][cur];
        if (cur == inf) return memo[a][b] = no;
    }
    return memo[a][b] = yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) {
        cin >> S[i];
        int n = S[i].length();
        rep(c, 0, 26) nxt[i][c].resize(n + 1, inf);
        rep(j, 0, n) nxt[i][S[i][j] - 'a'][j] = j + 1;
        rep(c, 0, 26) rrep(j, n - 1, 0) chmin(nxt[i][c][j], nxt[i][c][j + 1]);
    }
    rep(q, 0, Q) {
        int a, b; cin >> a >> b;
        a--; b--;
        printf("%s\n", solve(a,b).c_str());
    }
}

類題

　
　
　
　
　
　

SuperVector

HR Clothes Arrangement

問題概要

N着の服があり、FILOの入れ物に入っている。
これについてQ個の2種類のクエリを答える。
「1 C」入れ物に色Cの服を入れる
「2 C K」入れ物からK番目の色Cの服を取り出す（このとき、取り出す際に出した服の枚数を答える）

テク

平衡二分木を使うと、分割可能なvectorが作れる。

解説

BITを主に使用する。
i番目に追加された服がまだ入っているとき1が入っているとする。
すると、i番目に追加された服を取り出すときは、bit[i+1..max]がi番目の服を取るのに取り出す必要がある服の枚数となる。
後処理するべき問題は、まだ取り出されていない色Cの服のi番目が何番目に追加された服かを高速に取り出せればいい。
これはほぼvectorで実現できる。
sv[c] := 色cの取り出されていない服で、何番目に追加されているかが入っている配列
sv[c][i] := 色cの取り出されていない服で、先頭からi番目に入れられている服は何番目に追加されたか
　
Nを何個服が追加されたかを入れてある。
クエリ1

  • sv[c]の先頭にNを追加
  • bit[N]を1にする
  • Nをインクリメント

クエリ2

  • sv[c][k]に何番目に追加された服かが書いてあるので、idxとおく
  • bit[idx+1...N]が答え
  • bit[idx]を0にする
  • sv[c][k]を取り除く

　　
vectorにおいて、「任意の要素を取り除く」、「任意の場所に要素を追加する」ことをO(logN)で実現するデータ構造がある。
それが、平衡二分木。これを持っていると、「任意の要素を取り除く」「任意の場所に要素を追加する」「ある要素の値を取得する」がO(logN)でできる。
配列を分割・結合するのがO(logN)でできるため、これを応用している。
分割・結合の応用の範囲内であれば、他のこともできる。
自分はライブラリ化のために平衡二分木で作られたvectorをSuperVectorとして、使っている。
これの応用として、セグメントツリーを平衡二分木で作ることで、分割・結合可能なセグメントツリーを作ることもできる。

template<typename V> struct SuperVector {
    int getrand(int x) { static uint32_t y = time(0); y ^= (y << 13); y ^= (y >> 17); y ^= (y << 5); return y % x; }
    struct Node { V val; Node *lch, *rch; int sz; Node(V a) :val(a), lch(0), rch(0), sz(1) {  } };
 
    SuperVector() :root(NULL) {}
    Node *root;
    inline int size(Node *t) { return t ? t->sz : 0; }
    int size() { return size(root); }
    inline Node *update(Node *t) {
        if (!t)return 0; t->sz = size(t->lch) + size(t->rch) + 1; return t;
    }
 
    Node *merge(Node *a, Node *b) {
        if (!a)return b;
        if (!b)return a;
 
        if (getrand(size(a) + size(b)) < size(a)) {
            a->rch = merge(a->rch, b);
            return update(a);
        }
        else {
            b->lch = merge(a, b->lch);
            return update(b);
        }
    }
 
    template<class... T> Node *merge(Node *a, T... y) { return merge(a, merge(y...)); }
 
    pair<Node *, Node *>split(Node *t, int k) {//[0,k) [k,N)
        if (!t)return make_pair(t, t);
        if (k <= size(t->lch)) {
            pair<Node *, Node *>s = split(t->lch, k);
            t->lch = s.second;
            return make_pair(s.first, update(t));
        }
        else {
            pair<Node *, Node *>s = split(t->rch, k - size(t->lch) - 1);
            t->rch = s.first;
            return make_pair(update(t), s.second);
        }
    }
 
    // [l,r]番目でa,b,cに分ける(終わったらちゃんとマージすること)
    // rootは0になってる
    tuple<Node*, Node*, Node*> split3(int l, int r) {
        auto p = split(root, l);
 
        auto a = p.first;
 
        auto q = split(p.second, r - l + 1);
 
        auto b = q.first;
        auto c = q.second;
        root = 0;
 
        return make_tuple(a, b, c);
    }
 
    void change(int i, Node* v) { // i番目をvに更新
        auto p = split(root, i);
        auto a = p.first;
        auto q = split(p.second, 1);
        Node* b = q.first;
        auto c = q.second;
 
        b = v;
 
        root = merge(merge(a, b), c);
    }
 
    void dump() {
        dump(root);
        cout << endl;
    }
    void dump(Node *t) {
        if (t == NULL)return;
        dump(t->lch);
        cout << t->val << " ";
        dump(t->rch);
    }
 
    void push_back(V v) {
        Node *t = new Node(v);
        root = merge(root, t);
    }
 
    void push_front(V v) {
        Node *t = new Node(v);
        root = merge(t, root);
    }
 
    void shift(int l, int r) { // [l,r]の範囲を右にシフトする(最右は左へ移る)
        Node *a, *b, *c;
        tie(a, b, c) = split3(l, r);
 
        Node *ba, *bb;
        tie(ba, bb) = split(b, r - l);
 
        root = merge(root, a, bb, ba, c);
    }
 
    V operator[](int i) { 
        auto p = split(root, i);
        auto a = p.first;
        auto q = split(p.second, 1);
        Node* b = q.first;
        auto c = q.second;
 
        root = merge(merge(a, b), c);
 
        return b->val;
    }
 
    SuperVector cut(int L, int R) { // [L,R]を切り取る
        Node *a, *b, *c;
        tie(a, b, c) = split3(L, R);
 
        root = merge(a, c);
 
        SuperVector res;
        res.root = b;
        return res;
    }
 
    void insert(int i, V v) { // i番目としてndを追加する(i-1番目の後ろに追加)
        Node *a, *b;
        Node* nd = new Node(v);
        tie(a, b) = split(root, i);
        root = merge(a, nd, b);
    }
 
    template<typename Func> void foreach(Func f) { foreach(root, f); }
    template<typename Func> void foreach(Node* n, Func &f) {
        if (!n) return;
        if (n->lch) foreach(n->lch, f);
        f(n);
        if (n->rch) foreach(n->rch, f);
    }
};
int N, Q;
BIT<int> bit(1010101);
SuperVector<int> sv[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int c; cin >> c;
        bit.add(i, 1);
        sv[c].push_front(i);
    }
    cin >> Q;
    rep(q, 0, Q) {
        int ty; cin >> ty;
        if (ty == 1) {
            int c; cin >> c;
            bit.add(N, 1);
            sv[c].push_front(N);
            N++;
        } else {
            int c, k; cin >> c >> k;
            if (sv[c].size() < k) {
                printf("-1\n");
                continue;
            }
 
            k--;
            int idx = sv[c][k];
            sv[c].cut(k, k);
 
            bit.add(idx, -1);
            int ans = bit.get(idx, N);
            printf("%d\n", ans);
            
        }
    }
}


　
　
　
　
　
　

貪欲で確かめる要領で数え上げる

HR Permutation

問題概要

ある数Nが与えられる。
この数でM種類の数が現れるとする。
現れる数を1ずつ使った数はleading-zeroを許すとM!個ある。
この中で、Nの部分列（連続でなくてもいい）として含まれるものは何通りあるか。

テク

普通にやるとかぶって数えてしまう数え上げは、貪欲に確かめる要領で数え上げるのが良い。
このテクはDEGwerさんの数え上げテクニック集に乗っている。
参考

解説

数字が10種類しかなく、2^10ができそうな感じがあるので、DPが思いつく。
dp[i][msk] := i文字目までで出てきた数字がmskである組み合わせ
しかし、これは普通にやると、重複して数えてしまう。
例えば、001であると、0_1, _01を2回数えるが、今回はM!通りのなかで、条件を満たすものであるため、この2つは1つとして数えたい。
　
こういう問題で使えるテクが、「普通にやるとかぶって数えてしまう数え上げは、貪欲に確かめる要領で数え上げるのが良い」である。
『貪欲に確かめる要領』というのがわかりにくい。
例えば、14324432という数で1342という数を部分列として含むかの判定問題を考える。
すると、1342を頭から貪欲に取ってくることができれば、部分列として含むことが判定できる。
14324432
=_=_=__=
DPの遷移を「一番近い所」のように貪欲に決めることで、ある部分列が数え上げられるルートが1通りとなり、重複に数えられることを防ぐ。
　
よって、この問題は、事前計算としてnxt配列を作る。
nxt[i][c] := i桁目から一番近い数cの桁目
これは累積minの要領で作れる。
このテクを使うときは、大体この配列を作ることになる。
　
あとは、遷移のときにnxt配列を使って、貪欲に数を決めていけばいい。
遷移周りは下のプログラムを見るとわかりやすいかもしれない。

string S; int N;
ll dp[101][1 << 10];
int nxt[101][10];
//---------------------------------------------------------------------------------------------------
ll solve() {
    cin >> S;
    N = S.length();
    S = "#" + S;
    
    rep(i, 0, N + 1) rep(msk, 0, 1 << 10) dp[i][msk] = 0;
    dp[0][0] = 1;
 
    rep(i, 0, N + 1) rep(c, 0, 10) nxt[i][c] = inf;
    rep(i, 1, N + 1) nxt[i - 1][S[i] - '0'] = i;
    rrep(i, N - 1, 0) rep(c, 0, 10) chmin(nxt[i][c], nxt[i + 1][c]);
    
    rep(i, 0, N) rep(msk, 0, 1 << 10) {
        rep(c, 0, 10) if (!(msk & (1 << c)) and nxt[i][c] < inf) dp[nxt[i][c]][msk | (1 << c)] += dp[i][msk];
    }
 
    int msk = 0;
    rep(i, 1, N + 1) msk |= 1 << (S[i] - '0');
    
    ll ans = 0;
    rep(i, 0, N + 1) ans += dp[i][msk];
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) printf("%lld\n", solve());
}

類題

　
　
　
　
　

あとがき

えーSuperVectorなんですけど、xuzijian629さんの記事がSuperVectorの最終進化系みたいな感じになってまして、そちらをご覧いただくのがいいかもです。
「これの応用として、セグメントツリーを平衡二分木で作ることで、分割・結合可能なセグメントツリーを作ることもできる。」と書いたのが、これのことです。
　
さて、明日は、くぬーさんが勉強したことについて書かれるそうです。楽しみですー