読者です 読者をやめる 読者になる 読者になる

AOJ 2741 Invisible

解法

メモ化再帰で解ける.
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

解法

実装できなかったので,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

解法

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

AOJ 0526 Boat Travel

解法

基本はワーシャルフロイドだが,それだと間に合わないので工夫する.
仮に島a, b間の船舶が更新された時,グラフ上の異なる2つの島u, vの最短経路は,

  • u -> a -> b -> v つまり d[u][a] + d[b][v] + d[a][b]
  • u -> b -> a -> v つまり d[u][b] + d[a][v] + d[a][b]
  • そもそも a, b 間の船舶を利用しない,つまり d[u][v]

の3通りで,これらの中から最小のものを d[u][v] に入れれば良い.

これだと計算量は,各更新に対して O(N^2) で,更新は高々 10^3 回なので間に合う.

まぁ,毎回ダイクストラしてもいいけど.それだと高々 2.5 * 10^7 ぐらいか.

ソースコード

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

constexpr int INF = 1e9;

int main() {
    int n, k;
    while(cin >> n >> k, n) {
        vector<vector<int>> d(n, vector<int>(n, INF));
        for(int i=0; i<n; ++i) {
            d[i][i] = 0;
        }
        for(int i=0; i<k; ++i) {
            int a;
            cin >> a;
            if(a == 0) {
                int b, c;
                cin >> b >> c;
                b--; c--;
                cout << (d[b][c] == INF ? -1 : d[b][c]) << endl;
            } else {
                int b, c, e;
                cin >> b >> c >> e;
                b--; c--;
                if(d[b][c] <= e) {
                    continue;
                }
                for(int j=0; j<n; ++j) {
                    for(int l=0; l<n; ++l) {
                        d[j][l] = min(d[j][l], min(d[j][b] + d[c][l], d[j][c] + d[b][l]) + e);
                    }
                }
            }
        }
    }
}

AOJ 0562 Shopping in JOI Kingdom

解法

まず,各頂点がショッピングモールからどれだけ離れているかを求める.
これは,ショッピングモールの頂点をあらかじめ全てpriority_queueに突っ込んでおいたダイクストラを解けばよい.
すると解の候補としては

  • 求めた各頂点のショッピングモールからの距離
  • 隣接した2頂点の,それぞれのショッピングモールからの距離d1, d2と,2頂点を結ぶ辺の重みを足したものを2で割ったもの

の2つであるから,これらを実際に求めれば良い.
出力する答えを四捨五入するのを忘れずに.

計算量は O(MlogN + N + M).

ソースコード

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

using P = pair<int, int>;

struct edge {
    int to, weight;
};

constexpr int INF = 1e9;

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

    priority_queue<P, vector<P>, greater<P>> que;
    vector<int> d(N, INF);
    for(int i=0; i<K; ++i) {
        int s;
        cin >> s;
        s--;
        que.push(make_pair(0, s));
        d[s] = 0;
    }

    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.weight) {
                d[e.to] = d[v] + e.weight;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }

    double res = 0;
    for(int i=0; i<N; ++i) {
        res = max(res, (double)d[i]);
        for(int j=0; j<g[i].size(); ++j) {
            res = max(res, (d[i] + d[g[i][j].to] + g[i][j].weight) / 2.0);
        }
    }
    cout << (int)floor(res + 0.5) << endl;
}

AOJ 0623 Zombie Island

解法

危険な街を列挙さえすれば,あとはただの単一始点最短路問題.
危険な街を列挙するには,ゾンビに支配された街を全て,最初にqueueにプッシュしておくだけで十分である.

計算量は O(N + MlogN)

ソースコード

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

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

constexpr ll INF = 1e18;

int main() {
    int N, M, K, S;
    ll P, Q;
    cin >> N >> M >> K >> S;
    cin >> P >> Q;

    vector<ll> zd(N, INF);
    queue<int> que1;
    for(int i=0; i<K; ++i) {
        int c;
        cin >> c;
        c--;
        que1.push(c);
        zd[c] = 0;
    }

    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);
        g[b].push_back(a);
    }

    while(!que1.empty()) {
        int v = que1.front();
        que1.pop();
        for(auto to : g[v]) {
            if(zd[to] == INF) {
                zd[to] = zd[v] + 1;
                que1.push(to);
            }
        }
    }

    vector<ll> d(N, INF);
    d[0] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> que;
    que.push(make_pair(0, 0));
    while(!que.empty()) {
        pll p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first) {
            continue;
        }
        for(auto to : g[v]) {
            if(zd[to] == 0) {
                continue;
            }
            ll cost = to == N-1 ? 0 : (zd[to] > S ? P : Q);
            if(d[to] > d[v] + cost) {
                d[to] = d[v] + cost;
                que.push(make_pair(d[to], to));
            }
        }
    }
    cout << d[N-1] << endl;
}

AOJ 0616 JOI Park

解法

まず,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;
}