yukicoder contest 380 E
解き方
※ ここに書く解き方は、解説とは異なり、FFTを使わない解き方である 精進期間中は毎日$ 1 分野以上選ぶことと、各友人には$ 1 日ずつ講師をお願いすることから、精進期間は最大$ N 日間である。
$ 1 以上$ N 以下の整数$ i それぞれについて、$ s_{i} を下記で定める数として、まずはこれを求める。
苦手分野を選ばない日（空いている日）があっても良いと制限を緩くした場合に、精進期間が$ i 日間となる日程の個数
同じ分野を教える友人に対し、同じ日に講師をお願いすることはできないため、$ s_{i} は下記のようにして求められる。
各分野$ j について教える友人が$ c_{j} 人のとき、どの友人にどの日に講師をお願いするかは$ {}_{i} P _{c_{j}} 通り考えられる。
分野$ j に関する日程は他の分野の日程には影響しないため、これらを全ての$ j についてかけ合わせれば良い。
さて、これで$ s_{i} が求められるが、これをそのまま実装すると各$ i について最悪で$ M 回の計算が必要になる。
つまり、全体では$ NM 回の計算が必要ということになり、今回の問題の制約を考えると、実行時間制限に間に合わないと思われる。
ここで、異なる分野$ j と$ j^{\prime} に対し、$ c_{j} = c_{j^{\prime}} であれば$ {}_{i} P_{c_{j}} = {}_{i} P_{c_{j^{\prime}}} である。
よって、$ c_{j} が等しいような$ j をまとめて一度に計算すれば、$ s_{i} が効率的に計算できると思われる。
実際に、$ \sum_{j=1}^{M} c_{j} = N を満たすような$ ( c_{0}, c_{1}, \ldots, c_{M} ) を考えたとき、この数列から重複を除いた個数は$ O(\sqrt{N}) となる。
これは、$ \sum_{i=1}^{n} i が$ n の$ 2 乗のオーダーになることを考えれば、逆に$ n は総和の$ \frac{1}{2} 乗のオーダーになることから想像がつく。
以上より、$ 1 以上$ N 以下の全ての$ i に対する$ s_{i} の値を合計で$ O(N\sqrt{N}\log M) の計算量で求められた。
ここで、計算量に$ \log M を付けたのは、$ c_{j} が同じである分野の個数だけ$ {}_{i} P_{c_{j}} をかける必要があるためである。
これで$ 1 以上$ N 以下の全ての$ i に対する$ s_{i} の値が求められたが、これらの値から本来求めたい値を求めることを考える。
$ 1 以上$ N 以下の整数$ i それぞれについて、$ t_{i} を下記で定める数とすると、これの総和が求めたい数である。
苦手分野を選ばない日（空いている日）がないように日程を組んだ場合に、精進期間が$ i 日間となる日程の個数
ここで、$ s_{i} と$ t_{i} の関係を考えていくと、$ 1 以上$ N 以下の任意の整数$ i について下の関係が成り立つことがわかる。
$ t_{i} = \sum_{j = 1}^{i} (-1)^{j+1} \times {}_{i} C_{i-j+1} \times s_{i-j+1}
この理由を、$ s_{i} を計算する際に数えた日程について、空いている日が何日あるかで場合分けをしながら考える。
まず、空いている日がない日程は左辺でも数えるべき日程ではあるが、右辺でも$ s_{i} の中でちょうど$ 1 度だけ数えられており問題ない。
次に、空いている日が$ k 日あった場合を考えると、$ {}_{i} C_{i-j+1} \times s_{i-j+1} の中で$ {}_{k} C_{j-1} 回だけ数えられていることがわかる。
なぜなら、$ {}_{i} C_{i-j+1} \times s_{i-j+1} の$ {}_{i} C_{i-j+1} = {}_{i} C_{j-1} は、$ (i-j+1) 日間の日程を$ i 日間の日程にする方法の数だからである。
空いている日である$ k 日のうち、この調整に使われたものの組み合わせを考えれば、$ {}_{k} C_{j-1} 回だけ数えられていることがわかる。
ただし、ここでは$ n \lt r のとき、$ {}_{n} C_{r} = 0であるとする。
よって、空いている日が$ k 日あった場合は右辺において$ \sum_{j=1}^{i} (-1)^{j+1} {}_{k} C_{j-1} 回数えられている。
これは$ 0 \lt k \lt i において$ 0 に等しいため、右辺において空いている日がある日程を全て除外することができたことがわかる。
よって、空いている日がない日程である$ t_{i} と等しいと思われる。
今回求めたい値は$ t_{i} の総和であるため、それを$ \sum_{i = 1}^{N} (-1)^{i+1} \times b_{i} \times s_{i} という形で表すことを考える。
上の事実を使うと、$ 1 以上$ N 以下の任意の整数$ i について$ b_{i} = \sum_{j = 0}^{N} (-1)^{j+1} {}_{j} C_{i} であることがわかる。
ただし、ここでは$ n \lt r のとき、$ {}_{n} C_{r} = 0であるとする。
まず、$ b_{1} について考えると、$ N が奇数のときは$ \frac{N+1}{2} 、$ N が偶数のときは$ - \frac{N}{2} となることが帰納法で確認できる。
また、一般の$ i について$ b_{i} を考えると、偶数番目の項と奇数番目の項にパスカルの三角形を適用できることがわかる。
$ N が奇数のとき、パスカルの三角形を適用すると$ b_{i} = \sum_{j = 0}^{(N+1)/2} {}_{2j} C_{i-1} と変形できる。
よって、$ i \gt 1 のとき、$ 2b_{i} + b_{i-1} = \sum_{j=0}^{N} {}_{j} C_{i-1} = {}_{N+1} C_{i} という漸化式が導出できるため、これに従って$ b_{i} を計算すれば良い。
$ N が偶数のときは、$ N を$ 1 増やすか減らすかして奇数にしたうえで$ b_{i} を求めて、最後の項を引いたり足したりすれば良い。
以上より、$ 1 以上$ N 以下の任意の整数$ i について$ s_{i} と$ b_{i} が計算できるため、求めたい値も計算できる。
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
int cmp_int_rev (const void *ap, const void *bp) {
int a = *(int *)ap;
int b = *(int *)bp;
if (a < b) {
return 1;
}
if (a > b) {
return -1;
}
return 0;
}
long long power_mod (long long a, long long b, long long mod_num) {
long long ans = 1LL;
if (b > 0LL) {
ans = power_mod(a, b/2LL, mod_num);
ans = (ans * ans) % mod_num;
if (b%2LL == 1LL) {
ans = (ans * (a % mod_num)) % mod_num;
}
}
return ans;
}
int main () {
int m = 0;
int n = 0;
int a = 0;
int res = 0;
long long ans = 0LL;
long long mod_num = 998244353LL;
int cnt = 0;
res = scanf("%d", &m);
res = scanf("%d", &n);
for (int i = 0; i < n; i++) {
res = scanf("%d", &a);
}
for (int i = 0; i < n+1; i++) {
facti+1 *= (long long) (i+1); }
invfn+1 = power_mod(factn+1, mod_num-2LL, mod_num); for (int i = n+1; i > 0; i--) {
}
qsort(c, m+1, sizeof(int)*2, cmp_int_rev);
cnt = 1;
for (int i = 1; i <= m; i++) {
cnt++;
}
}
for (int i = 1; i <= n; i++) {
}
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < ci0; j++) { }
for (int j = ci0; j <= n; j++) { sj *= power_mod(mul, (long long)ci1, mod_num); }
}
if (n%2 == 0) {
b1 = ((long long)(n/2))*(-1LL)+mod_num; } else {
b1 = ((long long)(n/2))+1LL; }
for (int i = 2; i <= n; i++) {
if (n%2 == 0) {
sub %= mod_num;
bi += mod_num-sub%mod_num;; }
}
for (int i = 1; i <= n; i++) {
if (i%2 == 1) {
} else {
ans += mod_num-(bi*si)%mod_num; }
}
printf("%lld\n", ans%mod_num);
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_380_E
提出のURL 提出時刻 結果 備考
感想
コンテスト中はD問題に苦戦したこともあって、E問題は暫く考えてわからなかったから早々に諦めて、G問題を眺めていた。
そんなわけで、このE問題をちゃんと考えたのは、コンテスト終了後にGが解き終わってから。
ちょうど最近に、ABC215Gを解いていたこともあり、$ O(\sqrt{N}) になるところはすぐに思いついたかな。 問題はその後で、畳み込みも疑ってはいたはずなんやけど、私には畳み込みの形は全くみえなかった。
結局、上で書いた通りごちゃごちゃやっていたら解けたので、かなり難しかったなーと思いながら解説をみたら
解説に書かれていた解き方と全く異なっていて驚いたかな