AOJ 1333 Beautiful Spacing

問題文

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

問題文

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

問題文

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

問題文

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

問題文

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

問題文

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

2014 Yandex.Algorithm Elimination Stage, Round 2 B - Remainders

問題文

http://codeforces.com/gym/100453

解法

ある数 a_i からスタートした時に，それ以上の値で余りをとっても変化はない．
したがって，数列をまずソートし，最初にする数字を何にするか全部試すのが良さそうである．
これは dp で計算できて，
dp[i] := 大きい方から i 番目まで見た時に，あまりとしてありえる数字の集合
とすると，
dp[i] = dp[i - 1] + (dp[i - 1] に含まれる数を a[i] で割った余り) + a[i]
となる（+ は集合の和とする）．

dp[i - 1] の部分についてだが，途中で a_j で割った後にそれ以上の値 a_k で割っても変化がないという議論のとおり，a_i を最初に選んだ後，それ以下の数字 a_j を次に選んだとすれば，a_j <= a_k <= a_i となる a_k は無視してよくなる．
これをあらわすのが dp[i - 1] の部分である．
あとの2項はそれはそう．

最後に，今できている数字の集合のうち，数列の最小の値以下のものをカウントすると答えになる．以下である理由は，最小値を一番最初の数に選べば，ずっと最後まで残るからである．
ただし，数列に含まれる最小値が複数ある場合は，その値自体を取ることが不可能であるので，その場合は未満でカウントする．

計算量は O(N * max(a[i])) である．

ソースコード

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(rbegin(a), rend(a));

    unordered_set<int> dp;
    for(int i = 0; i < n; ++i) {
        unordered_set<int> nxt = dp;
        nxt.insert(a[i]);
        for(auto x : dp) {
            nxt.insert(x % a[i]);
        }
        dp = move(nxt);
    }

    int ans = 0;
    const int lim = a.back() == a[a.size() - 2] ? a.back() - 1 : a.back();
    for(auto x : dp) {
        ans += x <= lim;
    }

    cout << ans << endl;
}

感想

すぐに書けたけど，よく考えるとうまくできてる問題だなあ．