【AtCoder】ABC 462 D - Accomplice

D - Accomplice

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 798 / NoviSteps: 1Q / 配点: 400 点

問題概要

とある館で起きた殺人事件の犯人の候補が $N$ 人いる。 人 $i$ は時刻 $S_i$ に館に入り、時刻 $T_i$ に館を出て、ほかの時刻には出入りしなかった。

犯行について以下のことが分かっている。

• 犯人はちょうど $2$ 人いる。
• 犯行はある整数時刻 $x$ に開始し、$D$ 単位時間かけて行われ、時刻 $x + D$ に完了した。
• 犯人は $2$ 人とも犯行開始から犯行完了まで常に館にいた(犯行開始と同時に館に入ったり、犯行完了と同時に館を出たりした可能性もある)。

$N$ 人の犯人候補の中に犯人が $2$ 人ともいると仮定したとき、$2$ 人の犯人の組み合わせと犯行開始時刻の組としてありうるものは何通りあるか求めよ。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq S_i \leq T_i \leq 10^6$
• $1 \leq D \leq 10^6$
• 入力される値は全て整数

考察

まず、各時刻 $t$ に何人が犯行可能かを考える。

人 $i$ が時刻 $t$ に犯行可能である条件は、

である。

したがって、人 $i$ が犯行可能な時刻の候補となる区間は $[S_i, T_i - D]$ である。

また、ある時刻 $t$ に犯行可能な人の数を $c_t$ とすると、$c_t$ 人の中から犯人を $2$ 人選ぶ方法は $\frac{c_t(c_t - 1)}{2}$ 通りあるので、求める答えは

となる。

今回は時刻の上限が $10^6$ なので、長さ $10^6$ の配列を用意して、imos法の要領で $c_t$ を求めることができる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.using ll = long long;
7. 
8.// ======================================== //
9. 
10.int main()
11.{
12.    int N, D;
13.    cin >> N >> D;
14. 
15.    vector<int> time(1001000, 0);
16.    rep(i, 0, N) {
17.        int S, T;
18.        cin >> S >> T;
19. 
20.        if (S <= T - D) {
21.            time[S]++;
22.            time[T - D + 1]--;
23.        }
24.    }
25. 
26.    ll ans = 0, cnt = 0;
27.    rep(t, 1, 1001000) {
28.        cnt += time[t];
29.        ans += cnt * (cnt - 1) / 2;
30.    }
31. 
32.    cout << ans << endl;
33. 
34.    return 0;
35.}

https://atcoder.jp/contests/abc462/submissions/76639243

atcoder.jp

実装時間: 15 分

コメント

AtCoderの世界でも殺人事件って起こるのか...