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

問題文

解法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したんではみたいな気持ちになってきた．