るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 548 Div2

250: KingdomAndDucks
やるだけ


int kind[100];
class KingdomAndDucks {
public:
  int minDucks(vector <int> duckTypes) {
    memset(kind,0,sizeof(kind));
    int k = 0;
    rep(i,duckTypes.size()){
      if(!kind[duckTypes[i]]) k++;
      kind[duckTypes[i]]++;
    }
    int mx = 0;
    rep(i,100) mx = max(mx,kind[i]);
    return k * mx;
  }
};

500: KingdomAndTrees


問題文を読んだ瞬間二分探索を思いついたところまでは良かった。
しかし解が適しているかを判定する関数でなぜかバグを量産。しかもオーバーフロー...

むしゃくしゃしたので、自分のコードに何度もChallengeしたら600点とかになって少し焦った (PracticeRoomって何度でもチャンレンジできる...?)


class KingdomAndTrees {
public:
  bool acc(vector<ll>h){
    for(int i = 1; i < h.size(); i++)
      if(h[i - 1] >= h[i]) return false;
    return true;
  }
  bool C(ll d,vector<ll>h){
    h[0] = max(1LL,h[0] - d);
    for(int i = 1; i < h.size(); i++){
      if(h[i - 1] < h[i])
	h[i] = max(h[i - 1] + 1,h[i] - d);
      else
	h[i] = min(h[i - 1] + 1,h[i] + d);
    }
    return acc(h);
  }

  int minLevel(vector <int> heights) {
    vector<ll>h;
    rep(i,heights.size()) h.pb((ll)heights[i]);
    if(acc(h)) return 0;
    ll lb,ub;
    lb = 0,ub = 1000000000LL;
    ll mid = 0;
    while(lb + 1 < ub){
      mid = (ub + lb) / 2LL;
      if(C(mid,h)) ub = mid;
      else lb = mid;
    }
    return ub;
  }
};

最近まったく頭が回らない。結構悩んでいる...