AtCoder Beginners Contest 137 D - Summer Vacation 別解(マトロイド)

はじめに

自分の提出したコードが、解説pdfで別解として紹介されているマトロイド解だったことに気づいたため、紹介します。

問題リンク

atcoder.jp

考え方

Bが大きい順に、Bが同じの場合はAが大きい順にソートする。
要素を一つずつ見ていき、仕事が実行可能である場合には、現状のスケジュールとの兼ね合いを取りつつ最も遅いタイミングに挿入する。
例えば、

3 3
1 5
3 4
2 4

の場合は、まず(1,5)を見て2日目にこの仕事を確定させる。次に、(3,4)を見て0日目に確定させる。最後に(2,4)を見て1日目に確定させる。
すべての仕事で報酬がもらえるので、答えは13となる。

提出したコード

https://atcoder.jp/contests/abc137/submissions/6827880

int main(){
  int N,M;
  cin>>N>>M;
  vector<pair<int,int>> BA(N);
  set<int> times;
  REP(i,N){
    int a,b;
    cin>>a>>b;
    BA[i]=make_pair(-b,-a);
  }
  REP(i,M)times.insert(i);
  sort(ALL(BA));
  ll ans=0ll;
  for(auto e:BA){
    int value=-e.first;
    int time=-e.second;
    auto it=times.lower_bound(time-1);
    if(it!=times.end()){
      ans+=value;
      times.erase(it);
    }
  }
  cout<<ans<<endl;
}

timesというsetに、仕事して報酬を受け取ることが可能な(まだ仕事が埋まっていない)日付をすべて入れる。初期値は{0,1,2,3,...,M-1}

実際には、実装を簡単にするために、setの中身は、報酬を受け取るまでにかけることのできる時間としている。
適切にソートして、Aの値以上で最も小さいものを削除していく。この操作は二分探索でO(logM)で可能である 。 Aの値を超える日付が存在しなければ、その仕事は不可能、または、やると損であるため、捨てる。