第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes
問題
考察
部分点解法
スライム$ iがスライム$ i + j (j > 0)に合体する場合の数がどれだけあるか考えてみます。
$ i + j \neq N - 1のとき
スライム$ iがスライム$ i + jに合体するには、$ i+1, i+2, \dots, i + j - 1までが$ iより先に選ばれる必要があります。
なので、
選ぶ順$ N - 1個のうち$ j + 1個の場所を確保し $ \cdots {}_{N-1} C_{j+1}
最後に$ i + j、最後から二番目に$ iを入れる
残りの$ i + 1, i + 2, \dots, i + j - 1の並べ方 $ \cdots (j - 1)!
$ i, \dots, i + j 以外のものの並べ方 $ \cdots (N - 1 - (j + 1))!
$ {}_{N-1} C_{j+1} (j - 1)! (N - 2 - j)! = \frac{(N-1)!}{j(j+1)}
$ i + j = N - 1のとき
$ iと$ N - 1の間に、選ばれて良いのは$ iより小さいものです。$ iより小さいもののうち$ k個を使うとすると、
$ iより小さい$ i個のうち$ k個を選んで並べる $ \cdots { }_i P _k
それ以外のものを並べる $ \cdots (N - 1 - (k + 1))!
階乗を事前に計算しておけばこれで$ O(N^2)になります。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int N;
vector<int> x;
int main() {
cin >> N;
x.resize(N);
Combination<ModInt> comb(N + 1);
ModInt ans = 0;
rep(i, N - 1) {
for (int j = 1; i + j < N - 1; ++j) {
ans += comb.factorial(N - 1) / j / (j+1) * (xi + j - xi); }
for (int k = 0; k <= i; ++k) {
ans += comb.P(i, k) * comb.factorial(N - 2 - k) * (xN - 1 - xi); }
}
cout << ans << endl;
return 0;
}
mod.hppやcombination.hppの中身が気になる場合には提出コードを見てください。
満点解法
$ i, i+1が部分としても含めてどれだけ使われるかについて考えます。
$ i, i + 1を通過するスライムの個数の期待値を$ c_iとすると、 最初に$ i番目のスライムが選ばれて、残り$ i -1個のスライムがある状況になる $ \cdots \frac{1}{i}(1 + c_{i-1})
最初に$ i番目以外のスライムが選ばれて$ i, i + 1を通らずに合成されて、残り$ i - 1個ある状況になる $ \cdots \frac{i-1}{i} c_{i-1}
$ c_i = \frac{1}{i}(1 + c_{i-1}) + \frac{i-1}{i} c_{i-1} = c_{i-1} + \frac{1}{i}
となるので、$ c_i = \sum_{j=1}^{i} \frac{1}{j}です。この和を事前計算をしていないと$ O(N^2)、すれば$ O(N)です。
code:cpp
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i) #define all(a) (a).begin(), (a).end() int N;
vector<int> x;
int main() {
cin >> N;
x.resize(N);
Combination<ModInt> comb(N);
vector<ModInt> S(N + 1, 0);
rep(i, N) Si + 1 = Si + comb.factorial(N - 1) / (i + 1); ModInt ans = 0;
cout << ans << endl;
return 0;
}
参考
https://www.youtube.com/watch?v=TIiDKDNFob0&feature=youtu.be