2017-06-12

AOJ 2255 6/2(1+2)

競プロ AOJ

問題

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

解法

BNFどおりに実装する必要はなくて，区間DPをすればよい．
その区間で取りうる値の集合を持たせておく．
区間 [l..r] の演算子を全て見ていって [l..i-1] と [i+1..r] に分ける．
この時，演算子で分けて括弧の対応が崩れるなら一旦スルーしておく必要がある．
たとえば，括弧が ( .. ( .. op_i .. ) .. ) となっていると，op_i で左右に分けることができない．
これは最初に括弧の対応付を調べておけばよい．
また，( expr ) となっているときは， expr に置き換えて処理するとよい．

ソースコード

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

set<int> memo[201][201];
vector<int> par_pos;

int number(string const& s, int p) {
    int res = 0;
    while(p < s.size() && isdigit(s[p])) {
        res *= 10;
        res += s[p++] - '0';
    }
    return res;
}

set<int> solve(string const& s, int l, int r) {
    auto& res = memo[l][r];
    if(res.size() != 0) {
        return res;
    }
    bool f = true;
    for(int i=l; i<=r; ++i) {
        f &= isdigit(s[i]);
    }
    if(f) {
        res.insert(number(s, l));
        return res;
    }
    if(par_pos[l] == r) {
        return res = solve(s, l+1, r-1);
    }
    vector<int> pare(s.size());
    for(int i=l; i<=r; ++i) {
        if(s[i] == '(') {
            pare[i] = 1;
        }
        if(s[i] == ')') {
            pare[i] = -1;
        }
        if(i != l) {
            pare[i] += pare[i-1];
        }
    }
    for(int i=l+1; i<r; ++i) {
        char c = s[i];
        if(pare[i] != 0) {
            continue;
        }
        if(c == '+' || c == '-' || c == '*' || c == '/') {
            set<int> s1 = solve(s, l, i-1);
            set<int> s2 = solve(s, i+1, r);
            for(auto x : s1) {
                for(auto y : s2) {
                    if(c == '+') {
                        res.insert(x + y);
                    } else if(c == '-') {
                        res.insert(x - y);
                    } else if(c == '*') {
                        res.insert(x * y);
                    } else {
                        if(y == 0) {
                            continue;
                        }
                        res.insert(x / y);
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    string s;
    while(cin >> s, s != "#") {
        for(int i=0; i<201; ++i) {
            for(int j=0; j<201; ++j) {
                memo[i][j].clear();
            }
        }
        par_pos.assign(s.size(), -1);
        stack<int> p;
        for(int i=0; i<s.size(); ++i) {
            if(s[i] == '(') {
                p.push(i);
            }
            if(s[i] == ')') {
                par_pos[p.top()] = i;
                p.pop();
            }
        }
        cout << solve(s, 0, s.size()-1).size() << endl;
    }
}

2017-06-11

AOJ 1350 There is No Alternative

競プロ AOJ

問題

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

問題概要

連結グラフ G が与えられる．一般に G の最小全域木は複数存在しうる．G のすべての最小全域木に必ず含まれている辺を求めよ．

・制約
3 <= N <= 500
N-1 <= M <= min(50000, N(N-1)/2)

解法

最小全域木 T を一つ求める．すると，候補の辺は必ずこの T に含まれている．
よって，T に含まれる辺を一つ使えないようにした状態で，最小全域木 T2 を構築してみる．w(T) != w(T2) ならば，この時使えなくした辺は必ず使う辺である．

計算量は O(MlogM + NMα(N))．

ソースコード

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

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


using weight = int;

struct edge {
    int u, v;
    weight cost;
    bool operator<(edge const& e) const {
        return cost < e.cost;
    }
};

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

int main() {
    int N, M;
    cin >> N >> M;
    edges es(M);
    for(int i=0; i<M; ++i) {
        cin >> es[i].u >> es[i].v >> es[i].cost;
        es[i].u--;
        es[i].v--;
    }
    sort(es.begin(), es.end());
    int mst_sum = 0;
    edges mst;
    union_find uf(N);
    for(int i=0; i<M; ++i) {
        if(!uf.same(es[i].u, es[i].v)) {
            uf.unite(es[i].u, es[i].v);
            mst.push_back(es[i]);
            mst_sum += es[i].cost;
        }
    }
    int cnt = 0, res_sum = 0;
    for(int i=0; i<N-1; ++i) {
        uf.init(N);
        int sum = 0;
        for(auto& e : es) {
            if(!uf.same(e.u, e.v) && (mst[i].u != e.u || mst[i].v != e.v)) {
                uf.unite(e.u, e.v);
                sum += e.cost;
            }
        }
        if(sum != mst_sum) {
            cnt++;
            res_sum += mst[i].cost;
        }
    }
    cout << cnt << ' ' << res_sum << endl;
}

2017-06-10

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

2017-06-05

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

2017-06-04

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

2017-05-26

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

2017-05-26

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