yukicoder contest 391 C
解き方
※ ここに書く解き方は、解説に書かれている方法とは少し異なる。 この問題において、数列$ a は次のように作成されると考えることができる。
$ 1 \leq i \leq N を満たす整数$ i それぞれについて、$ B_{i} 以上$ C_{i} 以下の整数を一様ランダムに1つ選び$ b_{i} とする。
ある順列$ p が与えられるため、$ 1 \leq i \leq N を満たす整数$ i それぞれについて、$ a_{i} = b_{p_{i}} とする。
上記の考えに基づき考えていくが、まずはこの記事内で使用する記法や各種値を表す文字などを以下の通り定義する。
順列$ p に対して、$ p^{-1} を以下の条件をみたす順列とする。
$ 1 \leq i \leq N を満たす任意の整数$ i について、$ p^{-1}_{p_{i}} = i を満たす。
$ 1 以上$ N 以下の正整数$ i について、$ b_{i} の取りうる値の個数を$ l_{i} とする。すなわち$ l_{i} = C_{i}-B_{i}+1 とする。
$ 1 \leq i \lt j \leq N を満たす整数$ i と$ j について、$ b_{i} の取りうる値と$ b_{j} の取りうる値の両方に含まれる数の個数を$ s_{i,j} とする。
例えば、もし$ C_{i} \lt B_{j} ならば$ s_{i,j} = 0 であり、$ B_{i} \leq B_{j} \leq C_{i} \leq C_{j} であれば$ s_{i,j} = C_{i}-B_{j}+1 である。
$ 1 \leq i \lt j \leq N を満たす整数$ i と$ j について、確率変数$ X_{i,j} を以下の通り定める。
全ての順列$ p に対して数列$ a を作ったときに、$ b_{i} と$ b_{j} が$ a の中で転倒する回数
より明確な定義を書くとするならば、以下を2条件のいずれかを満たすような順列$ p の個数を$ X_{i,j} とする。
$ p^{-1}_{i} \lt p^{-1}_{j} かつ$ b_{i} \gt b_{j}
$ p^{-1}_{i} \gt p^{-1}_{j} かつ$ b_{i} \lt b_{j}
$ X_{i,j} の期待値を$ E_{i,j} とすると、期待値の線型性より、この問題の答えは$ \sum_{j = 2}^{N} \sum_{i = 1}^{j-1} E_{i,j} と表せる。
よって、次に$ E_{i,j} の値がどうなるか考えるが、実は$ E_{i,j} = \left( 1-\frac{s_{i,j}}{l_{i}l_{j}} \right) \times \frac{N!}{2} となる。これは、次のように確認できる。
$ p^{-1}_{i} \lt p^{-1}_{j} を満たす順列$ p の個数と$ p^{-1}_{i} \gt p^{-1}_{j} を満たす順列$ p の個数は、いずれも$ \frac{N!}{2} である。
よって、$ b_{i} \neq b_{j} （つまり$ b_{i} \lt b_{j} または$ b_{i} \gt b_{j} ）のとき、$ X_{i,j} の値は$ \frac{N!}{2} となる。
一方で、$ b_{i} = b_{j} であるときは、$ b_{i} \lt b_{j} も$ b_{i} \gt b_{j} も成り立たないため、$ X_{i,j} の値は$ 0 となる。
以上より、$ p_{i,j} を$ b_{i} \neq b_{j} となる確率とすると、期待値の定義により$ E_{i,j} = p_{i,j} \times \frac{N!}{2} となる。
ここで、$ b_{i} = b_{j} となるとき、$ b_{i} および$ b_{j} の値として有り得るのは$ s_{i,j} 個である。
よって、$ b_{i} = b_{j} となる確率は$ \frac{s_{i,j}}{l_{i}l_{j}} であるため、$ p_{i,j} = 1- \frac{s_{i,j}}{l_{i}l_{j}} となり、$ E_{i,j} = \left( 1-\frac{s_{i,j}}{l_{i}l_{j}} \right) \times \frac{N!}{2} であることがわかる。
また、$ b_{i} \lt b_{j} となる確率と、$ b_{j} \lt b_{i} となる確率をそれぞれ求め、それらを足して$ \frac{N!}{2} を掛けるという方法でも上の式を導ける。
ただし、その場合は$ B_{i} 、$ C_{i} 、$ B_{j} 、$ C_{j} の大小関係によって場合分けが必要となり煩雑なため、詳細は割愛する。
この問題を解くにあたり、$ 1 \leq i \lt N を満たす任意の整数$ i について$ B_{i} \leq B_{i+1} が成り立っていると仮定しても一般性を失わない。
（もし、成り立っていなければ、$ B_{i} の値について昇順に並び替えれば良い）
上の結果を用いて$ \sum_{j = 2}^{N} \sum_{ i = 1 }^{j-1} E_{i,j} を求めれば良いが、今回の制約では愚直に計算すると間に合わない可能性がある。
そのため、$ 2 \leq j \leq N を満たす$ j について、小さい方から順に計算していくことで$ \sum_{ i = 1 }^{j-1} E_{i,j} を効率的に計算することを考える。
ここで、$ \sum_{ i = 1 }^{j-1} E_{i,j} = \frac{N!}{2} \times \left( j-1-\sum_{ i=1 }^{j-1} \frac{s_{i,j}}{l_{i}l_{j}} \right) であるため、$ \sum_{ i=1 }^{j-1} \frac{s_{i,j}}{l_{i}l_{j}} を効率的に計算できれば良い。
仮定として$ B は昇順に並んでいるとしているため、$ s_{i,j} の値は$ C_{i} によって決まる。そこで$ C_{i} の大きさで$ i を以下の3つに分類する。
$ 1 \lt j \leq N を満たす整数それぞれについて、
$ C_{i} \lt B_{j} の場合
$ B_{j} \leq C_{i} \leq C_{j} の場合
$ C_{i} \gt C_{j} の場合
１つ目の場合については$ s_{i,j} = 0 となることから考慮は不要であるため、2つ目の場合と3つ目の場合について考える。
2つ目の場合となるような$ i の集合を$ \Lambda_{1} とする。すなわち$ \Lambda_{1} = \{ i \in \mathbb{N} \mid 1 \leq i \lt j \text{ and } B_{j} \leq C_{i} \leq C_{j} \} とする。
このとき、$ \sum_{i \in \Lambda_{1} } \frac{s_{i,j}}{l_{i}l_{j}} = \sum_{i \in \Lambda_{1} } \frac{C_{i}-B_{j}+1}{l_{i}l_{j}} = \frac{1}{l_{j}} \times \left( \left( \sum_{i \in \Lambda_{1} } \frac{C_{i}}{l_{i}} \right)-(B_{j}-1) \sum_{i \in \Lambda_{1}} \frac{1}{l_{i}} \right) となる。
3つ目の場合となるような$ i の集合を$ \Lambda_{2} とする。すなわち$ \Lambda_{2} = \{ i \in \mathbb{N} \mid 1 \leq i \lt j \text{ and } C_{i} \gt C_{j} \} とする。
このとき、$ \sum_{i \in \Lambda_{2} } \frac{s_{i,j}}{l_{i}l_{j}} = \sum_{i \in \Lambda_{2} } \frac{C_{j}-B_{j}+1}{l_{i}l_{j}} = \frac{C_{j}-B_{j}+1}{l_{j}} \sum_{i \in \Lambda_{2}} \frac{1}{l_{i}} となる。
よって、$ \sum_{i = 1}^{j-1} E_{i,j} を計算するには、$ \sum_{i \in \Lambda_{1} } \frac{C_{i}}{l_{i}} や$ \sum_{i \in \Lambda_{1}} \frac{1}{l_{i}} や$ \sum_{i \in \Lambda_{2}} \frac{1}{l_{i}} を効率よく求められれば良い。
ここで、$ i が$ \Lambda_{1} や$ \Lambda_{2} に含まれるかは$ C_{i} が特定の区間に含まれるか否かによって決まる。
そのため、$ C_{i} の値を基準に考えれば、上記の値は特定の区間に対する和だと考えられるため、セグメント木で効率化できる。
ただし、$ C_{i} の値は大きくなり得るため、その値をそのまま添え字として使うのではなく、少し工夫が必要である。
$ C_{i} の値の種類数大小関係を維持したまま$ N 未満の非負整数にマッピングすれば良い例えば
以上により、本問題の答えが$ O(N(\log N + \log \mathrm{MOD})) という計算量で計算できることがわかる。
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
int cmp_ll (const void *ap, const void *bp) {
long long a = *(long long *)ap;
long long b = *(long long *)bp;
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
void add_segt (long long *t, int idx, long long val, int size) {
idx = idx+size-1;
while (idx > 0) {
idx = (idx-1)/2;
}
return;
}
long long sum_segt_rec (long long *t, int a, int b, int k, int l, int r) {
long long ans = 0LL;
if (r <= a || b <= l) {
return 0LL;
}
if (a <= l && r <= b) {
}
ans += sum_segt_rec(t, a, b, 2*k+1, l, (l+r)/2);
ans += sum_segt_rec(t, a, b, 2*k+2, (l+r)/2, r);
return ans;
}
long long sum_segt (long long *t, int a, int b, int size) {
return sum_segt_rec(t, a, b, 0, 0, size);
}
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 n = 0;
int res = 0;
long long ans = 0LL;
long long mod_num = 998244353LL;
int size = 1;
int ucnt = 1;
res = scanf("%d", &n);
for (int i = 0; i < n; i++) {
res = scanf("%lld", b+i);
res = scanf("%lld", c+i);
bcn+i1 = (long long)(n+i); }
qsort(bc, 2*n, sizeof(long long)*2, cmp_ll);
if (bc01 < (long long)n) { } else {
}
for (int i = 1; i < 2*n; i++) {
ucnt++;
}
if (bci1 < (long long)n) { b[(int)bci1] = (long long)(ucnt-1); } else {
c[((int)bci1)-n] = (long long)(ucnt-1); }
}
while (size <= ucnt) {
size <<= 1;
}
for (int i = 0; i < n; i++) {
}
qsort(p, n, sizeof(long long)*2, cmp_ll);
for (int i = 0; i < n; i++) {
long long tmp = sum_segt(t0, (int)pi0, (int)pi1, size)%mod_num; long long cnt = sum_segt(t1, (int)pi0, (int)pi1, size)%mod_num; long long div = power_mod(map[(int)pi1]-map[(int)pi0]+1LL, mod_num-2LL, mod_num); tmp += (sum_segt(t1, (int)pi1, ucnt, size)%mod_num)*(map[(int)pi1]-map[(int)pi0]+1LL); tmp %= mod_num;
tmp += mod_num-(cnt*(map[(int)pi0]-1LL))%mod_num; tmp %= mod_num;
tmp *= div;
ans += mod_num-tmp%mod_num;
ans += (long long)i;
add_segt(t0, (int)pi1, (map[(int)pi1]*div)%mod_num, size); add_segt(t1, (int)pi1, div, size); }
ans %= mod_num;
for (int i = 2; i < n; i++) {
ans *= (long long)(i+1);
ans %= mod_num;
}
printf("%lld\n", ans%mod_num);
return 0;
}
私の提出一覧
table: submissions_yukicoder_contest_391_C
提出のURL 提出時刻 結果 備考
感想
期待値の問題であるため、適当な要素に分解して、期待値の線形性を使って足し合わせるだけかと思ったが、意外に手間取ってしまった。
まずは、上の解き方で$ E_{i,j} とした値がどのようになるか考えたが、ここにけっこう時間がかかった。
対称性から$ \frac{N!}{2} 倍になることは割とすぐにきがついたが、$ b_{i} = b_{j} が余事象となることに気づけなかった。
そのため、上の解き方では割愛したが、$ b_{i} \lt b_{j} となる確率と、$ b_{j} \lt b_{i} となる確率をそれぞれ求める方針で考えた。
試しに$ B_{i} \leq B_{j} \leq C_{i} \leq C_{j} の場合や$ B_{i} \leq B_{j} \leq C_{j} \leq C_{i} の場合に関して計算してみて、共通部分を引けば良いと推測した。
$ b_{i} = b_{j} が余事象となることは、解いた後に過程を整理していたときに漸く気づいた。
さらに、確率にするために場合の数で割ることを忘れていたから、$ E_{i,j} = \frac{N!}{2} \times (l_{i}l_{j}-s_{i,j}) だと勘違いしていた。
だから、$ \sum_{i} C_{i} や$ \sum_{i} 1 をセグメント木で計算する方針で最初実装していた。
実装後にサンプルの答えが合わないから考え直してみて、漸く間違いに気づいて、なんとか軌道修正できないかと考えた。
よく考えたらセグメント木に足す値を先に$ l_{i} で割っておけばよいのではと思いつき、上の解き方になった。
セグメント木に足す値を変えたときに、オーバーフローの考慮を忘れていて、1回WAとなってしまった。