まず，0を始点としてダイクストラで，各点への最短路重みを求めておく．
そして，その重みで頂点をソートしておく．また，あらかじめ辺全体の重みの総和を求めておく．
Xの候補としては，各頂点への最短路重みだけ考えればよいことは明らかにわかる．
つまり，Xの候補はN通り．
ここでXを大きくしていき，その各過程で点0から到達可能な頂点集合Sについて，今追加しようとしている頂点からSと接続している辺の重みを，総和から減らしていくと良い．
こうしていった中で一番小さい値が求める答えである．

計算量は O(ElogV + VlogV)

ソースコード

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

using ll = long long;
using P = pair<ll, ll>;

struct edge {
    int from, to;
    ll weight;
};

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

constexpr ll INF = 1e18;

int main() {
    ll N, M, C;
    cin >> N >> M >> C;

    graph g(N);
    ll sum_cost = 0;
    for(int i=0; i<M; ++i) {
        int a, b;
        ll d;
        cin >> a >> b >> d;
        a--; b--;
        g[a].push_back((edge){a, b, d});
        g[b].push_back((edge){b, a, d});
        sum_cost += d;
    }

    vector<P> d(N);
    for(int i=1; i<N; ++i) {
        d[i] = make_pair(INF, i);
    }
    d[0] = make_pair(0, 0);
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(make_pair(0, 0));
    while(!que.empty()) {
        P p = que.top();
        int v = p.second;
        que.pop();
        if(d[v].first > p.first) {
            continue;
        }
        for(auto& e : g[v]) {
            if(d[e.to].first > d[v].first + e.weight) {
                d[e.to].first = d[v].first + e.weight;
                que.push(make_pair(d[e.to].first, e.to));
            }
        }
    }
    sort(d.begin(), d.end());
    ll res = 1e18;
    set<int> S;
    for(int i=0; i<N; ++i) {
        for(auto& e : g[d[i].second]) {
            if(S.count(e.to) == 1) {
                sum_cost -= e.weight;
            }
        }
        res = min(res, sum_cost + C * d[i].first);
        S.insert(d[i].second);
    }
    cout << res << endl;
}

2017-05-11

AOJ 0600 Baumkuchen

競プロ AOJ

問題文

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

解法

累積和と二分探索．
まず，バウムクーヘンの累積和を二周分求めておく．
その後，左端を適当に定め，そこから始めて長さが (lb + ub) / 2 以上になるところを2分探索で求める．さらにそこから同様に次の地点を求めて，各地点の距離の差が(lb + ub) / 2以上であれば，下限を更新する．そうでなければ上限を更新．

解の範囲を収束させるのに O(logN)，仮定した長さが条件をみたすか調べるのにO(NlogN)かかるので，トータルO(N(logN)^2)．

しゃくとりでやるともうちょい早くなりそうだけどめんどくさそうなのでやめました（実はそんなにめんどくさくない？）

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
bool check(vector<ll> const& a, ll m) {
    const int N = a.size() / 2;
    bool ok = false;
    for(int i=0; i<N; ++i) {
        int j = lower_bound(a.begin()+i, a.begin()+i+N+1, a[i]+m) - a.begin();
        int k = lower_bound(a.begin()+j, a.begin()+i+N+1, a[j]+m) - a.begin();
        if(a[j] - a[i] >= m && a[k] - a[j] >= m && a[i+N] - a[k] >= m) {
            ok = true;
            break;
        }
    }
    return ok;
}
 
int main() {
    int N;
    cin >> N;
    vector<ll> a(2*N+1);
    for(int i=1; i<=N; ++i) {
        cin >> a[i];
        a[i+N] = a[i];
    }
    for(int i=1; i<2*N+1; ++i) {
        a[i] += a[i-1];
    }
 
    ll lb = 0, ub = (a[N] + 2) / 3;
    while(ub - lb > 1) {
        ll m = (ub + lb) / 2;
        if(check(a, m)) {
            lb = m;
        } else {
            ub = m;
        }
    }
    cout << lb << endl;
}

2017-05-01

AOJ 0509 Sheets

競プロ AOJ

問題文

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

問題概要

平面座標に n 個の長方形がある．重なっていることもある．
それらがつくる図形の面積と，周の長さを求めよ．

・制約
1 <= n <= 10000
長方形の左下，右上の座標の x, y 座標は，共に 0 以上 10000 以下である．

解法

累積和（いもす法）でやる．
ただし愚直に2次元累積和を取ると MLE する．
そのため，まず0行目から横一行（縦一列でもよい）ずつ見ていくようにして，次の行を見るときは前の行の値を使うようにする．
こうすると，それ以前の値を保存する必要が無いので，MLEを防げる．
流れとしては，

横で累積和をとる．
そのあと，前の行の累積和を足す．
累積和の値が1以上であれば面積に1追加，図形の端（自身と四方の累積和を比較すればわかる）であれば周の長さに1追加する．

どこに +1 して -1 するかは，y座標をindexとする vector の vector を持っておけば良い．

これでなんとか解ける．
計算量は O(XY) = 10^8 で，定数倍かかるのでかなりギリギリになった．

賢く書けばもうちょい早くなるかも．

ソースコード

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

using P = pair<int, int>;

constexpr int MAX_Y = 10003;
constexpr int MAX_X = 10003;

int main() {
    int n, r;
    while(cin >> n >> r, n) {
        vector<vector<P>> v(MAX_Y);
        for(int i=0; i<n; ++i) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            v[y1+1].emplace_back(x1+1, 1);
            v[y1+1].emplace_back(x2+1, -1);
            v[y2+1].emplace_back(x1+1, -1);
            v[y2+1].emplace_back(x2+1, 1);
        }
        vector<vector<int>> sum(2, vector<int>(MAX_X));
        int S = 0, len = 0;
        for(int i=0; i<MAX_Y; ++i) {
            int now = i % 2, pre = (i+1) % 2;
            fill(sum[now].begin(), sum[now].end(), 0);
            for(int j=0; j<v[i].size(); ++j) {
                sum[now][v[i][j].first] += v[i][j].second;
            }
            for(int j=0; j<MAX_X; ++j) {
                sum[now][j+1] += sum[now][j];
                sum[now][j] += sum[pre][j];
            }
            for(int j=0; j<MAX_X; ++j) {
                S += sum[now][j] > 0;
                len += ((sum[pre][j] > 0) != (sum[now][j] > 0));
                len += ((sum[now][j] > 0) != (sum[now][j+1] > 0));
            }
        }
        
        if(r == 1) {
            cout << S << endl;
        } else {
            cout << S << '\n' << len << endl;
        }
    }
}

2017-05-01

AOJ 0517 Longest Steps

競プロ AOJ

問題文

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

解法

しゃくとり法でやった．
与えられた k 枚のカードをソートしておく．
0が含まれていれば1つだけ飛ばせるので，それは場合分けで処理．
行けるところまでいったら，左端をカードの数字が1以上飛んでいるところに更新する．

オーダーはソートがネックなので O(klogk + k)．

しかし，連続部分を pair でもっておいて，0 が含まれていれば隣り合う連続区間をつなげる，みたいな実装の方が自然かもしれない．

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, k;
    while(cin >> n >> k, n) {
        vector<int> v(k);
        for(int i=0; i<k; ++i) {
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        int f = v[0] == 0;
        int l = 0+f, r = 1+f, cnt = 0, next_l = -1;
        int res = 0;
        while(true) {
            next_l = -1;
            while(r < k && (v[r] - v[r-1] == 1 || v[r] - v[r-1] == 2)) {
                if(v[r] - v[r-1] == 1) {
                    r++;
                } else if(cnt < f) {
                    cnt++;
                    next_l = r;
                    r++;
                } else {
                    break;
                }
            }
            res = max(res, r - l + ((r == k && cnt < f) || cnt));
            if(r == k) {
                break;
            }
            if(next_l == -1) {
                l = r;
                r++;
            } else {
                l = next_l;
            }
            cnt = 0;
        }
        cout << res << endl;
    }
}