読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

SRM 645 Div1 easy : JanuszTheBusinessman

SRM 貪欲 Div1

問題概要 :
貴方はホテルを経営している
今年も既にn人から予約が入っている
n人の到着する日と出発する日が与えられる
貴方はn人の中から何人か選んでその人らにプレゼントをあげる
プレゼントをもらった人はハッピーになる
プレゼントをもらった人と同じ日にホテルにいる人は同様にハッピーになる
プレゼントをもらった人が出発する日に到着した人もハッピーになる
全ての人をハッピーにするために必要なプレゼントの数の最小値はいくらか

制約 :
1 <= n <= 50
1 <= 出発日、到着日 <= 365

解法 :
貪欲法
全ての人をハッピーにしなければならない
一番最初に出発する人はハッピーにならなければならないのだが、
この人をハッピーにするために、この人と同じ日にホテルにいるひとのうち最も遅く出発する人を選びその人にプレゼントをあげる
こうしてプレゼントをもらった人と同じ日にホテルにいる人を全て消し、残った人達で同様にして計算していくと良い

以下のコードは本番中のものだが、ちょっと勘違いしているため無駄な計算をしている
最初は二分探索でプレゼントをあげる人の数の最小値を決め打ちしようと考えていたがサイズが小さいので全探索にした
が、結局1回やれば必要な数は分かるため最小値を決めるループにはオーダーを増やすこと以外意味がない

コード :

struct Se {
  int s,t;
  bool operator < (const Se &seg) const {
    if( t != seg.t ) return t < seg.t;
    return s < seg.s; ///////
  }
};

typedef long long ll;
const int IINF = INT_MAX;

bool fin[100];

class JanuszTheBusinessman {
public:
  int N;
  vector<Se> vec;

  bool cross(int i,int j){ // jがiとatteruka
    if( vec[i].s > vec[j].t || vec[i].t < vec[j].s ) return false;
    return true;
  }

  bool check(int cnt){
    rep(i,N) fin[i] = false;
    rep(i,vec.size()) if( !fin[i] ){
      int maxi = i;
      REP(j,i+1,vec.size()) if( cross(i,j) ) {
        if( vec[maxi].t < vec[j].t ) maxi = j;
      }
      if( cnt <= 0 ) return false;
      --cnt;
      fin[maxi] = true;
      rep(j,vec.size()) if( !fin[j] ) {
        if( cross(maxi,j) ) fin[j] = true;
      }
    }
    return true;
  }

  int makeGuestsReturn( vector <int> a, vector <int> d ) {
    N = a.size();
    rep(i,N) vec.push_back((Se){a[i],d[i]});
    sort(vec.begin(),vec.end());
    rep(mini,N) if( check(mini) ) return mini;
    return N;
  }
};

コメント :
チャレンジフェーズ中は上位勢から結構チャレンジされてた
その結果、動揺してしまい一人自分と異なる答えを返す人を見つけたが、答えが異なるケースを図にしたものを見て相手のコードのほうが正しいと勘違いしてしまいそのまま何もせずに終わってしまった