SRM579Div2

Easy:PrimalUnlicensedCreatures
クリーチャーが何体か居て、それぞれのレベルがvectorで与えられる。
自分の初期レベルが与えられる。
自分より低いレベルのクリーチャーを倒すことができ、倒したクリーチャーのレベル/2(切り捨て)だけ自分のレベルがUPする。
最大何体のクリーチャーを倒すことができるか。

解法:
弱い奴から順番に倒す。

class PrimalUnlicensedCreatures {
public:
  int maxWins(int lv, vector <int> v) {
    int res = 0;
    sort(v.begin(),v.end());
    rep(i,v.size()){
      if( lv > v[i] ){
         lv += v[i]/2;
         res++;
      }
    }
    return res;
  }
};

Medium:UndoHistory
変なテキストエディタを使って与えられた文字列を入力する時の、最小プレス数を求める。
・入力した文字はバッファに格納される。(1文字あたり1プレス)
・Enterキーを押すとバッファに入っている文字列がアウトプットされる。この時別にバッファはクリアされない。(1回1プレス)
・バッファの履歴が残っており、UNDOで以前の状態のバッファに復元出来る。(1UNDOにつき2プレス)

解法:
UNDOは新しい行の行頭でしか使っても意味がないから、改行する度に、バッファの続きから打つ場合・UNDOを使う場合 の2通りに点数をつける。
点数 = 節約出来る文字数 - プレス数
点数が高い方でGreedyに処理していく。
バッファの履歴は全パターン取っておかなくても、そこまでに入力した行を覚えておけば良いらしい。

class UndoHistory {
public:
  int minPresses(vector <string> lines) {
    int res=0;

    set<string> undo;
    string buffer;

    rep(i,lines.size()){
      string line = lines[i];
      int score_buffer = -1*(1<<29);
      int score_undo = -2;
      int start_pos = 0;

      if(buffer == "" || line.find(buffer) == 0){
        score_buffer = buffer.size();
      }

      rep(j,line.size()){
        string s = line.substr(0,j+1);
        if(undo.find(s) != undo.end()){
          if(score_undo < -2+j+1){
            score_undo = -2+j+1;
            start_pos = j+1;
          }
        }
      }

      string restline;
      if(score_buffer > score_undo){
        restline = line.substr(buffer.size());
      }else{
        res += 2;
        restline = line.substr(start_pos);
        buffer = line.substr(0, start_pos);
      }

      res += restline.size();

      rep(j, restline.size()){
        undo.insert(buffer + restline.substr(0,j+1));
      }
      
      res++;
      buffer = line;
    }

    return res;
  }
};

Hard:MarblePositioning
マーブルが何個か与えられ、それらを横一列に並べた時の距離の最小値を求める問題。

解法:
最大8個なので全通り試しても40320パターンくらいしかないので全通り試す。

class MarblePositioning {
public:
  double dist(double r1, double r2){
    double a = r1+r2;
    double b = r1-r2;
    return sqrt(a*a - b*b);
  }

  double totalWidth(vector <int> R){
    double res=1e20;
    sort(R.begin(),R.end());
    do{
      vector<double> P(R.size());
      rep(i,R.size()){
        rep(j,i){
          P[i] = max(P[i], P[j] + dist(R[j], R[i]));
        }
      }
      res = min(res, P.back());
    }while(next_permutation(R.begin(),R.end()));
    return res;
  }
};