ARC054 C - たい焼き

解法

2部グラフの完全マッチングの個数の偶奇性を問う問題.
当然数え上げるのは無理.しかし偶奇だけなら,行列式でわかる.

与えられた隣接行列を Aとする.
すると,完全マッチングの個数 M は,A のパーマネントに等しい事がわかる.
パーマネントを求めるのは困難だが,偶奇だけなら,行列式に一致する.
行列式は,パーマネントに置換の符号がついたものである.置換の符号は -1 か 1 だから,mod 2 の上ではこれらはともに 1 に等しく,隣接行列は,mod 2 上で行列式とパーマネントが一致する.

行列式は O(n^3) でもとまるので,これでACをもらうことができる.

ソースコード

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

bool det(vector<vector<int>> v) {
    const int n = v.size();
    bool res = 1;
    for(int i = 0; i < n; ++i) {
        int pivot = i;
        for(int j = i + 1; j < n; ++j) {
            if(v[j][i]) {
                pivot = j;
            }
        }
        swap(v[pivot], v[i]);
        res &= v[i][i];
        if(!v[i][i]) {
            break;
        }
        for(int j = i + 1; j < n; ++j) {
            for(int k = n - 1; k >= i; --k) {
                v[j][k] = v[j][k] ^ v[i][k] & v[j][i];
            }
        }
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> v(N, vector<int>(N));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            char c;
            cin >> c;
            v[i][j] = c == '1';
        }
    }
    if(det(v)) {
        cout << "Odd" << endl;
    } else {
        cout << "Even" << endl;
    }
}

感想

有名事実らしいが,本番でこれを導き出せる人はすごいと思う.

ARC050 C - LCM 111

解法

1 が A 桁続いたものと,1 が B 桁続いたものの最大公約数 G は,1 が gcd(A, B) 桁続いたものになる.
例えば 111111 (A = 6) と 1111 (B = 4) の最大公約数は,1 が gcd(6, 4) = 2桁続いたもの.
これは,
111111 = 1111 * 100 + 11
11 = 11 * 1 + 0
のようにユークリッド互除法を適用していくと,1 が並んだものがどんどん小さくなっていく.この桁数が,gcd(A, B) に対応する.

あとは A * B / G を考えるだけなので,A,B / G がどうなるか考えば十分.
ここで 1 が並んだ数は
a(k+1) = 10a(k) + 1, a(1) = 1
つまり
a(k+2) = 11a(k+1) - 10a(k)
となる数列と考えられるので,これは行列累乗で求められる.これで A は求まった.

次に,B / G を考える.これは 1000100010001...1 のような形をしていることがわかる.1 が現れる間隔が,G に対応しているので,これは
b(k+1) = 10^G b(k) + 1, b(1) = 1
という数列,つまり
b(k+2) = (10^G + 1)b(k+1) - 10^G b(k)
という数列で表される.
B はこれの B / D 項なので,同様に行列累乗で求める.

ソースコード

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

// matrix は長いので略

int main() {
    ll A, B, M;
    cin >> A >> B >> M;
 
    ll g = __gcd(A, B);
    vector<ll> b1 = {11, 1};
    vector<ll> b2(2);
    b2[0] = modpow(10, g, M) + 1;
    b2[1] = 1;
    auto C = make_matrix<ll>(2, 2);
    C[0][0] = 11; C[0][1] = -10 + M;
    C[1][0] = 1;
    C = modpow(C, A - 1, M);
    auto C2 = make_matrix<ll>(2, 2);
    C2[0][0] = modpow(10, g, M) + 1;
    C2[0][1] = -modpow(10, g, M) + M;
    C2[1][0] = 1;
    C2 = modpow(C2, B / g - 1, M);
    
    ll x = modmul(C, b1, M)[1];
    ll y = modmul(C2, b2, M)[1];
    cout << (x * y) % M << endl;
}

感想

行列累乗じゃないコードのほうがスッキリしてた.
1111 ... を等比数列みたいに捉えるのに時間がかかってしまった.

ARC055 B - せんべい

解法

dp[i][j][ate_max] := i 番目まで見て,j 個食べていて,現時点で最大のものを食べている(ate_max: bool) 状態から始めたとき,最終的に N を食べられる確率
と定義する.
dp[N][j][1] が,確率 1 に相当する.(N 枚まで見て max を食べているなら,それは N にほかならない.この状態から始めれば当然確率 1.)

遷移は,以下の3通り.
1. 今食べようとしているせんべいが過去最大であり,それを食べる
2. 今食べようとしているせんべいが過去最大であり,それを食べない
3. 今食べようとしているせんべいは過去最大でないため,それを食べない

過去最大でないせんべいを食べる必要性は全く無いので,それは考えない.
今食べようとしているせんべいが過去最大である確率は,nCi * (i - 1)! / (nPi) = 1/i となる.ケース1 と 2 の大きい方と,3 を足し合わせたものが答え.

ソースコード

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

int N, K;

double rec(int n, int k, bool ate_max, vector<vector<vector<double>>>& dp) {
    double& res = dp[n][k][ate_max];
    if(res != -1) {
        return res;
    }
    if(n == N) {
        return res = ate_max;
    }

    res = 0;

    // 今見ているせんべいが今までで最大である場合 食べる or 食べない
    double eat = (k < K ? 1.0 / (n + 1) * rec(n + 1, k + 1, true, dp) : 0);
    double not_eat = 1.0 / (n + 1) * rec(n + 1, k, false, dp);
    res += max(eat, not_eat);
    // 今見ているせんべいが今までで最大でない場合 食べないのが最善
    res += 1.0 * n / (n + 1) * rec(n + 1, k, ate_max, dp);
    return res;
}

int main() {
    cin >> N >> K;
    vector<vector<vector<double>>> dp(N + 1, vector<vector<double>>(K + 1, vector<double>(2, -1)));
    cout << fixed << setprecision(10) << rec(0, 0, 0, dp) << endl;
}

感想

普通に難しいと思うんだけどナア.
めっちゃ簡単じゃんと言われたことがあり,とてもつらい気持ちになっています.

Codeforces Round #292 (Div. 1) D. Drazil and Morning Exercise

問題概要

木 T が与えられる.また,クエリが q 回投げられる.それぞれのクエリは L を投げてくる.
木 T の頂点 i に対して,i からそこから最も遠い葉までの距離を D(i) とする.
各クエリに対し,T の部分木 S で,かつ S の任意の二頂点 i, j が |D(i) - D(j)| <= L となるようなものの中で,最も大きいものの大きさを求めよ.
D(i) はあくまでも T での距離であって,S での距離ではないことに注意.

・制約
1 <= n <= 10^5
1 <= q <= 50
1 <= L <= 10^11

解法

全方位木DP,Union-Find木で解ける.
T においてもっとも遠い葉までの距離を,全方位木DPで求める.
そうして得られた距離 d[i] を,降順にソートする.
あとはソートして得られた距離の列上で,前からしゃくとりする.最大が x なら x - L までは含んで良い.
しゃくとりで新たに頂点を追加する場合,その頂点の隣接点で,今現在追加されている頂点があるなら,そこと union-find でマージする.
しゃくとりで左端を縮めるときは,union-find のサイズを1つ小さくするだけでよい.
これは,d を降順でソートしているからである.もし昇順にしてしまうと,サイズを1減らすだけではおかしな値になる.
(イメージとしては,葉の方から根の方にどんどん集合が集まってくる感じ.根からスタートすると,途中で分岐したときに集合を完全にわけないとだめになって,サイズを 1 減らすだけでは対応できない.葉の方からスタートすると,途中でくっつくことがあっても別れることはない.)

ソースコード

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

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

struct edge {
    int to;
    ll cost;
};

using edges = vector<edge>;
using graph = vector<edges>;

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

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) {
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

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

    void dec(int x) {
        par_[root(x)] += 1;
    }

private:
    std::vector<int> par_;
};

void dfs(int v, int prev, graph const& g, vector<ll>& d) {
    d[v] = 0;
    for(auto& e : g[v]) {
        if(e.to == prev) {
            continue;
        }
        dfs(e.to, v, g, d);
        d[v] = max(d[v], d[e.to] + e.cost);
    }
}

void dfs2(int v, int prev, ll par_d, graph const& g, vector<ll> const& d, vector<pll>& res) {
    res[v].second = v;
    vector<pll> child = {{0, -1}};
    for(auto& e : g[v]) {
        if(e.to == prev) {
            child.emplace_back(par_d + e.cost, e.to);
        } else {
            child.emplace_back(d[e.to] + e.cost, e.to);
        }
    }
    sort(child.rbegin(), child.rend());
    res[v].first = child[0].first;

    for(auto& e : g[v]) {
        if(e.to == prev) {
            continue;
        }
        if(e.to == child[0].second) {
            dfs2(e.to, v, child[1].first, g, d, res);
        } else {
            dfs2(e.to, v, child[0].first, g, d, res);
        }
    }
}

int main() {
    int n;
    cin >> n;
    graph g(n);
    for(int i = 0; i < n - 1; ++i) {
        int x, y;
        ll v;
        cin >> x >> y >> v;
        x--;
        y--;
        g[x].push_back(edge{y, v});
        g[y].push_back(edge{x, v});
    }
    vector<ll> tmp_d(n);
    vector<pll> d(n);
    dfs(0, -1, g, tmp_d);
    dfs2(0, -1, 0, g, tmp_d, d);
    sort(d.rbegin(), d.rend());

    int q;
    cin >> q;
    while(q--) {
        ll L;
        cin >> L;
        int l = 0, r = 0;
        vector<bool> used(n);
        union_find uf(n);
        int res = 0;
        while(r < n) {
            while(r < n && d[l].first <= d[r].first + L) {
                for(auto& e : g[d[r].second]) {
                    if(used[e.to]) {
                        uf.unite(e.to, d[r].second);
                    }
                }
                used[d[r].second] = true;
                r++;
            }
            res = max(res, uf.size(d[l].second));
            uf.dec(d[l].second);
            used[d[l].second] = false;
            l++;
        }
        cout << res << endl;
    }
}

感想

オーバーフローに気づかなくで大量に時間を溶かしてしまった.
UnionFind ってこういう使い方もあるんだなあと勉強になった.

JOI 春合宿2015 コピー&ペースト2

問題概要

文字列 S が与えられる.
S に対して,クエリが N 個投げられる.
各クエリは A, B, C を持ち,これは S の部分文字列 [A, B) を位置 C の直前にコピー挿入することを意味する.
最終的にできた S の先頭 K 文字を答えよ.
ただし,操作の途中で M 文字を超えた場合は,M 文字以降を削るものとする.

・制約
1 <= K <= 200
1 <= M <= 10^9
K <= S <= min(M, 2 * 10^5)
1 <= N <= 2 * 10^5

解法

K が小さいことに気が付かず,平衡二分探索木を書き始めて辛い思いをしていた.
実際,K が大きければこれで良い.
今回は 1 <= K <= 200 なので,O(KN) が間に合う.
やり方は,操作を逆順に見るという定番のテクで求めていく.

今 t 番目の文字が,ある操作の直前にどこにあったかを考えれば,最終的にどの文字になるかがわかる.
これをすべての 0 <= t < K に対してやる.
1. i 番目の操作で t 番目の文字が変化しない
2. i 番目の操作で t 番目の文字は挿入された文字の一部(overlap)になる.
3. i 番目の操作で t 番目の文字は挿入によって単に後ろにずれる.
のいずれかだから,場合分けしてやればよい.

ソースコード

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

int main() {
    int K, M, N;
    string S;
    cin >> K >> M >> S >> N;
    vector<int> A(N), B(N), C(N);
    for(int i = N - 1; i >= 0; --i) {
        cin >> A[i] >> B[i] >> C[i];
    }
    string res;
    for(int i = 0; i < K; ++i) {
        int t = i;
        for(int j = 0; j < N; ++j) {
            if(t < C[j]) {
                continue;
            } else if(t < C[j] + (B[j] - A[j])) {
                t = A[j] + t - C[j];
            } else {
                t = t - (B[j] - A[j]);
            }
        }
        res += S[t];
    }
    cout << res << endl;
}

感想

制約はちゃんと読もうね.

CSAcademy - Xor Closure

問題概要

N 項からなる数列 {a_n} が与えられる.この数列にいくつか数を追加して,以下の性質を満たすようにする.

  • 相異なる任意の i, j に対して,a_i XOR a_j もまた数列 {a_n} に含まれる

このとき,{a_n} にいくつ数を追加すれば上記の性質を満たすようにできるか?

・制約
1 <= N <= 10^5
{a_n} の要素は相異なる.

解法

線形空間の定義そのままであることに気づければ勝ち.
つまり,この問題は,与えられた01ベクトル列の基底(というか次元)を求めてね,という問題に帰着できる.
次元を K とすると,答えは 2^K - N となる.

もうちょっと丁寧に書くと(とはいってもほとんど同じだけど),
{a_n} を 01上の線形(部分)空間にすることが目標.
二元体のベクトルが XOR と AND で線形空間をなすのは有名事実である.
部分空間 W の定義として,
任意の x, y ∈ W にたいして x + y ∈ W である
がある.これは問題文と同じ.
基底を e1, e2, ..., eK とすると,W の任意の元は
x = (c1 AND e1) XOR ... XOR (cK AND eK)
と表せるので,この線形空間の要素数は係数の割り当て方で 2^K 通り.
もともと N 個あるわけだから,2^K - N が答え.

ソースコード

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

using ull = unsigned long long;

// 直交するように基底を選んでいく
void binary_basis_insert(vector<ull>& w, ull a) {
    for(auto v : w) {
        if(v & (-v) & a) {
            a ^= v;
        }
    }
    if(a == 0) { // すでに生成可能
        return;
    }
    for(auto& v : w) {
        if(a & (-a) & v) {
            v ^= a;
        }
    }
    w.push_back(a);
}

vector<ull> binary_basis(vector<ull> const& w) {
    vector<ull> res;
    for(auto v : w) {
        binary_basis_insert(res, v);
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<ull> a(N);
    for(int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    auto basis = binary_basis(a);
    cout << (1ULL << basis.size()) - N << endl;
}

感想

http://codeforces.com/contest/587/problem/E
Codeforcesでほとんど同じ問題がある.Codeforcesのほうが難しい.

ARC025 C - ウサギとカメ

解法

制約をみて,なんとなく全頂点を始点としてダイクストラできるなーと検討はつく.
とりあえず,目的地を決め打ちしてしまって,目的地を始点にダイクストラする.
その後,得られた距離 d[i] をソートしておく.
次に,カメのスタート地点を決め打ちして,中継地点からの距離を D とする.
すると,ウサギは D / T < d[i] / R を満たすような d,つまり D * R / T < d[i] を満たすような中継点からスタートすれば良いことがわかる.
このような i の個数は,ソートしておいた距離の候補上で二分探索すれば求めることができる.
ただし,ウサギがカメより遅い場合は,同じスタート地点からスタートしないように -1 しておく必要がある.

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

ソースコード

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

using ll = long long;
using weight = double;

constexpr weight INF = 1e9;

struct edge {
    int from, to;
    weight cost;

    bool operator<(edge const& rhs) const {
        return cost > rhs.cost;
    }
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to, weight cost) {
    g[from].push_back(edge{from, to, cost});
}

std::vector<weight> dijkstra(graph& g, int s) {
    using P = std::pair<weight, int>;
    std::vector<weight> d(g.size(), INF);
    std::priority_queue<P, std::vector<P>, std::greater<P>> que;
    fill(d.begin(), d.end(), INF);
    d[s] = 0;
    que.push(P{0, s});

    while(!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if(d[v] < p.first) {
            continue;
        }
        for(int i=0; i<g[v].size(); ++i) {
            edge e = g[v][i];
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P{d[e.to], e.to});
            }
        }
    }
    return d;
}


int main() {
    int N, M;
    double R, T;
    cin >> N >> M >> R >> T;
    graph g(N);
    for(int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        add_edge(g, a, b, c);
        add_edge(g, b, a, c);
    }

    ll res = 0;
    for(int i = 0; i < N; ++i) {
        auto d = dijkstra(g, i);
        sort(d.begin(), d.end());
        for(int j = 1; j < N; ++j) {
            auto t = upper_bound(d.begin(), d.end(), d[j] * R / T) - d.begin();
            res += N - t - (t <= j);
        }
    }
    cout << res << endl;
}

感想

ウサギよりカメが早いケース,WA生やさずに気づけたけど完全に罠.
まあカメって走ると意外と早いからね.