[AtCoder] ABC 014 C – AtColor

2019年5月15日

問題

方針

いもす法

区間の最大被覆数を求める問題なので、いもす法が思い浮かぶと思います。実際に、いもす法の解説においてもこの問題が取り上げられています。

優先度付きキューを用いる方法

いもす法では値が大きくなると計算量がその分増えるという問題があります。僕にはこの問題の解決法が分からなかったので、優先度付きキューを用いて方針を立てました。

区間 \([a_i,  b_i]\) が与えられたとき、任意の整数 \( x \) が含まれる区間の数の最大値を求めます。このとき、 \( x \) の候補は、\( a_i \) を調べれば十分であることが分かります。

区間の整列

区間 \( [a_i, b_i]\) を \(a_i \) について昇順に整列させ、\(a_i = a_j \) のときは、\(b_i\) と \( b_j\) を比較して昇順に整列させます。

優先度付きキュー

昇順になるような優先度付きキュー \(q\) を用いて、問題の最大値を求めます。キューのサイズの最大値が求める答えになります。

まず初めに、\( k = a_1 \)、\(q_1 = b_1\) とします。ここで、\(q_1 \) は \(q \)における最小値とします。

次に、\(i = 2\) から \(i = n\) まで整列させた区間を順に調べていきます。

  1. \(q \) に \(b_i \) を挿入する。
  2. \(k > q_1\) ならば、\( k <= q_1 \) となるまで、キューから値を取り出す。また、キューが空になればこの手順を終える。
  3. このときのキューのサイズで最大値を更新する。
  4. \(k = a_i \) として、1. に戻る。

以上の手順を繰り返すことで、最大値を得られます。

具体的に何をしているかというと、\( k \) が入る区間の個数を数えています。

\( k \) は一つ前の区間の \( a_{i  – 1} \) の値であるので、\(k > q_1\) となるとき、\(q_1 \) の値をもつ区間は \( k \) を含まないので、取り除かれます。

図を書いて見ると分かりやすいかもしれません。

コード

提出したコード

優先度付きキューを使う部分

priority_queue<int, vector<int>, greater<int>>qr;
  int g = 1;
  qr.push(v[0].second);
  int k;
  for(int i = 1; i < n; i++){
    k = v[i].first;
    qr.push(v[i].second);
    if(k > qr.top()){
     while(!qr.empty()){
        if(k <= qr.top()){
          break;
        }else{
          qr.pop();
        }
      }
    }
    g = max(g, (int)qr.size());
  }

\( v \) は区間を表し、\( v[0].first \) は \( a_i \) を、\( v[0].second\) は \( b_i \) に対応しています。