るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 553 Div2

250: PlatypusDuckAndBeaver

少し危ない計算量だけど間に合った。

class PlatypusDuckAndBeaver {
public:
  int minimumAnimals(int webbedFeet, int duckBills, int beaverTails) {
    int result = 0;
    for(int x = 0; x <= 500; x++){
      for(int y = 0; y <= 250; y++){
	for(int z = 0; z <= 250; z++){
	  if(2 * x + 4 * y + 4 * z == webbedFeet && x + y == duckBills && y + z == beaverTails){
	    result = x + y + z;
	  }
	}
      }
    }
    return result;
  }

};

500: Suminator

適当に数字を入れて計算してwantedResultとの差分を返す。ただし0は別処理。
あと-1の部分をまったく使わない場合と、使っても該当する数字が無い場合は-1を返す。
オーバフローに気づかず時間食った。

class Suminator {
public:
  ll calc(vector<ll>p){
    vector<ll>st;
    rep(i,100) st.pb(0);
    rep(i,p.size()){
      if(p[i] == 0){
	ll a = st[st.size() - 1]; st.pop_back();
	ll b = st[st.size() - 1]; st.pop_back();
	st.pb(a + b);

      }else{
	st.pb(p[i]);
      }
    }
    return st[st.size() - 1];
    
  }
  int findMissing(vector <int> pg, int wR) {
    int index = 0;
    vector<ll>tmp;
    rep(i,pg.size()){
      if(pg[i] == -1) index = i;
      tmp.pb((ll)pg[i]);
    }
    tmp[index] = 0;
    ll p1 = calc(tmp);
    if(p1 == wR) return 0;
    tmp[index] = 1;
    ll p2 = calc(tmp);
    tmp[index] = 2;
    ll p3 = calc(tmp);
    if(p2 == p3) return -1;
    ll ans = wR - p2 + 1;
    if(ans <= 0) return -1;
    return (int)ans;
  }
};