TopCoder SRM #629 Div2

SRM DP グラフ 確率

ooo 911->1089(+178) 11th とかなり調子が良かった。

Easy(250)

配列の連続な部分列の総和、の総和を求めよ。

nは小さいので愚直に足し算する。

class SumOfPower {
public:
    int findSum(vector<int> v) {
        int n = v.size();
        int ans = 0;
        rep(i, n)loop(j, i + 1, n + 1){
            ans += accumulate(v.begin() + i, v.begin() + j, 0);
        }
        return ans;
    }

Med(500)

1～aの目が出るサイコロAと、1～bの目が出るサイコロBを振ったとき、Aの目のほうが大きかった。Aの目の期待値を求めよ。

目の出方全ての場合に対して分母と分子を別々に求めて足してゆき、最後に分子/分母を返す。

class FixedDiceGameDiv2 {
public:
    double getExpectation(int a, int b) {
        double ans = 0;
        int c = 0;
        for (int aa = 1; aa <= a; aa++){
            for (int bb = 1; bb <= b; bb++){
                if (aa <= bb) continue;
                c++;
                ans += aa;
            }
        }

        return ans / c;
    }

Hard(1000)

解けた！！！(が、昔解いたこれ↓とほぼ同じだったので運が良かっただけ。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0212 )

有向グラフが与えられる。v[1]からv[n]までの最短経路を求めよ。ただしそれぞれの経路で最大changes回だけグラフの重みをマイナスにできる。同じ辺の往復も可能で、自己ループもあるかもしれない。

changesが高々i回だけ使えるという制限で求めた最短距離の情報d[i][]が分かっているとき、さらにもう一回changesを使って良いことにしたらどうなるか考えると d[i] = min(d[a][v] + e.cost, d[a - 1][v] - e.cost) という漸化式が立つ。これでi=changesまで順番に更新していく。ダイクストラ以外だと少し工夫しないとTLEするらしい？

はじめ、戻り値がlong longになっているのに気づかずに全部intにしてsubmitする。その後慌てて直したけど結局間に合わず絶望する。が、よく考えたらintで普通に収まるじゃないか…

結局はAOJ0212で重みを1/2倍にできたのを-1倍に置き換えただけだけど、それを思いつき、ググって問題を特定するまでに結構時間を使ってしまった。(「最短距離 回数 半額」とかでググったけどなかなか見つからなかった)

const int inf = 1 << 29;
struct Edge { 
    int src, dst, cost;
    Edge(int src, int dst, int cost) : src(src), dst(dst), cost(cost){}
};
struct State {
    int cost, v;
    State(int cost, int v) :cost(cost), v(v){}
    bool operator<(const State& r) const{
        return cost > r.cost;
    }
};

typedef vector<vector<Edge>> Graph;

class NegativeGraphDiv2 {
public:
    long long findMin(int N, vector <int> s, vector <int> t, vector <int> w, int c) {
        Graph g(N + 1);
        int const E = s.size();
        rep(i, E) g[s[i]].emplace_back(Edge(s[i], t[i], w[i]));
        vi prev(N + 1, inf);
        rep(i, c + 1){
            vi cur(N + 1, inf);
            dijk(g, i, cur, prev);
            swap(cur, prev);
        }
        return prev[N];
    }

    void dijk(Graph const& g, int c, vi& cur, vi const& prev){
        priority_queue<State> q;
        q.push(State(0, 1));
        cur[1] = 0;
        while (q.size()){
            State p = q.top(); q.pop();
            int v = p.v;
            if (cur[v] < p.cost) continue;
            rep(i, g[v].size()){
                Edge const& e = g[v][i];
                int t = cur[v] + e.cost;
                if (c) t = min(cur[v] + e.cost, prev[v] - e.cost);
                if (cur[e.dst] > t){
                    cur[e.dst] = t;
                    q.push(State(t, e.dst));
                }
            }
        }
    }