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