libclangのPython bindingsで構文解析する

,

なんだか難しいやつという印象があったが使えば使えたので簡単にメモしておく。 githubに上げて動態保存したいところだが、用途が死んでしまったのでblogに。

導入

Ubuntuなら

$ apt install python-clang-4.0 libclang-4.0-dev

あるいはpip https://pypi.python.org/pypi/clang

$ pip2 instal clang

Python 3.xのは入るが動かなかった。

資料

コードは全てclang/cindex.pyの中。これを読んでいい感じにすればよい。 手元では特に /usr/lib/python2.7/dist-packages/clang/cindex.py に位置していた。

公式のdocumentはこれ: http://releases.llvm.org/4.0.0/tools/clang/docs/index.html

その他の資料としては:

概要

登場するclassについて

  • Index
    • なんか top-level なやつ、libclang-x.y.so を保持するぐらいの役割
  • TranslationUnit
    • 構文解析結果の木をまとめたもの
    • index.parse(...)により作られる
  • Cursor
    • 木の頂点を指す
    • tu.cursorで得られる
    • cursor.get_children()で子を取得し再帰する
    • cursor.kindCursorKind.FUNCTION_DECLだとかそういう情報が取れる

具体例

まずIndexの作成。これはすぐ。

# Python Version: 2.x
from clang.cindex import Index
index = Index.create()

次にTranslationUnitを作る。コードを持ってきて解析させる。コンパイル時オプションを渡したり出力される警告やエラーを受け取ったりもできる。

path = 'foo.cpp'
code = '''\
#include <iostream>
using namespace std;
int main() {
    cout << hello + world << endl;
    return 0;
}
'''
tu = index.parse(path, unsaved_files=[ (path, code) ], args=[ '-std=c++14' ])

そしてCursorで木を舐める。 普通にやるだけ。 例えば以下のようにすると、iostreamをincludeすることで定義される構造体/classが列挙される。

from clang.cindex import CursorKind
namespace = []
def visit(cursor):
    global namespace
    if cursor.kind == CursorKind.TRANSLATION_UNIT:
        for child in cursor.get_children():
            visit(child)
    elif cursor.kind == CursorKind.NAMESPACE:
        namespace += [ cursor.spelling ]
        for child in cursor.get_children():
            visit(child)
        namespace.pop()
    elif cursor.kind in ( CursorKind.STRUCT_DECL, CursorKind.CLASS_DECL, CursorKind.CLASS_TEMPLATE, ):
        if cursor.spelling.strip() and not cursor.spelling.startswith('_'):
            print '::'.join(namespace + [ cursor.spelling ])  #=> std::allocator std::uses_allocator std::char_traits std::__cxx11::basic_string ...
    else:
        pass
visit(tu.cursor)

AtCoder Grand Contest 009: A - Multiple Array

,

http://agc009.contest.atcoder.jp/tasks/agc009_a

solution

典型ぽい貪欲。最後の項を変えるには最後のボタンを押すしかないので、後ろから順にそのようにする。$O(N)$。

implementation

必要になったから使ったのだけどzip(*[ ... ])は便利

#!/usr/bin/env python3
n = int(input())
a, b = zip(*[ map(int, input().split()) for _ in range(n) ])
c = 0
for i in reversed(range(n)):
    c += (- (a[i] + c)) % b[i]
print(c)

AtCoder Grand Contest 009: C - Division into Two

,

http://agc009.contest.atcoder.jp/tasks/agc009_c

蟻本などの教科書に載ってそうな感じ。

solution

DP。 愚直だと$O(N^3)$。 $A \le B$と仮定すると$X$側の使った位置をほとんど覚えなくてよくて$O(N^2)$。 しゃくとり法と累積和で$O(N)$。

左から順に所属を決めていく。 愚直には$s_i = \max X, \; s_j = \max Y$であるようなときの$(X, Y)$の場合の数を$\mathrm{dp}(i, j)$とする。 $A \le B$であると仮定する。 $i \lt j - 1$であるとき$s_i + A \le s_{j-1} + B \le s_j + B$であるので、$s_{j+1}$以降の所属を決めるのに$i$の細かい値は必要ない。 $j$番目まで見たとき次に$Y$に所属させる要素$s_k$を決めて開区間$(j, k)$の中は全て$X$に所属させるようにすると、これで$\mathrm{dp} : 2 \times (N+1) \to 10^9+7$とできて$O(N^2)$。 その更新はとりあえず書いてみて眺めれば容易に高速化でき、$O(N)$。

implementation

l_l > l_rな場合で無限にWAを出した。

#include <array>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

constexpr int mod = 1e9+7;
int main() {
    // input
    int n; ll a, b; scanf("%d%lld%lld", &n, &a, &b);
    vector<ll> s(n); repeat (i, n) scanf("%lld", &s[i]);
    if (a > b) swap(a, b);
    // solve
    s.insert(s.begin(), s.front() - a - b);
    s.insert(s.end(),   s.back()  + a + b);
    s.insert(s.end(),   s.back()  + a + b);
    vector<array<int, 2> > dp(n + 2);
    vector<int> acc(dp.size() + 1);
    dp[0][0] = 1;
    acc[1] = 1;
    int l_l = 0, l_r = 0;
    repeat_from (r, 1, dp.size()) {
        while (l_r < r - 1 and s[l_r] + b <= s[r]) ++ l_r;
        if (l_l <= l_r) {
            dp[r][0] = (acc[l_r] - acc[l_l] +(ll) mod) % mod;
        }
        if (not (s[r - 1] + a <= s[r])) l_l = r - 1;
        dp[r][1] = (s[r - 1] + b <= s[r]) ? (dp[r - 1][0] + dp[r - 1][1]) % mod : 0;
        acc[r + 1] = (0ll + acc[r]
                + (s[r - 1] + a <= s[r + 1] ? dp[r][0] : 0)
                + dp[r][1] ) % mod;
    }
    // output
    int result = (dp[n + 1][0] + dp[n + 1][1]) % mod;
    printf("%d\n", result);
    return 0;
}


AtCoder Beginner Contest 070: D - Transit Tree Path

,

http://abc070.contest.atcoder.jp/tasks/abc070_d

LCAを貼りかけた。だめ。

solution

答えは$d(x_j, K) + d(K, y_j)$。 頂点$K$からの最短経路長を全て求めておけばよい。Dijkstraでもよいが、木なのでDPでもできる。 $O(N + Q)$。

implementation

#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;

int main() {
    int n; scanf("%d", &n);
    vector<vector<pair<int, int> > > g(n);
    repeat (i, n - 1) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c); -- a; -- b;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    int q, k; scanf("%d%d", &q, &k); -- k;
    vector<ll> dist(n, -1);
    function<void (int)> go = [&](int i) {
        for (auto e : g[i]) {
            int j, cost; tie(j, cost) = e;
            if (dist[j] != -1) continue;
            dist[j] = dist[i] + cost;
            go(j);
        }
    };
    dist[k] = 0;
    go(k);
    while (q --) {
        int x, y; scanf("%d%d", &x, &y); -- x; -- y;
        printf("%lld\n", dist[x] + dist[y]);
    }
    return 0;
}



AtCoder Beginner Contest 070: A - Palindromic Number

,

http://abc070.contest.atcoder.jp/tasks/abc070_a

固定文字列出力する部分はつまらんって言って雑に書くの毎回やってる気がする。

implementation

#!/usr/bin/env bf
,>,,[<->-]+
<[>-
    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-] N
    +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-] o
]>[-
    +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-] Y
    +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-] e
    +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-] s
]>
++++++++++. newline

AtCoder Grand Contest 006: D - Median Pyramid Hard

,

http://agc006.contest.atcoder.jp/tasks/agc006_d

多くの部分で定数倍高速化$O(N^2)$を試みたが、最良でも$5$倍足りずでだめだった。

solution

答えに関して二分探索。 答え$a_k \ge L$だとすると、$b_i = (a_i \ge L) \in \{ 0, 1 \}$だとして同様に作ったピラミッドの頂点も$1$であるはず。 $0, 1$なら答えは$O(N)$で求められる。 $n - 1 \equiv 0 \pmod{2}$にしておいて$2$回ずつmedianを取るように考えると楽。 全体で$O(N \log N)$。

implementation

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

int median(int a, int b, int c) {
    if (a > b) swap(a, b);
    return max(a, min(b, c));
}

template <typename UnaryPredicate>
int binsearch(int l, int r, UnaryPredicate p) { // [l, r), p is monotone
    assert (l < r);
    -- l;
    while (r - l > 1) {
        int m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x in [l, r) | p(x) }, or r
}

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(2 * n - 1);
    repeat (x, 2 * n - 1) {
        scanf("%d", &a[x]);
    }
    // solve
    if ((n - 1) % 2 == 1) {
        vector<int> b(2 * n - 3);
        repeat (x, 2 * n - 3) {
            b[x] = median(a[x], a[x + 1], a[x + 2]);
        }
        a.swap(b);
        -- n;
    }
    int result = binsearch(1, 2 * n, [&](int limit) {
        vector<char> b(2 * n - 1);
        repeat (x, 2 * n - 1) {
            b[x] = a[x] > limit;
        }
        int result = b[n - 1];
        int dist = 2 * n;
        repeat (x, (2 * n - 1) - 2) {
            if ((b[x] != b[x + 1] and b[x + 1] == b[x + 2])
                    or (b[x] == b[x + 1] and b[x + 1] != b[x + 2])) {
                int ndist = abs((x + 1) - (n - 1));
                if (ndist < dist) {
                    dist = ndist;
                    result = b[x + 1];
                }
            }
        }
        return not result;
    });
    // output
    printf("%d\n", result);
    return 0;
}

AtCoder Grand Contest 006: B - Median Pyramid Easy

,

http://agc006.contest.atcoder.jp/tasks/agc006_b

solution

同じ数字がふたつ並ぶともうそれは変化しない。 ピラミッドの中央に目標の$x$でそのようなものを作ればよい。 これは$x + 2, x - 1, x, x + 1, x - 2$などと並べればできる。$O(N)$。

implementation

#!/usr/bin/env python3
n, x = map(int,input().split())
assert n >= 2
if x == 1 or x == 2 * n - 1:
    print('No')
else:
    a = [ x - 1, x, x + 1 ]
    b = list(range(1, x - 1)) + list(range(x + 2, 2 * n))
    c = b[n - 2 :] + a + b[: n - 2]
    print('Yes')
    print(*c, sep='\n')

TopCoder SRM 719 Div1 Medium: OwaskiAndTree

,

問題文中に Overwatch って単語が出てきてなんだっけとぐぐったら固有名詞 (ゲーム名)だった。

problem

頂点に重みの付いた木上を歩く。 始めて訪ずれたときその重み分の点数を得る。点数が負になる場合は$0$に戻す。 根から始めて自由な位置で終了してよい。 点数の最大値を求めよ。

solution

$0$に戻さない場合の値は木DPで明らか。 $0$に戻す操作は途中で負にすることを許してちょうど$1$回だけ行なうと見做せ、それをした後は戻さない場合のDPから求まる。そのようにすると木の根と葉全ての間のcutを決めてその下側だけ$0$に戻す操作なしで自由に使った場合の最大値になるので、これを木DP。$O(N)$。

implementation

$2$回走らせてる再帰は明らかに融合できる。

#include <bits/stdc++.h>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
class OwaskiAndTree { public: int maximalScore(vector<int> parent, vector<int> pleasure); };

constexpr int root = 0;
int OwaskiAndTree::maximalScore(vector<int> parent, vector<int> pleasure) {
    int n = pleasure.size();
    vector<vector<int> > children(n);
    repeat (i, n - 1) {
        children[parent[i]].push_back(i + 1);
    }
    vector<ll> acc(n); {
        function<void (int)> go = [&](int i) {
            acc[i] += pleasure[i];
            for (int j : children[i]) {
                go(j);
                if (acc[j] > 0) {
                    acc[i] += acc[j];
                }
            }
        };
        go(root);
    }
    vector<ll> dp(n); {
        function<void (int)> go = [&](int i) {
            for (int j : children[i]) {
                go(j);
                dp[i] += dp[j];
            }
            setmax(dp[i], acc[i]);
            setmax(dp[i], 0ll);
        };
        go(root);
    }
    return dp[root];
}

TopCoder SRM 719 Div1 Easy: LongMansionDiv1

,

問題文がこどふぉのように難しい。 どうでもいいストーリーを付けるな。 $x$-th rowと$y$-th columnなのをやめろ。

solution

あるrowを選んで$y$方向の移動はすべてそこで行うようにする。選ぶrowについて総当たり。$O(N)$。

implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(x) begin(x), end(x)
typedef long long ll;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
class LongMansionDiv1 { public: long long minimalTime(vector<int> t, int sX, int sY, int eX, int eY); };

constexpr ll inf = ll(1e18)+9;
ll LongMansionDiv1::minimalTime(vector<int> t, int sX, int sY, int eX, int eY) {
    int w = t.size();
    vector<int> acc(w + 1);
    partial_sum(whole(t), acc.begin() + 1);
    ll result = inf;
    repeat (x, w) {
        ll it = 0;
        it += acc[max(x, sX) + 1] - acc[min(x, sX)];
        it += acc[max(x, eX) + 1] - acc[min(x, eX)];
        it += t[x] *(ll) (abs(eY - sY) - 1);
        setmin(result, it);
    }
    return result;
}

AtCoder Grand Contest 010: F - Tree Game

,

http://agc010.contest.atcoder.jp/tasks/agc010_f

後輩が$700$点ぐらいだって言ってた。そう聞いてから解いたらそうだった。

solution

有向木にして始点ごとにDFS。$O(N^2)$。メモ化すれば$O(N)$だが不要。

頂点$i - j$が隣接していて$A_i \le A_j$だとしよう。 駒が$i$にあるときに$j$に動かすと、相手の番で$i$に戻されて$A_i-1 \le A_j-1$という状況になる。 これは繰り返せば自分が負ける。 つまり駒を石の数の減少する方向に動かせなければ負け。 逆に$A_i \gt A_j$であれば(相手が$i$に駒を戻すなら)これは勝ちとなる。

よって辺$i - j$を$A_i, A_j$の比較によって向きを付け、交互に動かして葉に辿り付いた方が負け。 これは$O(N)$のDFSで解ける。 始点については総当たりしても間に合う。

implementation

#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
    vector<vector<int> > g(n);
    repeat (i, n - 1) {
        int x, y; scanf("%d%d", &x, &y); -- x; -- y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    // solve
    function<bool (int)> go = [&](int i) {
        for (int j : g[i]) if (a[i] > a[j]) {
            if (not go(j)) {
                return true;
            }
        }
        return false;
    };
    vector<int> result;
    repeat (i, n) if (a[i]) {
        if (go(i)) {
            result.push_back(i);
        }
    }
    // output
    repeat (i, result.size()) {
        printf("%d%c", result[i] + 1, i + 1 == result.size() ? '\n' : ' ');
    }
    return 0;
}

AtCoder Grand Contest 007: A - Shik and Stone

,

http://agc007.contest.atcoder.jp/tasks/agc007_a

$1$WA。

solution

#の数が$H + W - 1$に一致するか見る。$O(HW)$。

implementation

#!/usr/bin/env python3
def solve(h, w, a):
    b = []
    b += [ '.' * (w + 2) ]
    b += [ '.' + row + '.' for row in a ]
    b += [ '.' * (w + 2) ]
    y, x = 1, 1
    while (y, x) != (h, w):
        if b[y - 1][x] == b[y][x - 1] == '#':
            return False
        if b[y + 1][x] == b[y][x + 1] == '#':
            return False
        if b[y + 1][x] == '#':
            y += 1
        elif b[y][x + 1] == '#':
            x += 1
        else:
            return False
    return True
h, w = map(int, input().split())
a = [ input() for _ in range(h) ]
print(['Impossible', 'Possible'][solve(h, w, a)])

CS Academy Round #41: F. Subset Trees

,

https://csacademy.com/contest/archive/task/subset-trees

区間を右端でソートしていたため通せなかった。

problem

閉区間が$N$個与えられる。 その部分集合に対し、区間を頂点とし端点含む交差がある区間どうしに辺を張りグラフを作る。 このグラフが木となるような部分集合はいくつあるか。

solution

DP。 区間の集合を固定すれば各点で重複度のようなものを考えられて、これが$3$になってはいけない。 左から順に決めていくとして、区間の集合に対しその重複度が$2$な点と$1$な点で最も右のものそれぞれ$l, r$が考えられる。 $\mathrm{dp}(l, r)$をそのような区間の集合の数として求める。 $w = \max r_i$として$O(w^2 \log w)$。

区間は左端でソートする。 右端だと$[1, 2], [3, 4], [2, 5]$みたいなケースでだめ。

愚直に書くと$O(w^3)$になるが、適当にやれば$O(w^2 \log w)$にできる。 ただしsegment treeを使うとTLEした。 binary indexed treeだと$2, 3$倍速くなって通る。 座圧しても回避できるはず。

implementation

#include <algorithm>
#include <cstdio>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

template <typename Monoid>
struct binary_indexed_tree { // on monoid
    typedef typename Monoid::underlying_type underlying_type;
    vector<underlying_type> data;
    Monoid mon;
    binary_indexed_tree(size_t n, Monoid const & a_mon = Monoid()) : mon(a_mon) {
        data.resize(n, mon.unit());
    }
    void point_append(size_t i, underlying_type z) { // data[i] += z
        for (size_t j = i + 1; j <= data.size(); j += j & -j) data[j - 1] = mon.append(data[j - 1], z);
    }
    underlying_type initial_range_concat(size_t i) { // sum [0, i)
        underlying_type acc = mon.unit();
        for (size_t j = i; 0 < j; j -= j & -j) acc = mon.append(data[j - 1], acc);
        return acc;
    }
    underlying_type range_concat(size_t l, size_t r) {
        return mon.append(initial_range_concat(r), mon.invert(initial_range_concat(l)));
    }
};
template <int mod>
struct modplus_t {
    typedef int underlying_type;
    int unit() const { return 0; }
    int append(int a, int b) const { int c = a + b; return c < mod ? c : c - mod; }
    int invert(int a) const { return a ? mod - a : 0; }
};

constexpr int mod = 1e9+7;
int main() {
    int n; scanf("%d", &n);
    vector<int> l(n), r(n); // [l, r]
    repeat (i, n) {
        scanf("%d%d", &l[i], &r[i]);
    }
    { // sort of SoA
        vector<pair<int, int> > lrs(n);
        repeat (i, n) {
            lrs[i] = { l[i], r[i] };
        }
        sort(whole(lrs));
        repeat (i, n) {
            tie(l[i], r[i]) = lrs[i];
        }
    }
    const int max_r = *max_element(whole(r));
    auto dp = vectors(max_r + 1, binary_indexed_tree<modplus_t<mod> >(max_r + 1));
    repeat (i, n) {
        repeat_from (r_j, l[i], max_r + 1) {
            dp[max(r[i], r_j)].point_append(min(r[i], r_j), dp[r_j].range_concat(0, l[i]));
        }
        dp[r[i]].point_append(0, 1);
    }
    ll result = 0;
    repeat (r_j, max_r + 1) {
        result += dp[r_j].range_concat(0, r_j + 1);
    }
    printf("%d\n", int(result % mod));
    return 0;
}

元々のDP

    auto dp = vectors(max_r + 1, max_r + 1, ll());
    repeat (i, n) {
        repeat (l_j, l[i]) {
            repeat_from (r_j, l[i], max_r + 1) {
                dp[min(r[i], r_j)][max(r[i], r_j)] += dp[l_j][r_j];
            }
        }
        dp[0][r[i]] += 1;
    }
    ll result = 0;
    repeat (r_j, max_r + 1) {
        repeat (l_j, r_j + 1) {
            result += dp[l_j][r_j];
        }
    }

CS Academy Round #41: E. Candles

,

https://csacademy.com/contest/round-41/task/candles/

これを解いた時点では全体$8$位で日本人内だとuwiさんやantaさんを下して$1$位だった。 思わずスクリーンショット取ってしまった。

その後はFが解けなかったのでもちろん抜かれたが、rating +84して赤色になった。CSAの赤の価値は分からないにせよ始めての赤。嬉しい。

problem

長さ$h_i$を持ったろうそくがいくつかある。 毎晩$c_j$本のろうそくを灯し、使われたろうそくは長さが$1$減る。 灯せなかったらそこで終了。最大何日灯せるか。

solution

常にろうそくを長い順に$c_j$個使うのが最適。 遅延伝播segment木をいい感じに使って$O(N \log N + M (\log N)^2)$

単純にやると$O(MN \log N)$であり、定数倍高速化はかなり厳しそう。 区間へのクエリであるのでsegment木が思い出されるが、sortはなおも必要。 ここで減少量が常に$1$であることを使う。 引いた後のsortは元々同じ数だった区間を反転させるだけなので、操作する区間を分けて反転を不要にする。 例えば112222333という列から$5$個使うなら1122*****と引いて112211222とするのではなく11**22***と引けば111122222。 諸々の位置は二分探索する。

ついでに、減少量が常に$K$以下と一般化された場合は実質的に上を$K$回やることになりそう。 気合いで細かく実装して定数倍改善はあるだろうけれど。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;

template <class OperatorMonoid>
struct dual_segment_tree {
    typedef OperatorMonoid monoid_type;
    typedef typename OperatorMonoid::underlying_type operator_type;
    typedef typename OperatorMonoid::target_type underlying_type;
    int n;
    vector<operator_type> f;
    vector<underlying_type> a;
    OperatorMonoid op;
    dual_segment_tree() = default;
    dual_segment_tree(int a_n, underlying_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(n, initial_value);
        f.resize(n-1, op.unit());
    }
    underlying_type point_get(int i) { // 0-based
        underlying_type acc = a[i];
        for (i = (i+n)/2; i > 0; i /= 2) { // 1-based
            acc = op.apply(f[i-1], acc);
        }
        return acc;
    }
    void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            if (i < f.size()) {
                f[i] = op.append(z, f[i]);
            } else {
                a[i-n+1] = op.apply(z, a[i-n+1]);
            }
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2*i+1, il, (il+ir)/2, 0, n, f[i]);
            range_apply(2*i+2, (il+ir)/2, ir, 0, n, f[i]);
            f[i] = op.unit();
            range_apply(2*i+1, il, (il+ir)/2, l, r, z);
            range_apply(2*i+2, (il+ir)/2, ir, l, r, z);
        }
    }
};
struct plus_operator_t {
    typedef int underlying_type;
    typedef int target_type;
    int unit() const { return 0; }
    int append(int a, int b) const { return a + b; }
    int apply(int a, int b) const { return a + b; }
};

template <typename UnaryPredicate>
ll binsearch(ll l, ll r, UnaryPredicate p) { // [l, r), p is monotone
    -- l;
    while (r - l > 1) {
        ll m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x in [l, r) | p(x) }, or r
}

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<int> h(n); repeat (i, n) scanf("%d", &h[i]);
    vector<int> c(m); repeat (i, m) scanf("%d", &c[i]);
    // solve
    sort(whole(h));
    dual_segment_tree<plus_operator_t> segtree(n, 0);
    repeat (i, n) {
        segtree.range_apply(i, i + 1, h[i]);
    }
    int result = 0;
    for (; result < m; ++ result) {
        int c_i = c[result];
        int k = segtree.point_get(n - c_i);
        if (k == 0) break;
        int l = binsearch(0, n - c_i, [&](int j) {
            return segtree.point_get(j) >= k;
        });
        int r = binsearch(n - c_i, n, [&](int j) {
            return segtree.point_get(j) > k;
        });
        segtree.range_apply(r, n, -1);
        segtree.range_apply(l, l + (c_i - (n - r)), -1);
    }
    // output
    printf("%d\n", result);
    return 0;
}

CS Academy Round #41: D. BFS-DFS

,

https://csacademy.com/contest/round-41/task/bfs-dfs/

発想。

problem

BFSをしたときの頂点列とDFSをしたときの頂点列が通り掛け順で見て与えられるので、そのようになるグラフをひとつ出力せよ。 ただし辺の出力順によってBFS/DFSの結果は変化することに注意。

solution

ほとんど車輪なものを作る。 始点とその次の頂点は一致していないとおかしいので、そうだとする。 DFSの順に$1$本の道を張り、その後にBFSの順に始点から辺を張ればよい。 $O(N)$。

implementation

#!/usr/bin/env python3
n = int(input())
bfs = list(map(int, input().split()))
dfs = list(map(int, input().split()))
if bfs[: 2] != dfs[: 2]:
    print(-1)
else:
    print(2 * n - 3)
    for i in range(n - 1):
        print(dfs[i], dfs[i + 1])
    for i in range(2, n):
        print(bfs[0], bfs[i])