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したんではみたいな気持ちになってきた．
2014 Yandex.Algorithm Elimination Stage, Round 2 F - Permutation Cube
解法
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
解法
長さを最小化するので，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
解法
ある数 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; }
感想
すぐに書けたけど，よく考えるとうまくできてる問題だなあ．
2014 Yandex.Algorithm Elimination Stage, Round 2 A - Cycles with Common Vertex
問題概要
n 個の鎖が与えられ，それぞれのサイズは c_i である．
鎖とは，連結グラフであり，かつ両端点以外の頂点の次数が2であるものである．
これらの鎖を，鎖とは別に用意した1つの頂点 X に，その両端をつなげる．
こうしてできたグラフ（Xに輪っかがいっぱいついてるみたいなグラフ）の何箇所かを黒で塗る．
ただし，任意の黒で塗られた頂点間の最短距離が K 以上となるように塗らなければならない．
このとき，最大何箇所を黒で塗ることができるか？
・制約
1 <= N <= 10^5
1 <= K <= 10^5
K <= c_i <= 10^9
解法
各輪っかのサイズは c_i + 1 になり，K個置きに黒く塗る．
すると，各輪っかについて，黒く塗られていない最大の連続した部分があるはずである．
その部分の真中に，X が来るようにする．
すると，X から各鎖について，黒く塗られている場所までの距離は K/2 以上となる（ただし，K / 2 は整数での割り算であり，切り捨てである）．
したがって，このように配置すれば，異なる鎖に含まれる黒同士の距離は K / 2 * 2 以上となり，基本的に最大に色をぬることができる．
ただし，切り捨てであるから，実際は K / 2 == (K - 1) / 2 となる鎖がいくつか含まれる可能性がある．
そのような鎖の数を M とすると，それらのうちから M - 1 個選んで，黒く塗る箇所を1つ諦めるしかない．
以上で，O(N) で解けた．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int N, K; cin >> N >> K; vector<int> c(N), space(N); int cnt = 0; for(int i = 0; i < N; ++i) { cin >> c[i]; space[i] = (K + ((c[i] + 1) % K)) / 2; cnt += space[i] * 2 < K; } ll ans = 0; for(int i = 0; i < N; ++i) { ans += (c[i] + 1) / K; } ans -= max(0, cnt - 1); cout << ans << endl; }
感想
A問題にしては難しくない？若干迷走してしまった．
2014 Yandex.Algorithm Elimination Stage, Round1 F - Data Mining
問題概要
n 個の要素からなる数列 a が与えられる．あなたは以下の操作を k 回行える．
- ある要素の値を隣接する（どちらかの1方の）要素に加える．
k 回の操作の後の，数列に含まれる値の最小値を最大化せよ．
また，出力はその値を 10^9+7 で割った余りで出力するものとする．
・制約
1 <= n <= 10^4
1 <= k <= 10^6
1 <= a_i <= 10^8
解法
K < N の時は，どう頑張っても a の K + 1 番目の値より大きく出来ず，また逆にこれを実現する分配方法が存在するので，ソートして K + 1 番目の値を出力する．
K >= N のときは，できるだけでかい隣接2項を互いに足し合わせまくって，最後の N - 1 回で残りに足していく感じ．
どの隣接2項が良いかを考えるのだが，互いに足し合わせる操作は N - K + 1 回行われることを考えれば，ある a[i] と a[i + 1] を選んだときの答えは
fib(N - K + 1) * min(a[i], a[i + 1]) + fib(N - K + 2) * max(a[i], a[i + 1])
である．
これが一番大きいものを選べばよいのだが，N - K + 1 が大きいとオーバーフローして計算できないので，long double でごまかす．
とはいっても十分小さい K に対してはフィボナッチ数の比が黄金比に十分近づいていないので，愚直にやらないといけない．
具体的には，N - K + 1 > 40 のとき（これはかなり雑で，オーバーフローギリギリを狙うのが良いと思う），黄金比を φ として
min(a[i], a[i + 1]) + ma(a[i], a[i + 1]) * φ
の大きさで一番大きい i を選択する．
あとは先の値を mod で計算すれば答えになる．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; constexpr int mod = 1e9 + 7; int main() { int k, n; cin >> k >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } if(k < n) { sort(begin(a), end(a)); cout << a[k] << endl; } else { vector<ll> fib(k + 1); fib[1] = fib[2] = 1; for(int i = 3; i < k + 1; ++i) { fib[i] = (fib[i - 1] + fib[i - 2]) % mod; } ll ans = 0; if(k - n + 2 <= 40) { for(int i = 0; i + 1 < n; ++i) { ans = max(ans, fib[k - n + 1] * min(a[i], a[i + 1]) + fib[k - n + 2] * max(a[i], a[i + 1])); } ans %= mod; } else { const ld phi = (1.0 + sqrt(5.0)) / 2.0; int pos = 0; ld val = 0; for(int i = 0; i + 1 < n; ++i) { if(val < min(a[i], a[i + 1]) + max(a[i], a[i + 1]) * phi) { pos = i; val = min(a[i], a[i + 1]) + max(a[i], a[i + 1]) * phi; } } const ll mi = min(a[pos], a[pos + 1]); const ll ma = max(a[pos], a[pos + 1]); ans = (((fib[k - n + 1] * mi) % mod) + ((fib[k - n + 2] * ma) % mod)) % mod; } cout << ans << endl; } }
感想
誤差が不安だったけど，fib(41) / fib(40) の比率がもうほとんど正確な黄金比に近い値になっているので大丈夫なんでしょうきっと．
2014 Yandex.Algorithm Elimination Stage, Round1 E - Burger Bar
問題概要
n 個の要素からなる数列 a が1つ与えられる．
以下を満たす集合 X のうち，最小の |X| をもとめよ．
- X = {b_1, ..., b_k} とすると，任意の a の要素は，Xの要素のうちからいくつか選んで足し合わせて作ることができる（ただし，おなじ i に対して b_i を2回使うことはできない）．
・制約
1 <= n <= 20
1 <= a_i <= 50
解法
a_i のサイズが高々50であるから，解の上界は6である．
50C5 = 2 * 10^6 ぐらいなので，5個までを適当に全探索しても間に合いそう．
多分条件を満たすXがたくさんあるので，条件を満たすかチェックする分のオーダーを入れてもそんなに遅くないと思う．
ソースコード
#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]; } vector<int> used; function<bool(int)> can_make = [&](int limit) { if((int)used.size() == limit) { vector<bool> dp(51, false); dp[0] = true; for(int i = 0; i < limit; ++i) { for(int j = 50 - used[i]; j >= 0; --j) { dp[j + used[i]] = dp[j + used[i]] | dp[j]; } } bool ok = true; for(int i = 0; i < n; ++i) { ok &= dp[a[i]]; } return ok; } else { for(int i = (used.size() == 0 ? 1 : used.back() + 1); i <= 50; ++i) { used.push_back(i); if(can_make(limit)) { return true; } used.pop_back(); } return false; } }; int ans = 6; for(int i = 1; i <= 5; ++i) { if(can_make(i)) { ans = i; break; } } cout << ans << endl; }
感想
まさかEまできて全探索を書かされるとは思わなかった．
