るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 545 Div2

250: ANDEquation

やるだけ

class ANDEquation {
public:
  int restoreY(vector <int> A) {
    int result;
    rep(i,A.size()){
      int y = A[i];
      vector<int>t;
      rep(j,A.size()){
	if(j == i) continue;
	t.pb(A[j]);
      }
      rep(i,t.size() - 1)
	t[i + 1] = t[i] & t[i + 1];
      if(t[t.size() - 1] == y) return y;
    }
    return -1;
  }  
};


550: StrIIRec

思いつくと簡単だけど、なかなか思いつかない...

条件を満たすできるだけ小さい文字を追加していけば良い. 条件判定は、(現在の文字) + (残りの文字の降順) が最大なので、これを比較すれば貪欲に求まる。

class StrIIRec {
public:
  int Inv(string s){
    int res = 0;
    rep(i,s.size())
      for(int j = i + 1; j < s.size(); j++)
	if(s[i] > s[j]) res++;
    return res;
  }
  string recovstr(int n, int minInv, string minStr) {
    string li = "";
    string res = "";
    rep(i,n){
      string tmp(1,'a' + i);
      li += tmp;
    }
    rep(l,n){
      vector<pair<string,int> > limit;
      rep(i,li.size()){
	string rest;
	rep(j,li.size()){
	  if(i == j) continue;
	  rest += li[j];
	}
	reverse(all(rest));
	string t = res + li[i] + rest;
	limit.pb(mp(t,Inv(t)));
      }
      rep(i,limit.size()){
	if(limit[i].first >= minStr && minInv <= limit[i].second){
	  res += li[i]; li.erase(li.begin() + i);
	  break;
	}
      }
    }
    if(res.size() != n) return "";
    if(li.size() > 0) return "";
    return res;
	
  }
};