AOJ 1351 Flipping Parentheses

競プロ AOJ

問題文

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

解法

StarrySkyTree + 二分探索で通した．

( を +1, ) を -1 として累積和をStarrySkyTree上で管理する．
文字列が balanced であることと，累積和上の最小値が 0 以上であり，かつ末尾の値が0であることは同値である．

さて，与えられた位置をとりあえず反転して考える．

( -> ) に反転した場合，明らかに反転後最も左に現れる ) の位置が答えになる（証明も簡単）．

) -> ( に反転した場合が問題である．
ある位置の ( を ) に反転できる条件は，それ以降の累積和の値の最小値が2以上であることに気がつけば，二分探索で求めるだけになる．

計算量は O(N(logN)^2) となる．

ソースコード

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

constexpr int inf = 1e9;

class starry_sky_tree {
public:
    starry_sky_tree(int n_)
    : n(expand(n_)), data(n * 2, 0), lazy(n * 2, 0)
    {}

    void add(int l, int r, int val) {
        l += n, r += n;
        const int left = l, right = r;
        while(l != r) {
            if(l & 1) {
                lazy[l] += val;
                data[l++] += val;
            }
            if(r & 1) {
                lazy[--r] += val;
                data[r] += val;
            }
            l /= 2, r /= 2;
        }
        l = left, r = right - 1;
        while(l /= 2, r /= 2) {
            data[l] = min(data[l * 2], data[l * 2 + 1]) + lazy[l];
            data[r] = min(data[r * 2], data[r * 2 + 1]) + lazy[r];
        }
    }

    int query(int l, int r) const {
        l += n, r += n;
        int res1 = inf, res2 = inf;
        while(l != r) {
            if(l & 1) res1 = min(res1, data[l++]);
            if(r & 1) res2 = min(res2, data[--r]);
            l /= 2, r /= 2;
            res1 += lazy[l - 1];
            res2 += lazy[r];
        }
        --l;
        while(l /= 2, r /= 2) {
            res1 += lazy[l];
            res2 += lazy[r];
        }
        return min(res1, res2);
    }

private:
    int expand(int n) {
        return n == 1 ? n : expand((n + 1) / 2) * 2;
    }

private:
    const int n;
    vector<int> data, lazy;
};

int main() {
    int N, Q;
    string s;
    cin >> N >> Q >> s;

    starry_sky_tree sum(N);
    set<int> right_paren;
    for(int i = 0; i < N; ++i) {
        if(s[i] == '(') {
            sum.add(i, N, 1);
        } else {
            sum.add(i, N, -1);
            right_paren.insert(i);
        }
    }

    while(Q--) {
        int q;
        cin >> q;
        q--;

        int ans = q;
        if(s[q] == '(') {
            sum.add(q, N, -2);
            right_paren.insert(q);
            ans = *right_paren.begin();
            right_paren.erase(ans);
            sum.add(ans, N, 2);
        } else {
            sum.add(q, N, 2);
            int lb = 0, ub = N - 1;
            while(ub - lb > 1) {
                const int mid = (lb + ub) / 2;
                if(sum.query(mid, N) >= 2) {
                    ub = mid;
                } else {
                    lb = mid;
                }
            }
            ans = ub;
            sum.add(ans, N, -2);
            right_paren.erase(q);
            right_paren.insert(ans);
        }
        swap(s[q], s[ans]);

        cout << ans + 1 << endl;
    }
}

感想

swap(s[q], s[ans]) を書き忘れて WA をもらってしまった．

AOJ 1333 Beautiful Spacing

競プロ AOJ

問題文

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

解法

二分探索＋しゃくとり法．
二分探索は，普通に「スペースの隙間を X にして条件をクリアできるか」でやる．

次にしゃくとり部分．二分探索の過程で与えられた，空けていい間隔を S とする．

先に以下のテーブルを定義しておく．
dp[i] := i 番目の単語を左端にして，その後ろだけ考えた場合にクリアできるか．
更新は後ろからやる．

まず各 i について，「x[i] から x[j] まで一行に詰め込めるような，最大の j 」を考え，R1 とする．
次に，各 i について「x[i] から x[j] まで一行に詰め込んだ時に，Sをクリアできるような最小の j 」を R2 とする．
すると，R2 から R1 の間であれば，どこで一行を終えてもよい．また，位置 p を右端にして区切ってクリアできるかどうかは，dp[p + 1] をみればわかる．
したがって，
dp[i] = (dp[R2 + 1] + ... + dp[R1+1]) > 0
となる．

R1, R2, dp[R2 + 1] + ... + dp[R1 + 1] はすべてしゃくとりで計算できる．
したがって，これで計算量が O(NlogW) にできている．

ただし，最終行だけは右端に文字を置く必要がないと問題文に書かれているので，そこだけ辻褄を合わせる．

ソースコード

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

int main() {
    int W, N;
    while(cin >> W >> N, W) {
        vector<int> x(N), sum(N + 1);
        for(int i = 0; i < N; ++i) {
            cin >> x[i];
            sum[i + 1] = sum[i] + x[i];
        }

        auto check = [&](int space) {
            vector<int> dp(N + 1);
            int limit_r = N, ok_r = N;
            int ok_cnt = 0;
            for(int i = N - 1; i >= 0; --i) {
                while(W - (sum[limit_r] - sum[i]) - (limit_r - i - 1) < 0) {
                    ok_cnt -= dp[limit_r--];
                }
                while(ok_r > limit_r || ok_r - i - 1 > 0 && (W - (sum[ok_r] - sum[i]) + ok_r - i - 2) / (ok_r - i - 1) <= space) {
                    ok_cnt += dp[ok_r--];
                }

                dp[i] = limit_r == N || ok_cnt > 0;
            }

            return dp[0] == 1;
        };

        int lb = 0, ub = W;
        while(ub - lb > 1) {
            const int mid = (ub + lb) / 2;
            if(check(mid)) {
                ub = mid;
            } else {
                lb = mid;
            }
        }

        cout << ub << endl;
    }
}

感想

無限にバグった．
最初 O(NlogNlogW) 解で通るやろと贅沢に書いていたら11secぐらいでTLEしてしまい，泣きながらしゃくとりを書いた．
終わってみればしゃくとりのほうがコードはスッキリしていた．

2014 Yandex.Algorithm Elimination Stage, Round 3 E - Tetrahedron

競プロ Yandex.Algorithm

問題文

http://codeforces.com/gym/100459

解法

Standing -> 重心をおろした位置が底面の内部
Unstable -> 重心をおろした位置が底面の周上にある
Falling -> 重心をおろした位置が底面の外部

重心の座標は (a + b + c + d) / 4 なので，あとは底面の三角形と点との内外判定をするだけ．

ソースコード

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

using ld = long double;
using point = complex<ld>;
using polygon = vector<point>;

constexpr ld eps = 1e-10;
constexpr ld pi = acos(-1.0);

class segment {
public:
    segment(point p1, point p2)
    : a(p1), b(p2)
    {}

    point a, b;
};

bool isis_sp(segment s, point p) {
    return std::abs(s.a - p) + std::abs(s.b - p) - std::abs(s.b - s.a) < eps;
}


int is_in_polygon(polygon const& poly, point p) {
    const int n = poly.size();
    ld sum = 0;
    for(int i = 0; i < n; ++i) {
        point p1 = poly[i], p2 = poly[(i + 1) % n];
        if(isis_sp(segment(p1, p2), p)) {
            return 0;
        }
        sum += arg((p2 - p) / (p1 - p));
    }
    return std::abs(sum) < pi / 2 ? 2 : 1;
}

int main() {
    vector<double> x(4), y(4), z(4);
    for(int i = 0; i < 4; ++i) {
        cin >> x[i] >> y[i] >> z[i];
    }

    point g(accumulate(begin(x), end(x), 0.0) / 4, accumulate(begin(y), end(y), 0.0) / 4);
    polygon poly;
    for(int i = 0; i < 3; ++i) {
        poly.emplace_back(x[i], y[i]);
    }

    switch(is_in_polygon(poly, g)) {
        case 0: cout << "Unstable" << endl; break;
        case 1: cout << "Standing" << endl; break;
        case 2: cout << "Falling" << endl; break;
        default: assert(false);
    }
}

感想

これ競プロの問題としてどうなの．

2014 Yandex.Algorithm Elimination Stage, Round 3 C - Intervals

競プロ Yandex.Algorithm

問題文

http://codeforces.com/gym/100459

解法

しゃくとり法で解いた．
条件を満たさないようなペアの数を数えて，全体から引くことで求める．
しゃくとりの過程で，今現在の区間が overlap しうるので，その分は足すことで重複して引かないようにしている．

条件を満たさないような任意のペア (l, r) が，必ずしゃくとりの過程でカウントされることを証明する必要がある．
カウントされないような動きとしては，今見ている区間の右端が l と r の間にあるのに，左端を狭めるときに l と r の間に入り込んでしまう場合であり，これしかない．
しかし，右端が l と r の間にあり，かつ左端を狭めていく時は，必ず l か l の前で停止する．(l, r) の間に条件を満たすペアが無いことからこれは明らかである．
よって，任意の条件を満たさないペア (l, r) はしゃくとりの過程で必ずカウントされる．

ソースコード

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

using ll = long long;

int main() {
    int n, d;
    scanf("%d %d", &n, &d);
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    unordered_map<int, int> cnt;
    int l = 0, r = 0;
    int prev_r = -1;
    ll ans = 1LL * n * (n - 1) / 2;
    while(r < n) {
        while(r < n && cnt[a[r] + d] == 0 && cnt[a[r] - d] == 0) {
            cnt[a[r++]] += 1;
        }
        const ll width = r - l;
        const ll overlap = max(0, prev_r - l);
        ans -= width * (width - 1) / 2;
        ans += overlap * (overlap - 1) / 2;
        while(cnt[a[r] + d] > 0 || cnt[a[r] - d] > 0) {
            cnt[a[l++]] -= 1;
        }
        prev_r = r;
    }

    cout << ans << endl;
}

感想

この解法で解けそうだな～と思って通してしまった…．
証明はあとづけである．反省．しゃくとり書く時いつもこんな感じだ…．

2014 Yandex.Algorithm Elimination Stage, Round 3 B - Science

競プロ Yandex.Algorithm

問題文

http://codeforces.com/gym/100459

解法1

行列累乗で解く．
左から順番に見ていった時，状態としては k + 3 種類ある．
最初の second type が来た状態，途中の first type （k個の状態がある），最後の second type が来た状態（受理状態），それ以外
の k + 3 種類である．
あとはこれらの上での遷移を考えて，行列累乗する．

ソースコード1

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

using ll = long long;
using matrix = vector<vector<double>>;

matrix make_matrix(int n) {
    return vector<vector<double>>(n, vector<double>(n));
}

matrix operator*(matrix const& a, matrix const& b) {
    assert(a.size() == b.size() && a[0].size() == a.size());
    const int n = a.size();
    auto res = make_matrix(n);
    for(int i = 0; i < n; ++i) {
        for(int k = 0; k < n; ++k) {
            for(int j = 0; j < n; ++j) {
                res[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return res;
}

vector<double> operator*(matrix const& a, vector<double> const& b) {
    assert(a.size() == a[0].size() && a.size() == b.size());
    const int n = b.size();
    vector<double> res(n);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            res[i] += a[i][j] * b[j];
        }
    }
    return res;
}

matrix eye(int n) {
    auto res = make_matrix(n);
    for(int i = 0; i < n; ++i) {
        res[i][i] = 1;
    }
    return res;
}

matrix pow(matrix a, ll n) {
    auto res = eye(a.size());
    while(n > 0) {
        if(n & 1) {
            res = res * a;
        }
        a = a * a;
        n >>= 1;
    }
    return res;
}

int main() {
    cout << fixed << setprecision(10);

    ll n, k;
    cin >> n >> k;

    if(k + 2 > n) {
        cout << 0 << endl;
        return 0;
    }

    auto a = make_matrix(k + 3);
    a[0][0] = 0.5; // invalid -> invalid
    a[0][k + 1] = 0.5; // over second type
    for(int i = 0; i < k + 2; ++i) { // to first second type
        a[1][i] = 0.5;
    }
    for(int i = 1; i + 1 <= k + 1; ++i) {
        a[i + 1][i] = 0.5; // put first type
    }
    a[k + 2][k + 1] = 0.5; // to accepted
    a[0][k + 1] = 0.5;     // over first type
    a[k + 2][k + 2] = 1.0; // accepted
    vector<double> b(k + 3);
    b[0] = 1;

    a = pow(a, n);
    const auto ans = a * b;

    cout << ans[k + 2] << endl;
}

解法2

個数の期待値なので，どこにできるかで完全に独立して考えられる．
n - k - 1 箇所に目的の列が現れる可能性があり，それらの確率も同じである．
よって，(n - k - 1) * (0.5)^(k + 2) が答えになる．

ソースコード2

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

using ll = long long;

double solve2(ll n, ll k) {
    if(k >= n - 1) return 0;
    double res = n - k - 1;
    for(int i = 0; i < k + 2; ++i) res /= 2;
    return res;
}

int main() {
    cout << fixed << setprecision(10);

    ll n, k;
    cin >> n >> k;
    cout << solve2(n, k) << endl;
}

感想

反射で行列累乗したの頭悪かった…．というか行列累乗でできると思うなら2つ目がすぐ思いつくはずなんだけどな…．運でACしたんではみたいな気持ちになってきた．

2014 Yandex.Algorithm Elimination Stage, Round 2 F - Permutation Cube

競プロ Yandex.Algorithm

問題文

http://codeforces.com/gym/100453

解法

X, Y, Z のそれぞれについて，巡回するいくつかのグループに分けることができる．
周期 a で巡回する列と，周期 b で巡回する列と，周期 c で巡回する列を考える．これらはそれぞれ X, Y, Z から持ってくるとする．
このとき，これらの全体としての周期は lcm(a, b, c) である．
これは何を意味するかと言うと，この3つの列のすべての数を網羅するためには，a * b * c / lcm(a, b, c) 回のコスト1の移動が必要であるということである．
したがって，X, Y, Z のそれぞれについて，巡回する部分のサイズをそれぞれ求めて，3重ループですべての3組の巡回列について計算すればよい．
当然これをそのままやるとオーダーがヤバイのだが，同じサイズの巡回列は map でまとめてしまうとオーダーが落ちる．
なぜなら，高々サイズの種類数は sqrt(N) 通りしか無いからである(1 + 2 + ... + N = N * (N + 1) / 2 であるため）．
よって，この3重ループは O(Nsqrt(N)) となり，間に合う．

ソースコード

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

using ll = long long;

ll lcm(ll a, ll b, ll c) {
    const ll t = a * b / __gcd(a, b);
    return t * c / __gcd(t, c);
}

class union_find {
public:
    union_find(int n) : par(n, -1) {}

    int root(int x) {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) return;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }

    int size(int x) {
        return -par[root(x)];
    }

private:
    vector<int> par;
};

int main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n), z(n);
    vector<union_find> uf(3, n);
    for(int i = 0; i < n; ++i) {
        cin >> x[i];
        uf[0].unite(i, x[i] - 1);
    }
    for(int i = 0; i < n; ++i) {
        cin >> y[i];
        uf[1].unite(i, y[i] - 1);
    }
    for(int i = 0; i < n; ++i) {
        cin >> z[i];
        uf[2].unite(i, z[i] - 1);
    }

    vector<vector<bool>> used(3, vector<bool>(n));
    vector<unordered_map<int, int>> cnt(3);
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < n; ++j) {
            const int r = uf[i].root(j);
            if(used[i][r]) continue;
            used[i][r] = true;
            cnt[i][uf[i].size(r)] += 1;
        }
    }

    ll ans = 0;
    for(auto& p1 : cnt[0]) {
        for(auto& p2 : cnt[1]) {
            for(auto& p3 : cnt[2]) {
                const ll sz1 = p1.first, sz2 = p2.first, sz3 = p3.first;
                const ll cycle = lcm(sz1, sz2, sz3);
                ans += sz1 * sz2 * sz3 / cycle * p1.second * p2.second * p3.second;
            }
        }
    }

    cout << ans << endl;
}

感想

さすがに典型．油断してるとオーバーフローするのが罠なぐらいか．

2014 Yandex.Algorithm Elimination Stage, Round 2 D - Inversions

競プロ Yandex.Algorithm

問題文

http://codeforces.com/gym/100453

解法

長さを最小化するので，N * (N - 1) / 2 >= K && (N - 1) * (N - 2) / 2 < K となる最小の N を求める．
あとは，上から順に，その位置の値を変えなければならないところまで順番に 1 から埋めていく．
その場所まで来たら，変えないと行けない数字と swap して，残りの後ろの数を降順に並べるだけ．

コード読んだほうが早い．いつものやつだし．

計算量は O(NlogN)

ソースコード

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

int main() {
    int K;
    cin >> K;

    int sz = 1;
    while(sz * (sz - 1) / 2 < K) ++sz;

    vector<int> ans(sz);
    iota(begin(ans), end(ans), 1);
    for(int i = 0; i < sz; ++i) {
        const int sz2 = sz - i;
        const int offset = K - (sz2 - 1) * (sz2 - 2) / 2;
        if(offset > 0) {
            swap(ans[i], ans[i + offset]);
            sort(begin(ans) + i + 1, end(ans));
            reverse(begin(ans) + i + 1, end(ans));
            break;
        }
    }

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