AOJ 1330 Never Wait for Weights

競プロ AOJ

問題

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

解法

基本は union-find をいじるだけ．
各ノードは，親からの相対重さを持つ．
クエリで a, b, w が与えられたとする． a と b の代表元が異なる場合は，それぞれの集合の根を r1, r2，各ノードの真の重みを W とおくと，

  • W[r1] - W[r2] = -w + (b の r2 からの相対重み) - (a の r1 からの相対重み)

であることが（簡単な計算で）わかる．
あとはこの処理を union-find 木の処理に追加すればよい．

ソースコード

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

constexpr int INF = 1e9;

class union_find {
public:
    union_find(int N)
        : par(N, -1), rank(N), w(N)
    {}

    pair<int, int> root(int x) {
        if(par[x] < 0) {
            return make_pair(x, 0);
        }
        pair<int, int> p = root(par[x]);
        w[x] += p.second;
        p.second = w[x];
        par[x] = p.first;
        return p;
    }

    void unite(int x, int y, int v) {
        int rx = root(x).first, ry = root(y).first;
        if(rx == ry) {
            return;
        }
        if(rank[rx] > rank[ry]) {
            par[ry] = rx;
            w[ry] = v - w[y] + w[x];
        } else {
            par[rx] = ry;
            w[rx] = -v + w[y] - w[x];
            if(rank[rx] == rank[ry]) {
                rank[ry]++;
            }
        }
    }

    int calc(int x, int y) {
        if(root(x).first != root(y).first) {
            return INF;
        }
        return w[y] - w[x];
    }
        
private:
    vector<int> par;
    vector<int> rank;
    vector<int> w;
};

int main() {
    int N, M;
    while(cin >> N >> M, N) {
        union_find uf(N);
        for(int i=0; i<M; ++i) {
            char op; cin >> op;
            if(op == '!') {
                int a, b, v;
                cin >> a >> b >> v;
                a--; b--;
                uf.unite(a, b, v);
            } else {
                int a, b;
                cin >> a >> b;
                a--; b--;
                if(uf.calc(a, b) == INF) {
                    cout << "UNKNOWN" << endl;
                } else {
                    cout << uf.calc(a, b) << endl;
                }
            }
        }
    }
}

AOJ 1318 Long Distance Taxi

競プロ AOJ

問題

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

解法

単純に d[街の番号][残りのガソリン] で通ってしまって悲しいので，少し違う方針で．
まず，ガソリンスタンドについたら満タンにしてしまっていいので，ガソリンスタンドから cap を超えないように行ける街をあらかじめ M 回ダイクストラすることによって，新しいグラフを作る．新しい辺の重みはそのガソリンスタンドからの距離とする．（当たり前だが，辺を張るときは ガソリンスタンド -> 行ける街 のように張る．勢いで無向グラフにしないように．）
こうしてできたグラフの上で普通のダイクストラをすれば，上のような二次元配列を持つ必要はなくなる．

ソースコード

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

using pii = pair<int, int>;

struct edge {
    int to, cost;
};

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

constexpr int INF = 1e9;

vector<int> dijkstra(graph& g, int s) {
    vector<int> d(g.size(), INF);
    priority_queue<pii, vector<pii>, greater<pii>> que;
    que.push(make_pair(0, s));
    d[s] = 0;
    while(!que.empty()) {
        pii 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));
            }
        }
    }
    return d;
}

int main() {
    int N, M, cap;
    while(cin >> N >> M >> cap, N) {
        unordered_map<string, int> idx;
        string src, dest;
        cin >> src >> dest;
        graph g(6001);
        idx[src] = 0; idx[dest] = 1;
        cap *= 10;
        for(int i=0; i<N; ++i) {
            string c1, c2;
            int d;
            cin >> c1 >> c2 >> d;
            if(idx.count(c1) == 0) {
                idx[c1] = idx.size();
            }
            if(idx.count(c2) == 0) {
                idx[c2] = idx.size();
            }
            g[idx[c1]].push_back(edge{idx[c2], d});
            g[idx[c2]].push_back(edge{idx[c1], d});
        }
        vector<int> S = {0, 1};
        for(int i=0; i<M; ++i) {
            string s;
            cin >> s;
            S.push_back(idx[s]);
        }
        graph g2(S.size());
        for(int i=0; i<S.size(); ++i) {
            auto d = dijkstra(g, S[i]);
            for(int j=0; j<S.size(); ++j) {
                if(d[S[j]] <= cap) {
                    g2[i].push_back(edge{j, d[S[j]]});
                }
            }
        }
        auto res = dijkstra(g2, 0);
        cout << (res[1] == INF ? -1 : res[1]) << endl;
    }
}

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

競プロ Codeforces

問題文

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

競プロ AOJ

問題

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

競プロ AOJ

問題

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

競プロ AOJ

問題文

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

競プロ AOJ

問題

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;
}