ABC462 D - Accomplice
共犯
考え方
時刻と犯人 $2$ 人組のパターン数を求める問題。
「$2$ 人組を選んで、その $2$ 人での犯行数を求める」という方針では $O(N^2)$ かかるのでTLE。
ということで、時刻ごとに考えることになる。
時刻の最大値は $10^6$ なので、その長さの配列を用意するのは十分に可能。
ここに、各時刻に何人が犯行に加担可能かを記録していくことになる。
しかし、$1$ 人ずつforループで順番に $1$ を足していくと、$O(NT_{max})$ かかるのでこれもTLE。
よって、この加算を高速化する。
「vector の指定範囲に定数加算」を繰り返す場合、階差数列を作ってから累積和で復元する方法が有効。
$1$ 人ごとに vector を広く見る必要がなくなり、$O(N+T_{max})$ で完了する。
これが済んだら、時刻ごとに ${}_{加担可能人数}\mathrm{C}_2$ を求めて、その総和を答えればよい。
入力例1での動作
入力を受け取る。
時刻は受け取った値から $1$ を引いて 0-indexed にしておく。
n: 3
d: 2
(s, t): {(8, 16), (9, 11), (12, 19)}それぞれの人について、犯行開始から $D=2$ 単位時間ずっと館にいられる開始時刻を求める。
| 人 | 入館時刻 | 退館時刻 | 加担できる犯行開始時刻 |
|---|---|---|---|
| $1$ | $8$ | $16$ | $8$ 以上 $14$ 以下 |
| $2$ | $9$ | $11$ | $9$ のみ |
| $3$ | $12$ | $19$ | $12$ 以上 $17$ 以下 |
各範囲へ $1$ を加えるため、階差数列では範囲の先頭で $+1$、範囲の直後で $-1$ とする。
| 人 | $+1$ する時刻 | $-1$ する時刻 |
|---|---|---|
| $1$ | $8$ | $15$ |
| $2$ | $9$ | $10$ |
| $3$ | $12$ | $18$ |
変化がある付近だけを見ると、階差数列と、それを累積和で戻した加担可能人数は次のようになる。
| $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | $15$ | $16$ | $17$ | $18$ | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 階差 | $1$ | $1$ | $-1$ | $0$ | $1$ | $0$ | $0$ | $-1$ | $0$ | $0$ | $-1$ |
| 加担可能人数 | $1$ | $2$ | $1$ | $1$ | $2$ | $2$ | $2$ | $1$ | $1$ | $1$ | $0$ |
加担可能人数が $2$ の時刻では、犯人の選び方は ${}_2\mathrm{C}_2=1$ 通りである。
該当する時刻は $9,12,13,14$ の $4$ 個なので、合計は $4$ 通りとなる。
0-indexed 化する前の時刻に戻すと、犯行開始時刻は $10,13,14,15$ であり、公式例の $4$ 通りと一致する。
注意点
$N$ の値が大きいと、${}_N\mathrm{C}_2$ が大きくなり、int 型からはみ出る。
結果用変数には long long 型を用いること。
別解
シミュレーションをして答えることもできる。
その場合、以下で解ける。
- まず、館にいる時間が $D$ 未満である人は、最初からいなかったことにする。
- それ以外の人について、加担可能な時刻の開始と終了をそれぞれソートして用意する。
- 時刻を $1$ ずつ進め、人の増減をしてから $_{人数}\mathrm{C}_2$ を加算していく