D - Recording (abc080_d) ～番組の録画～

atcoder

Quiz

https://atcoder.jp/contests/abc080/tasks/abc080_d

Submit

https://atcoder.jp/contests/abc080/submissions/3888310

問題文

  • 「-0.5秒～」の箇所、ここで「チャンネル変更には0.5秒のコストがかかる（チャンネル変更しないならかからない）」と言っている
  • →同じチャンネルで（X, Y］、（Y, Z］があればくっつけてしまってよい★

要素

  • いもす法
  • タイムスケールを2倍

editorialとは違う解法でも解いてみた（2020/10/18）

  • ★の条件でくっつけた後は、同じチャンネルごとでも1は離れているので、全ての番組を別チャンネルとして同一視してよい
  • チャンネル数は30あれば全て録画できることが確定しているので、チャンネル数を1～30で全探索する（チャンネル数がもっと多いなら二分探索も可能）
  • 「時刻tからなら空いてますよ」の管理のためにmultisetを使い、ACした
  • この解法ならチャンネル数105, 時刻範囲109でも解けますね^^
// 隣同士で終点＝始点ならくっつける
vector<PII> connect(vector<PII> V){
  sort(ALL(V));
  deque<PII> que;
  for(auto pa : V){
    if(que.size()==0){
      que.push_back(pa);
    }else{
      if(que.back().second == pa.first){
        // くっつける
        auto front = que.back(); que.pop_back();
        pa.first = front.first;
      }
      else{
        // そのまま追加
      }
      que.push_back(pa);
    }
  }
  vector<PII> ret;
  for(auto pa : que){
    ret.push_back(pa);
  }
  return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,C;cin>>N>>C;

    // チャンネルごとに管理
    vector<vector<PII>> V(C);

    rep(i,N){
      ll s,t,c;cin>>s>>t>>c;
      c--;
      V[c].push_back({s,t});
    }
    rep(c,C){
      V[c] = connect(V[c]);
    }

    // 以降、全ての区間をチャンネル関係なしに同一視できる
    vector<PII> A;
    rep(c,C){
      for(auto pa : V[c]){
        pa.first--; // 0.5秒を考慮
        A.push_back(pa);
      }
    }
    sort(ALL(A));

    FOR(c,1,C+1){
      // c : 録画機の数
      multiset<ll> se;
      rep(i,c)se.insert(0);

      bool ok=true;
      for(auto pa : A){
        auto it = se.begin();
        if(*it>pa.first){
          // 空きがない
          ok=false;break;
        }else{
          se.erase(it);
          se.insert(pa.second);
        }
      }

      if(ok){
        p(c);return 0;
      }
    }
    
    return 0;
}