Codeforces Round #361 (Div. 2) D. Friends and Subsequences

問題文

http://codeforces.com/contest/689/problem/D

問題概要

長さ N の数列 A, B が与えられる．
max{A(l), ..., A(r)} = min{B(l), ... B(r)} となる (l, r) (l <= r) は何組存在するか求めよ．

・制約
1 <= N <= 200000

解法

Sparse table を書いてみたのでそのテストに使った．なので Sparse table で解く．
まず適当に l を定めて，条件を満たす右端の範囲を二分探索で求める．
l を定めたときに，l を左端として条件を満たすものが存在する可能性がなければ continue する．
存在しうるなら
l2 で初めて max{A(l), ..., A(l2)} >= min{B(l), ..., B(l2)}，
r2 で初めて max{A(l), ..., A(r2)} > min{B(l), ..., B(r2)}
となる l2 と r2 を2分探索で求めると，r2 - l2 + 1がそのときの答えになる．
あとは全ての l に対して足し合わせる．

計算量は O(NlogN)

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct rmq1 { // min
    using type = int;
    static bool comp(type const& l, type const& r) {
        return l < r;
    }
};

struct rmq2 { // max
    using type = int;
    static bool comp(type const& l, type const& r) {
        return l > r;
    }
};

template<typename Policy>
class rmq_sparse_table {
    using T = typename Policy::type;

public:
    rmq_sparse_table(std::vector<T> const& v)
        : a(v), n(v.size()), log_n(v.size()+1)
    {
        for(int i=2; i<n+1; ++i) {
            log_n[i] = log_n[i >> 1] + 1;
        }

        table = std::vector<std::vector<int>>(n, std::vector<T>(log_n[n] + 1));
        for(int i=0; i<n; ++i) {
            table[i][0] = i;
        }
        for(int k=1; (1<<k) <= n; ++k) {
            for(int i=0; i + (1 << k) <= n; ++i) {
                int first = table[i][k-1],
                    second = table[i + (1 << (k-1))][k-1];
                if(Policy::comp(a[first], a[second])) {
                    table[i][k] = first;
                } else {
                    table[i][k] = second;
                }
            }
        }
    }

    // [l..r]
    int query(int l, int r) {
        int k = log_n[r - l + 1];
        if(Policy::comp(a[table[l][k]], a[table[r - (1 << k) + 1][k]])) {
            return table[l][k];
        } else {
            return table[r - (1 << k) + 1][k];
        }
    }

private:
    const int n;
    std::vector<int> log_n;
    std::vector<T> a;
    std::vector<std::vector<int>> table;
};


int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for(int i=0; i<N; ++i) {
        scanf("%d", &A[i]);
    }
    for(int i=0; i<N; ++i) {
        scanf("%d", &B[i]);
    }
    rmq_sparse_table<rmq1> st1(B);
    rmq_sparse_table<rmq2> st2(A);
    ll res = 0;
    for(int i=0; i<N; ++i) {
        if(A[i] > B[i] || A[st2.query(i, N-1)] < B[st1.query(i, N-1)]) {
            continue;
        }
        int l = i-1, r = N-1;
        while(r - l > 1) {
            int m = (r + l) / 2;
            if(A[st2.query(i, m)] < B[st1.query(i, m)]) {
                l = m;
            } else {
                r = m;
            }
        }
        const int l2 = r;
        if(A[st2.query(i, l2)] != B[st1.query(i, l2)]) {
            continue;
        }

        l = i, r = N;
        while(r - l > 1) {
            int m = (l + r) / 2;
            if(A[st2.query(i, m)] <= B[st1.query(i, m)]) {
                l = m;
            } else {
                r = m;
            }
        }
        const int r2 = l;
        res += (r2 - l2 + 1);
    }

    cout << res << endl;
}

AOJ 2726 Black Company

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2726

問題概要

N 人の従業員がいて，それぞれ成果を c(i) あげたとする．成果に応じて，報酬 p(i) を分配する．
ただし，それぞれの従業員には親しい人が何人か存在する．
従業員 i が j と親しいときは，以下を満たすように p(i)，p(j) を定める．

• c(i) < c(j) ならば p(i) < p(j)
• c(i) > c(j) ならば p(i) > p(j)
• c(i) == c(j) ならば p(i) == p(j)

また，i と j が親しく，かつ i と k が親しいときは，j と k に対しても上と同じ条件を満たす必要がある．（ただしこの時は，j と k は親しいとは言わない．ただ条件を満たす必要があるだけ．もちろん j と k がもともと親しい場合もある．）
このような条件をみたすように，従業員に払う給料の総額を最小化せよ．

1 <= N <= 10^5
0 <= M <= 2 * 10^5
1 <= c(i) <= 10^5

解法

この手の，「a は b よりある順序関係のもとで"小さい"」を表現するのは，a -> b と辺を張るのがよくあるやり方だが，この問題もそのようにやる．
直接親しい場合は入力を受け取ったときに辺を張ればよい．
間接的に条件を満たす必要がある人は，ある人 i を定めたときに，隣接している人をすべて列挙して，成果順にソートし（ソートした後の人の集合を adj(i) で表す），adj(i)(j) -> adj(i)(j+1) と辺を張ればよい．
あとはこのグラフ上で，最も成果が小さい人から順に，給料を 1, 2, ... と定めていくだけ．これは配るDPのイメージでできる．

さて，問題になるのは，同じ成果を上げた人が存在し，かつ条件を満たす必要がある場合だが，この場合は，辺を張る代わりに，その頂点を縮約してしまえばよい．
縮約には union-find 木を使うと楽で，縮約前のサイズ分 dp で求めた値に掛けて加えてやればOK．

計算量はソートが一番大きくて，O(NlogN + VlogV)．(それと定数倍)

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using P = pair<int, int>;
using ll = long long;
 
class union_find {
public:
    union_find(int n)
        : par_(n, -1)
    {}
    void init(int n) {
        par_.assign(n, -1);
    }
 
    int root(int x) {
        return par_[x] < 0 ? x : par_[x] = root(par_[x]);
    }
 
    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) {
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }
 
    bool same(int x, int y) {
        return root(x) == root(y);
    }
 
    int size(int x) {
        return -par_[root(x)];
    }
 
private:
    std::vector<int> par_;
};
 
int main() {
    int N;
    cin >> N;
    vector<int> c(N);
    for(int i=0; i<N; ++i) {
        cin >> c[i];
    }
    int M;
    cin >> M;
    union_find uf(N);
    vector<vector<int>> g(N);
    vector<vector<P>> next(N);
    for(int i=0; i<M; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(c[a] > c[b]) {
            g[b].push_back(a);
        } else if(c[a] < c[b]) {
            g[a].push_back(b);
        } else {
            uf.unite(a, b);
        }
        next[a].emplace_back(c[b], b);
        next[b].emplace_back(c[a], a);
    }
 
    for(int i=0; i<N; ++i) {
        if(next[i].size() == 0) {
            continue;
        }
        sort(next[i].begin(), next[i].end());
        for(int j=0; j<next[i].size()-1; ++j) {
            P u = next[i][j], v = next[i][j+1];
            if(u.first == v.first) {
                uf.unite(u.second, v.second);
            } else {
                g[u.second].push_back(v.second);
            }
        }
    }
 
    vector<int> order;
    vector<ll> dp(N);
    for(int i=0; i<N; ++i) {
        if(uf.root(i) == i) {
            order.push_back(i);
            dp[i] = 1;
        } else {
            for(auto& v : g[i]) {
                g[uf.root(i)].push_back(v);
                g[i].clear();
            }
        }
    }
    sort(order.begin(), order.end(), [&](int const v1, int const v2) {
        return c[v1] < c[v2];
    });
    ll res = 0;
    for(auto i : order) {
        for(auto to : g[i]) {
            dp[uf.root(to)] = max(dp[uf.root(to)], dp[i] + 1);
        }
        res += dp[i] * uf.size(i);
    }
    cout << res << endl;
}

AOJ 2680 LR

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2680

解法

メモ化再帰．memo[l][r] で，s[l..r]の取りうる最大値，もし無ければ "invalid" を入れていく．
完全に数字に置き換えられるならそうして(当然それが最適)，そうじゃないならLかRなので，カンマの位置を全探索して2つに分け，それらを再帰的にとくとよい．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
string memo[51][51];
 
string max(string const& a, string const& b) {
    if(a == "invalid") {
        return b;
    }
    if(a.size() > b.size()) {
        return a;
    } else if(a.size() < b.size()) {
        return b;
    } else {
        return (a < b ? b : a);
    }
}
 
string number(int l, int r, string const& s) {
    if(l < r && s[l] == '0') {
        return "invalid";
    }
    string res;
    for(int i=l; i<=r; ++i) {
        if(s[i] != '?' && !isdigit(s[i])) {
            return "invalid";
        }
        res += s[i] == '?' ? '9' : s[i];
    }
    return res;
}
 
string solve(int l, int r, string const& s) {
    string& res = memo[l][r];
    if(res != "") {
        return res;
    }
    res = number(l, r, s);
    if(res != "invalid") {
        return res;
    }
    if(s[l+1] != '(' && s[l+1] != '?') {
        return "invalid";
    }
    if(s[r] != ')' && s[r] != '?') {
        return "invalid";
    }
    for(int i=l+3; i<=r-2; ++i) {
        if(s[i] != ',' && s[i] != '?') {
            continue;
        }
        string l_max = solve(l+2, i-1, s),
               r_max = solve(i+1, r-1, s);
        if(l_max == "invalid" || r_max == "invalid") {
            continue;
        }
        if(s[l] == 'L' || s[l] == '?') {
            res = max(res, l_max);
        }
        if(s[l] == 'R' || s[l] == '?') {
            res = max(res, r_max);
        }
    }
    return res;
}
 
int main() {
    string s;
    cin >> s;
    cout << solve(0, s.size()-1, s) << endl;
}

AOJ 2710 An Equation in a Mine

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2710

解法

区間DP（メモ化再帰）．
ある演算子に注目して，左と右に分けて，再帰的に処理していくとよい．
演算子が + であれば，左も右も最大値を取るようにすればよい．-であれば，左を最大に，右を最小にすればよい．
つまり，ある区間に対して最大値と最小値の両方が必要である．

気をつける必要があるのは，(n) のように，一つの数字だけを括弧で囲えないということ．たとえば 1 - (2 + 3 + 4) の場合，1つ目の + に注目すると "1 - (2" と "3 + 4)" に分かれる．左を更に分解すると "1" と "(2" になるが，"(2" はどうやっても条件を満たさないのでダメ．
つまり "1 + (2" とか "3) + 4" みたいな形になるような分解は不可能ということ．逆に，それ以外はいい感じにカッコを書けば可能．（例えば "(1 + 2" は一番右に")"を付け加えればOKなので，こういう場合はある演算子で分解する前に "1 + 2" も計算しておくようにすればいい．）
これに注意してメモ化再帰を書く．

計算量は O(N^3)．かな．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using P = pair<int, int>;

constexpr int INF = 1e9;

P memo[201][201];

P rec(int l, int r, string const& s) {
    P& res = memo[l][r];
    if(res != P{-INF, INF}) {
        return res;
    }
    if(l == r) {
        int v = s[l] - '0';
        return res = make_pair(v, v);
    }
    if(s[l] == '(' && r-l >= 3) {
        P p = rec(l+1, r, s);
        res.first = max(res.first, p.first);
        res.second = min(res.second, p.second);
    }
    if(s[r] == ')' && r-l >= 3) {
        P p = rec(l, r-1, s);
        res.first = max(res.first, p.first);
        res.second = min(res.second, p.second);
    }
    for(int i=l+1; i<r; ++i) {
        char op = s[i];
        if(op == '+' || op == '-') {
            P rl = rec(l, i-1, s);
            P rr = rec(i+1, r, s);
            if(op == '+') {
                res.first = max(res.first, rl.first + rr.first);
                res.second = min(res.second, rl.second + rr.second);
            } else {
                res.first = max(res.first, rl.first - rr.second);
                res.second = min(res.second, rl.second - rr.first);
            }
        }
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    for(int i=0; i<s.size(); ++i) {
        for(int j=0; j<s.size(); ++j) {
            memo[i][j] = make_pair(-INF, INF);
        }
    }
    cout << rec(0, s.size()-1, s).first << endl;
}

AOJ 2741 Invisible

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2741

解法

メモ化再帰で解ける．
memo[si][sj][i][j][turn][pass] := a(si)からa(i-1)，b(sj)からb(j-1)までスタックに積まれていて，手番がturnかつパスの状態がpassであるときの最大値．(pass == 1 ならば，スタックが空の状態で一回パスされたことを表す)

先攻は score_a - score_b が最大になるように，後攻は最小になるようにする．

パスしたときに何点入るかだが，よく考えてみると，スタックにある a のカードと b のカードの枚数の差は高々1枚であるので，丁寧に場合分けすると得点が計算できる．(累積和使ったほうがスッキリしたかも？)
あとは普通に遷移を書くだけ．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1e9;

int N, M;
int memo[51][51][51][51][2][2];
vector<int> a, b;

int calc(int si, int sj, int i, int j, int turn) {
    int score_a = 0, score_b = 0;
    if(turn == 0) {
        if(i - si < j - sj) {
            if(b[sj] != -1) {
                score_b = b[sj];
            }
            sj += 1;
        }
        for(int k=0; k<i-si; ++k) {
            if(a[si+k] == -1) {
                score_b = 0;
            } else {
                score_a += a[si+k];
            }
            if(b[sj+k] == -1) {
                score_a = 0;
            } else {
                score_b += b[sj+k];
            }
        }
    } else {
        if(j-sj < i-si) {
            if(a[si] != -1) {
                score_a = a[si];
            }
            si += 1;
        }
        for(int k=0; k<i-si; ++k) {
            if(b[sj+k] == -1) {
                score_a = 0;
            } else {
                score_b += b[sj+k];
            }
            if(a[si+k] == -1) {
                score_b = 0;
            } else {
                score_a += a[si+k];
            }
        }
    }
    return score_a - score_b;
}

// [si, i), [sj, j)
int dp(int si, int sj, int i, int j, int turn, int pass) {
    int& r = memo[si][sj][i][j][turn][pass];
    if(r != INF) {
        return r;
    }
    if(turn == 0) {
        r = -INF;
        if(pass == 1) {
            r = max(r, 0);
        } else {
            r = max(r, dp(i, j, i, j, 1, (i == si && j == sj)) + calc(si, sj, i, j, 0));
        }
        if(i < N) {
            r = max(r, dp(si, sj, i+1, j, 1, 0));
        }
    } else {
        r = INF;
        if(pass == 1) {
            r = min(r, 0);
        } else {
            r = min(r, dp(i, j, i, j, 0, (i == si && j == sj)) + calc(si, sj, i, j, 1));
        }
        if(j < M) {
            r = min(r, dp(si, sj, i, j+1, 0, 0));
        }
    }
    return r;
}

int main() {
    cin >> N >> M;
    a.resize(N);
    b.resize(M);
    for(int i=0; i<N; ++i) {
        cin >> a[i];
    }
    for(int i=0; i<M; ++i) {
        cin >> b[i];
    }
    fill(memo[0][0][0][0][0], memo[50][50][50][50][2], INF);
    cout << dp(0, 0, 0, 0, 0, 0) << endl;
}

AOJ 0575 Festivals in JOI Kingdom

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575

解法

実装できなかったので，eagletmt さんの解法を参考にした．
AOJ 0575 - Festivals in JOI Kingdom - プログラミングコンテストの記録

使うアルゴリズムとしては，DijkstraとKruskal，LCAの3つ．
まず，各街がお祭りをする街からどれくらい離れているかは，Dijkstra法で求められる．
街 i がお祭りしている街から離れている距離を d[i] とする．
次に，与えられたグラフ上の辺 e = (u, v) のコストを min(d[u], d[v]) と改める．
こうしてできたグラフ上で最大全域木問題（つまり辺のコストが大きい方から追加していく）を解く．これで木ができる．
すると，任意の2つの街 u, v の組に対し，u から v への移動の際には今構築した最大全域木上を動けば良いことがわかる．
あとは u から v へのパスのなかで一番値が小さいものを効率よく求められれば良い．

ここで，最大全域木を構築するときに工夫をすると，LCAでそれが楽に求められる．
Union-find木で街 u と 街 v を合併していくわけだが，この過程を木として残しておく．
これは，合併の度に新しいノード new_v を作ることで実現する．街 u と 街 v の合併のとき，ru = uf.root(u) と rv = uf.root(v) を，その新しいノード new_v にしてしまう．この際，new_v には，min(d[ru], d[rv]) を持たせておく．
そして，new_v から ru, rv に対し有向辺を張れば，これはまた木になっている．
各クエリは，こうしてできた木にたいして lca を求め，その値を出力すれば良い．

計算量は（ネックになるやつだけ見ると） O(ElogV + ElogE + QlogN) ．

手元で試すとスタックオーバーフローした．AOJだといけた．割りとギリギリ．
自分の書き方だとメモリ効率が悪くなってるかもしれない．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using P = pair<int, int>;

// コードが長いので，union_find は省略

struct edge {
    int from, to, cost;
    bool operator<(edge const& other) const {
        return cost > other.cost;
    }
};

using edges = vector<edge>;
using graph = vector<edges>;


class lca {
public:
    lca(vector<vector<int>>& g, int root)
        : V(g.size()),
          log_V(0),
          depth_(V, 0)
    {
        for(int v=V; v>0; v /= 2) {
            ++log_V;
        }
        parent.assign(log_V, std::vector<int>(V, 0));
        dfs(g, root, -1, 0);
        for(int k=0; k+1 < log_V; ++k) {
            for(int v=0; v<V; ++v) {
                if(parent[k][v] < 0) {
                    parent[k+1][v] = -1;
                } else {
                    parent[k+1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    void dfs(vector<vector<int>> const& g, int v, int p, int d) {
        parent[0][v] = p;
        depth_[v] = d;
        for(int i=0; i<g[v].size(); ++i) {
            if(g[v][i] != p) {
                dfs(g, g[v][i], v, d+1);
            }
        }
    }

    int depth(int v) const {
        return depth_[v];
    }

    int query(int u, int v) {
        if(depth_[u] > depth_[v]) {
            std::swap(u, v);
        }
        for(int k=0; k<log_V; ++k) {
            if((depth_[v] - depth_[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if(u == v) {
            return u;
        }
        for(int k=log_V - 1; k>=0; --k) {
            if(parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

private:
    int V, log_V;
    std::vector<vector<int>> parent;
    std::vector<int> depth_;
};


constexpr int INF = 1e9;

int main() {
    int N, M, K, Q;
    cin >> N >> M >> K >> Q;
    graph g(N);
    for(int i=0; i<M; ++i) {
        int a, b, l;
        cin >> a >> b >> l;
        a--; b--;
        g[a].push_back((edge){a, b, l});
        g[b].push_back((edge){b, a, l});
    }

    vector<int> d(2*N, INF);
    priority_queue<P, vector<P>, greater<P>> que;
    for(int i=0; i<K; ++i) {
        int f;
        cin >> f;
        f--;
        d[f] = 0;
        que.push(make_pair(0, f));
    }
    while(!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first) {
            continue;
        }
        for(auto& e : g[v]) {
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }

    edges es;
    for(int i=0; i<N; ++i) {
        for(auto& e : g[i]) {
            if(i < e.to) {
                es.push_back((edge){i, e.to, min(d[i], d[e.to])});
            }
        }
    }
    sort(es.begin(), es.end());

    union_find uf(N);
    vector<vector<int>> tree(2*N);
    int new_id = N;
    vector<int> id(N);
    for(int i=0; i<N; ++i) {
        id[i] = i;
    }
    for(auto& e : es) {
        int a = uf.root(e.from), b = uf.root(e.to);
        if(uf.unite(a, b)) {
            tree[new_id].push_back(id[a]);
            tree[new_id].push_back(id[b]);
            d[new_id] = min(d[id[a]], d[id[b]]);
            id[uf.root(a)] = new_id;
            new_id += 1;
        }
    }

    lca l(tree, new_id-1);
    for(int i=0; i<Q; ++i) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        cout << d[l.query(s, t)] << endl;
    }
}

AOJ 0519 Worst Reporter

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519

解法

a が b に勝利したことを，a -> b と有向辺で表現することにすれば，この問題はトポロジカル順序を求める問題になる．
トポロジカル順序が求まったら，その頂点列のなかで隣り合っていて，かつその頂点間に辺が存在していないものがあるかを考える．
存在していれば，順位は一意に定まらない．

最悪の記者だからトポロジカル順序に矛盾があるような入力があるかと思ったらそうでもなかった．最悪の記者でもなさそう（ほんまか）．

ソースコード

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>> const& g, int v, vector<bool>& used, vector<int>& res) {
    if(!used[v]) {
        used[v] = true;
        for(auto to : g[v]) {
            dfs(g, to, used, res);
        }
        res.push_back(v);
    }
}

vector<int> tsort(vector<vector<int>> const& g) {
    vector<bool> used(g.size());
    vector<int> res;
    for(int i=0; i<g.size(); ++i) {
        dfs(g, i, used, res);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i=0; i<m; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
    }
    auto res = tsort(g);
    bool f = true;
    for(int i=0; i<n-1; ++i) {
        bool f2 = false;
        for(int j=0; j<g[res[i]].size(); ++j) {
            f2 |= g[res[i]][j] == res[i+1];
        }
        f &= f2;
    }

    for(auto x : res) {
        cout << x+1 << endl;
    }
    cout << !f << endl;
}