Codeforces Round #320 (Div.1) C. Weakness and Poorness

* 問題文
http://codeforces.com/contest/578/problem/C

解法

max 取ってるし、x についての weakness を f(x) とすると、下に凸な関数になりそう。
なので3分探索する。
x を決めたときの a[i] - x 列の区間和最大、最小は線形で解ける。
左から累積和を見ていって、それまでの最大値と最小値を持っておけばOK。
よって O(nlog|a|) で解ける。

関係ないけど、区間Add区間和最大セグ木が途中でほしいなーと思って考えて、無理じゃね?となった。(区間Addで壊れる)

ソースコード

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

constexpr double inf = 1e9;
constexpr double gratio = (std::sqrt(5)+1)/2.0;

template <typename F>
double golden_section_search(F f, double lb, double ub, int cnt) {
    double x1 = (ub-lb)/(gratio+1) + lb,
        x2 = (ub-lb)*gratio/(gratio+1) + lb;
    double v1 = f(x1), v2 = f(x2);
    for(int i=0; i<cnt; ++i) {
        if(v1 < v2) {
            ub = x2;
            x2 = x1;
            v2 = v1;
            x1 = (ub-lb)/(gratio+1) + lb;
            v1 = f(x1);
        } else {
            lb = x1;
            x1 = x2;
            v1 = v2;
            x2 = (ub-lb)*gratio/(gratio+1) + lb;
            v2 = f(x2);
        }
    }
    return (lb+ub)/2;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(10);
    int n; cin >> n;
    vector<double> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    auto f = [&] (double x) {
        vector<double> sum(n + 1);
        double min_s = 0, max_s = 0;
        double res = 0;
        for(int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + a[i] - x;
            res = max({res, abs(sum[i + 1] - max_s), abs(sum[i + 1] - min_s)});
            min_s = min(min_s, sum[i + 1]);
            max_s = max(max_s, sum[i + 1]);
        }
        return res;
    };
    const auto opti = golden_section_search(f, -10000, 10000, 100);
    cout << f(opti) << endl;
}

Codeforces Round #319 (Div.1) B. Invariance of Tree

解法

自分は直感で、どうせ p に周期3以上のサイクルがあると困るんじゃないの、みたいに考えた。
周期3以上のサイクル内部で辺を張るとループができて困るので、そういう意味では正しい。
また、2つのサイクル c1 = (a1, a2, ..., ak), c2 = (b1, b2, ..., bm) があって、それらのうちから1つのペアを選んで結んでいくと、当然 a1-b1, a2-b2, ... のようにどんどん組まれていくことになる。
なので、k と m の長さが互いに素だとループができて困るなあということもわかる。

そして最も重要なこととして、こうして結んでできた連結成分の構造というのは、あるサイクルに含まれる頂点ごとに注目すると全く同じである。
つまり、ある段階で a1, a2, ... が属する連結成分をそれぞれ見ると、全く同じグラフになっているということ。
これと、木の中心はたかだか2個しかないという性質から、以下のことがわかる。
「周期1または2のサイクルがない場合、構築不可能である」
周期3以上のサイクル内の頂点が中心になるとすると、他の頂点もすべて中心になっているはずなので、それは矛盾だからである。

・周期1のサイクルがある場合
その頂点を他の全部の頂点と結べばOK
・周期1のサイクルがなく、周期2のサイクルがある場合
周期が互いに素だと困るなあ、というのはここで使う。つまり、周期が奇数のサイクルがあれば構築不可能であり、そうでなければ交互に結んでいけばOK。
例えば (a1, a2) と (b1, b2, b3, b4) があれば (a1, b1), (a2, b2), (a1, b3), (a2, b4) と辺を作る。
このときにサイクルの順番は崩さないように。union_find でサイクルを求めてしまって、順番が壊れたまま構築するとWAになる(僕はやらかしました、詰めが甘いね)。

これで解ける。オーダーは O(N)

ソースコード

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

using pii = pair<int, int>;

int main() {
    int n; cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; ++i) {
        cin >> p[i];
        p[i]--;
    }

    vector<bool> visited(n);
    function<void(int, vector<int>& vs)> dfs = [&] (int v, vector<int>& vs) {
        if(visited[v]) return;
        visited[v] = true;
        vs.push_back(v);
        dfs(p[v], vs);
    };
    vector<vector<int>> cmp;
    int sz1_v = -1;
    int sz2_cmp = -1, odd = 0;
    for(int i = 0; i < n; ++i) {
        if(visited[i]) continue;
        vector<int> vs;
        dfs(i, vs);
        if(vs.size() == 1u) {
            sz1_v = i;
        }
        if(vs.size() == 2u) {
            sz2_cmp = cmp.size();
        }
        odd += vs.size() & 1;
        cmp.push_back(move(vs));
    }
    if(sz1_v != -1) {
        cout << "YES" << endl;
        for(int i = 0; i < n; ++i) {
            if(i == sz1_v) continue;
            cout << sz1_v + 1 << ' ' << i + 1 << endl;
        }
    } else if(sz2_cmp != -1 && odd == 0) {
        cout << "YES" << endl;
        cout << cmp[sz2_cmp][0] + 1 << ' ' << cmp[sz2_cmp][1] + 1 << endl;
        for(int i = 0; i < (int)cmp.size(); ++i) {
            if(sz2_cmp == i) continue;
            for(int j = 0; j < (int)cmp[i].size(); j += 2) {
                cout << cmp[sz2_cmp][0] + 1 << ' ' << cmp[i][j] + 1 << endl;
                cout << cmp[sz2_cmp][1] + 1 << ' ' << cmp[i][j + 1] + 1 << endl;
            }
        }
    } else {
        cout << "NO" << endl;
    }
}

感想

時間内に解けなかった。
解説に "It's easy to notice, that centers of that tree must turn into centers after applying the permutation. That means, permutation must have cycle with length 1 or 2 since there're at most two centers" と書いてあって、最初な~にが easy じゃとなっていた。
union find 使って失敗したのも反省(当たり前なのにね、意外と気づかなかった)。

Bubble Cup 8 - Finals G. Run for beer

解法

1ステップごとにコストが10倍になり、かつ辺のコストは高々9であることから、通った道を前から見て10進表記したものがコストなので、できるだけ短いほうがいいことにはすぐ気がつく。

同じ長さならコストが小さいほうがいいが、コストを保持してダイクストラは不可能なので面倒。
とりあえず、今の(これまでに移動した回数、直前の辺のコスト)で最短経路問題を解き、最短路グラフもどきを作る。直前の辺のコストしか見ていないから、真の最短路ではない辺も含まれている。

あとは最短路グラフ(もどき)の上でゴールから1ステップずつみていって、その時々で一番小さいコストの辺を使う頂点以外を取り除いていき、頂点0までたどり着けた頂点が真の最短路になる。

もう一つ面倒なのが、コスト0の辺があることで、こいつのせいで leading zero をいい感じに処理しないといけなくなる。というのも、0がたくさん頭につくときに、これまでに移動した回数をカウントしてしまうと、実際は0なのに最短路グラフ(もどき)に含まれなくなるからである。かといって0のときにカウントしない、みたいなこともできない。

なので、あらかじめ頂点 n - 1 からコスト0だけを使って辿れるところを BFS で列挙しておく(BFSじゃないとパスの長さの最小化にならないので注意)。ここでも最短路グラフを作っておく。

さっきの始点から始める最短経路計算のゴールを、頂点 n - 1 じゃなくて、このBFSで辿れた頂点のうちのどこでもよい、とする。

最後に、その頂点まで至る最短路と、その頂点から終点までに至る最短路を別に復元すればOK。

計算量は O(mlogn + n) 。ダイクストラしてるからね。

ソースコード

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

using ll = long long;
using pii = pair<int, int>;

constexpr int inf = 1e9;

struct edge {
    int to, cost;
};

using graph = vector<vector<edge>>;

int main() {
    int n, m; cin >> n >> m;
    graph g(n);
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back(edge{b, c});
        g[b].push_back(edge{a, c});
    }
    vector<int> to(n, -1), len(n, inf);
    {
        queue<int> que;
        que.push(n - 1);
        len[n - 1] = 0;
        while(!que.empty()) {
            const auto v = que.front(); que.pop();
            for(auto& e : g[v]) {
                if(e.cost != 0 || len[e.to] != inf) continue;
                to[e.to] = v;
                len[e.to] = len[v] + 1;
                que.push(e.to);
            }
        }
    }

    using S = tuple<int, int, int, int>;
    priority_queue<S, vector<S>, greater<>> que;
    que.emplace(0, 0, len[0], 0);
    vector<pii> d(n, make_pair(inf, inf));
    d[0] = make_pair(0, 0);
    vector<vector<pii>> prev(n);
    int last_v = -1;
    while(!que.empty()) {
        int dn, pre_d, zero_len, v;
        tie(dn, pre_d, zero_len, v) = que.top(); que.pop();
        if(d[v] < make_pair(dn, pre_d)) continue;
        if(to[v] != -1 || v == n - 1) { // answer
            last_v = v;
            break;
        }
        for(auto& e : g[v]) {
            if(d[e.to] > make_pair(dn + 1, e.cost)) {
                d[e.to] = make_pair(dn + 1, e.cost);
                prev[e.to].clear();
                prev[e.to].emplace_back(v, e.cost);
                que.emplace(dn + 1, e.cost, len[e.to], e.to);
            } else if(d[e.to] == make_pair(dn + 1, e.cost)) {
                prev[e.to].emplace_back(v, e.cost);
            }
        }
    }

    string ans;
    vector<int> cur = {last_v}, prev2(n, -1);
    while(!cur.empty()) {
        int mini = 10;
        vector<int> nxt;
        for(auto v : cur) {
            for(auto& p : prev[v]) {
                if(mini > p.second) {
                    mini = p.second;
                    nxt.clear();
                    nxt.push_back(p.first);
                    prev2[p.first] = v;
                } else if(mini == p.second) {
                    prev2[p.first] = v;
                    nxt.push_back(p.first);
                }
            }
        }
        if(mini != 10) {
            ans += mini + '0';
        }
        cur = move(nxt);
    }
    if(ans.empty()) ans = "0";
    vector<int> path;
    {
        int now = 0;
        while(now != -1) {
            path.push_back(now);
            now = prev2[now];
        }
        now = last_v;
        while(to[now] != -1) {
            path.push_back(to[now]);
            now = to[now];
        }
    }

    const int sz = path.size();
    cout << ans << endl;
    cout << sz << endl;
    for(int i = 0; i < sz; ++i) {
        cout << path[i] << " \n"[i + 1 == sz];
    }
}

感想

公式解説だと O(n + m) らしい。すごいね。
無限にバグって辛かった(めんどくさいことが多すぎる)。

Codeforces Round #322 (Div.2) F. Zublicanes and Mumocrates

解法

(知っていれば)二乗の木DPっぽいな~となり、実際そうである。
ひとまず普通に木DPをする。
dp[v][cnt][c] := v の部分木だけ考えて、その中の葉を cnt だけ黒く塗り、v の色が c であるときの最小値
とする。
遷移は
dp[v][cnt][c] := min(dp[v][cnt][c], dp[v][cnt - ch_cnt][c] + dp[to][ch_cnt][ch_c] + (c != ch_c)) (forall ch)
みたいなことをする。ただし、v が葉でない場合は、ひとまず dp[v] の初期値を子から1つ選んで初期化しておく必要がある。
以降は最初に選んだ子は無視して遷移する。
遷移するときに、今処理してる子による結果が影響しないようにしておくこと。

さて、問題は計算量だが、cnt と ch_cnt によるループで各ノードで O(n^2) かかるので、全体として O(n^3) っぽいが、実際はそれほど計算が発生しない。

かなり大雑把に捉えるなら、例えば2つの子を持つ部分木を考えて、子のサイズを l, r としたとき、T(l + r) = T(l) + T(r) + l * r のような計算量の漸化式を考えると良い。
(l + r)^2 = l^2 + r^2 + l * r なので、T(n) = n^2 とみなせることがなんとなくわかるはず。

あとはMLEに注意する。あと、ループはきっちりサイズちょうどの上限で回さないと計算量が変わるので丁寧にやること。

ソースコード

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

constexpr int inf = 1e9;

int main() {
    int n; cin >> n;
    vector<vector<int>> g(n);
    for(int i = 0; i < n - 1; ++i) {
        int a, b; cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    if(n == 2) {
        cout << 1 << endl;
        return 0;
    }
    int root = -1;
    for(int i = 0; i < n; ++i) {
        if(g[i].size() != 1u) root = i;
    }

    vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(2, inf)));
    vector<int> sz(n);
    function<void(int, int)> dfs = [&] (int v, int p) {
        if(g[v].size() == 1u) {
            sz[v] = 1;
            dp[v][0][0] = dp[v][1][1] = 0;
            return;
        }
        int fst_ch = -1;
        for(auto to : g[v]) {
            if(to == p) continue;
            if(fst_ch == -1) fst_ch = to;
            dfs(to, v);
        }
        {
            int sum = 0;
            for(auto to : g[v]) {
                if(to == p) continue;
                sum += sz[to];
            }
            dp[v].assign(sum + 1, vector<int>(2, inf));
        }
        for(auto to : g[v]) {
            if(to == p) continue;
            sz[v] += sz[to]; // !! add here
            if(to == fst_ch) {
                for(int cnt = 0; cnt <= sz[v]; ++cnt) {
                    for(int c = 0; c < 2; ++c) {
                        for(int cc = 0; cc < 2; ++cc) {
                            if(dp[to][cnt][cc] == inf) continue;
                            dp[v][cnt][c] = min(dp[v][cnt][c], dp[to][cnt][cc] + (c != cc));
                        }
                    }
                }
            } else {
                for(int cnt = sz[v]; cnt >= 0; --cnt) {
                    for(int c = 0; c < 2; ++c) {
                        int mini = inf;
                        for(int ch_cnt = 0; ch_cnt <= min(sz[to], cnt); ++ch_cnt) {
                            for(int ch_c = 0; ch_c < 2; ++ch_c) {
                                mini = min(mini, dp[v][cnt - ch_cnt][c] + dp[to][ch_cnt][ch_c] + (c != ch_c));
                            }
                        }
                        dp[v][cnt][c] = mini;
                    }
                }
            }
        }
    };
    dfs(root, -1);

    cout << min(dp[root][sz[root] / 2][0], dp[root][sz[root] / 2][1]) << endl;
}

感想

二乗の木DP、集中してコーディングしないとすぐバグるからつらい。

Codeforces Round #318 (Div.1) B. Bear and Blocks

解法

1ステップ後の h[i] の高さは min(h[i - 1], h[i] - 1, h[i + 1]) になる。
一般化して、k ステップ後の h[i] の高さは min(h[i - k], h[i - k + 1] - 1, ..., h[i] - k, ..., h[i + k]) になる。
逆に考えると、h[i] の高さが 0 になるときは、ある j に対して min(h[i - j] - (k - j)) = 0 (j = -k, ..., k) が成り立つ時なので、k = h[i - j] + j である。
これは、左(と右)から順番に見ていけば求めることができるので、線形で解ける。

問題文

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

int main() {
    int n; cin >> n;
    vector<int> h(n + 2);
    for(int i = 1; i <= n; ++i) {
        cin >> h[i];
    }

    auto calc = [n] (vector<int> hs, bool rev = false) {
        if(rev) reverse(begin(hs), end(hs));
        vector<int> vs(n + 2);
        int mini = 0;
        for(int i = 1; i <= n; ++i) {
            mini++;
            if(mini > hs[i]) mini = hs[i];
            vs[i] = mini;
        }
        if(rev) reverse(begin(vs), end(vs));
        return vs;
    };
    auto left = calc(h), right = calc(h, true);

    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans = max(ans, min(left[i], right[i]));
    }

    cout << ans << endl;
}

感想

なんで解けなかったのか、これがわからない。
完全に変なことを考えて泥沼化していた。

AOJ 2850 Endless BFS

解法

01BFSで解いた。
まず、2部グラフだと永遠に終わらないことはわかる。
2部グラフじゃない場合、どこかのタイミングで隣接2頂点が同時に current に入り、そこからそれらの頂点は一生消えない。
そして、そこからどんどん頂点集合が広がっていくことがわかる。

どのタイミングで初めて隣接2頂点が current に入るかは普通に BFS をして、隣接頂点が同じ距離にあることが条件である。
そういう隣接2頂点を見つけたら次からは stable (消えない)状態にうつして、そっちはそっちでBFSをする。
ただし、stable のときの遷移は注意が必要である。例えば今 stable な状態で v にいたとして、隣接頂点 u に移ることを考える。stable な v に至るまでのコストを c1、u の頂点0からの距離を c2 とすると、c1, c2 のパリティが等しいときはコストを0にする(v に至ったタイミングで、u も stable とみなせるから)。
なので、01BFS をすればよいということになる。

stable であるかそうでないかで頂点の数を2倍持っておけばよく、計算量は O(n + m) である。

ソースコード

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

constexpr int inf = 1e9;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    vector<vector<int>> d(n, vector<int>(2, inf));
    d[0][0] = 0;
    deque<tuple<int, int>> que;
    que.emplace_back(0, 0);
    while(!que.empty()) {
        int v, stable;
        tie(v, stable) = que.front(); que.pop_front();
        if(stable == 0) {
            for(auto to : g[v]) {
                if(d[to][0] == d[v][0]) {
                    d[v][1] = d[v][0];
                    que.emplace_back(v, 1);
                }
                if(d[to][0] == inf) {
                    d[to][0] = d[v][0] + 1;
                    que.emplace_back(to, 0);
                }
            }
        } else {
            for(auto to : g[v]) {
                if(d[to][1] != inf) continue;
                if((d[to][0] & 1) == (d[v][1] & 1)) {
                    d[to][1] = d[v][1];
                    que.emplace_front(to, 1);
                } else {
                    d[to][1] = d[v][1] + 1;
                    que.emplace_back(to, 1);
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < n; ++i) {
        ans = max(ans, d[i][1]);
    }

    cout << (ans == inf ? -1 : ans) << endl;
}

感想

想定解はもっと賢かった。
最初にグラフ作るタイミングですでに頂点を2倍にしておいて、偶数を表す頂点と奇数を表す頂点間に辺をはる感じだった。そうするとただのBFSやるだけになる。
まあ解けたので良し。

AOJ 2847 Ninja Map

解法

まず一行目を適当に埋める。次数が 2 の頂点を見つけて、そこから隣接する中で一番小さい次数の頂点をたどっていけば自然に一行埋められる。
一行目が埋まると、下の行の数は一意に定まるので、あとは順番に埋めていくだけ。

ソースコード

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

int main() {
    int n; cin >> n;
    vector<vector<int>> g(n * n);
    for(int i = 0; i < 2 * n * n - 2 * n; ++i) {
        int a, b; cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }

    vector<bool> used(n * n);
    vector<vector<int>> ans(n, vector<int>(n, -1));
    for(int i = 0; i < n * n; ++i) { // r1
        if(g[i].size() == 2u) {
            int cur = i;
            ans[0][0] = cur;
            used[cur] = true;
            for(int j = 0; j < n - 1; ++j) {
                int nxt = -1;
                for(auto to : g[cur]) {
                    if(used[to] || (nxt != -1 && g[nxt].size() < g[to].size())) continue;
                    nxt = to;
                }
                cur = ans[0][j + 1] = nxt;
                used[nxt] = true;
            }
            break;
        }
    }
    for(int i = 0; i < n - 1; ++i) {
        for(int j = 0; j < n; ++j) {
            for(auto to : g[ans[i][j]]) {
                if(used[to]) continue;
                ans[i + 1][j] = to;
                used[to] = true;
            }
        }
    }

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cout << ans[i][j] + 1 << " \n"[j + 1 == n];
        }
    }
}

感想

O(n^4) も徳が高い人なら通りそう。
僕は試したんですがあと 0.2sec 縮めればOKだったので適当に定数倍早くすればよさそう。