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まできて全探索を書かされるとは思わなかった．
2014 Yandex.Algorithm Elimination Stage, Round1 D - Splitting Money
問題概要
n 個の数列が与えられる．
各要素について，集合Aとして使うか，集合Bとして使うか，あるいは使わないかを選択できる．
最終的に，集合Aとして使った数字のXORと，集合Bとして使った数字のXORが等しくなるようにしたい．
そのような集合AとBは何通りあるか．ただし，同じ数字であっても，元の数列で違う位置にあるものであれば，それらは区別するものとする．
・制約
1 <= n <= 10^4
1 <= a_i <= 10^4
解法
まず，数字の値が小さいことに注目する．
また，集合AのXORと集合BのXORが等しいとは，そもそもどちらかの集合に含めるとしたすべての要素のXORが0であることと同値である．
そのように数字を選んだ場合，各要素をどちらに振り分けても，それぞれのXORの値は等しくなる．
以上の2つから，以下の dp で計算することができる．
dp[i][j] := i 番目の要素まで見て，どちらかの集合として使う要素の XOR の値が j となるような値の振り分け方
ある数字を集合として使う時，どちらの集合に入れるかで2通りあるので，遷移は
dp[i + 1][j ^ a[i]] += dp[i][j] * 2
となる．
計算量は O(n * a_i) ．
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int mod = 1e9 + 7; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } vector<int> dp(1 << 14); dp[0] = 1; for(int i = 0; i < n; ++i) { auto nxt = dp; for(int j = 0; j < (int)dp.size(); ++j) { const int x = j ^ a[i]; if(x < (int)nxt.size()) { (nxt[x] += (2 * dp[j]) % mod) %= mod; } } dp = move(nxt); } cout << dp[0] << endl; }
2014 Yandex.Algorithm Elimination Stage, Round1 C - Non-Convex Quadrilaterals
問題概要
n 個の整数が与えられる．それらから4つ選んで，四角形の4辺の長さとする．
もちろん選び方によっては四角形が作れないが，そういう選び方は出来ないものとする．
こうしてできる四角形のうち，凹四角形であるもののなかで，周の長さが最も大きいものの値はなにか？
・制約
1 <= n <= 10^4
1 <= a_i <= 10^8
解法
実際に四角形を書けばすぐわかるが，ほとんどの四角形はいい感じに変形すると，
おなじ4辺をもつ凹四角形に変形できる．
したがって，基本的に四角形が作れるならそれは凹四角形にできるから，数字の大きい方から4つ選んでいって，実際に四角形を構築できるか考えれば十分である．
四角形が構築できる条件は，4つの辺のうちの最大の長さが他の3辺の長さの和未満であることである．
コーナーケースが1つあり，それは正方形である．これはどう変形しても凹四角形にできない．
計算量はソートの分で O(nlogn)．
ソースコード
#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)); int ans = -1; for(int i = 0; i + 3 < n; ++i) { if(a[i] == a[i + 1] && a[i] == a[i + 2] && a[i] == a[i + 3]) continue; // square int sum = 0; for(int j = i + 1; j <= i + 3; ++j) { sum += a[j]; } if(sum > a[i]) { ans = a[i] + sum; break; } } cout << ans << endl; }
2014 Yandex.Algorithm Elimination Stage, Round1 B - Adjusting Ducks
問題概要
n 要素からなる数列が与えられる．また，ある要素の値を任意の数に変えることができる．その時，もとの値と変えた後の値をそれぞれ a, b として |a - b| のコストがかかる．この操作は何回でも行える．
この操作によって，数列に含まれる値として，単独で存在するものがないようにしたい．最小のコストはいくらかかかるか？
・制約
1 <= n <= 10^5
1 <= a_i <= 10^8
解法
基本的には値の近い2つの数字をペアにしていけば良さそうである．
よって，最初にソートして以下の dp をした．
dp[i][j] := i 番目の要素まで見て，その要素が直前の要素に変えられたか，あるいは直前の値を今見ている値に変えたかとしたときの最小コスト．
今見ている要素に直前の値を合わせる時，そのさらに前の（つまり2個前）要素は，今見ている要素に合わせるのは明らかに不利である．なぜなら，その場合は直前の要素に今の値を合わせたほうがコストが小さく済むからである．
したがって，この場合は2つ前の要素は，今見ている要素とは無関係に考えてよい．
次に，今見ている要素を直前の値に合わせるときは，同じような理由で2つ前の値は直前の値に変えられていると考えて良い．
この遷移のやり方だと，今見ている値を直前の値に合わせて，かつ2つ前の値をその前の値に合わせるようなものを考えていないようだが，実は問題ない．なぜなら，これは直前の値を今見ている値に合わせたのと同じだからであり，これは先程の遷移に含まれているからである．
以上で O(N) でこの問題をとくことができる．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <typename T> constexpr T inf; template <> constexpr ll inf<ll> = 1e18; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } sort(begin(a), end(a)); vector<vector<ll>> dp(n + 1, vector<ll>(2, inf<ll>)); dp[1][0] = dp[1][1] = abs(a[0] - a[1]); for(int i = 2; i < n; ++i) { dp[i][0] = dp[i - 1][1] + a[i] - a[i - 1]; dp[i][1] = min(dp[i - 2][1], dp[i - 2][0]) + a[i] - a[i - 1]; } cout << min(dp[n - 1][0], dp[n - 1][1]) << endl; }
感想
変な dp をしてしまったが，もっとわかりやすいのがありそう．うーん．
