[AtCoder] ABC 127 C – Prison

2019年5月25日

問題

方針

\( 1 \) 枚のカードで全てのゲートを通過できるとは？

\( 1 \) 枚のカードで全てのゲートを通過できるとはどいうことかを考えます。ID が \( a \) のカードが全てのゲートを通過できるとき、全てのゲート \( i \) について、\( L_i \leq a \leq R_i \) を満たしている必要があります。このような \( a \) を \( 1 \leq a \leq N \) の範囲で調べる必要があります。

いもす法

\( a \) を変化させて、全てのゲートに対して調べるには計算量が多くなってしまうので、効率的な方法を考えます。この問題は、ある点において、区間の数が何個入るかを求めればよいので、いもす法を使います。\( M \) 個の区間が重なる個数が答えになります。いもす法を使うと次のような配列が得られます。

入力例 1

区間の数	\( 1 \)	\( 2 \)	\( 2 \)	\( 2 \)
ID	\( 1 \)	\( 2 \)	\( 3 \)	\( 4 \)

入力例 2

区間の数	\( 0 \)	\( 0 \)	\( 1 \)	\( 1 \)	\( 2 \)	\( 3 \)	\( 2 \)	\( 1 \)	\( 1 \)	\( 0 \)
ID	\( 1 \)	\( 2 \)	\( 3 \)	\( 4 \)	\( 5 \)	\( 6 \)	\( 7 \)	\( 8 \)	\( 9 \)	\( 10 \)

また、いもす法については、次のサイトを参照してください。

いもす研 – いもす法

satanic – Imos法(いもす法)

コード

提出したコード

いもす法

int L[M], R[M];
  for (int i = 0; i < M; i++) {
    cin >> L[i] >> R[i];
    L[i]--;
    R[i]--;
  }
  int b[N + 2]{};
  // 累積和を求める
  for (int i = 0; i < M; i++) {
    b[L[i]]++;
    b[R[i] + 1]--;
  }
  for (int i = 0; i <= N; i++) {
    b[i + 1] += b[i];
  }
  int cnt = 0;
  for (int i : b) {
    if (i == M) cnt++;
  }