SRM320 div2 - Set::prototype

easy

//やるだけ．
//きわめて簡単なコード
{
int len = s.length();
s += '0'; //番兵．a-zとはちがう要素なので、最後に必ず条件分岐が真になる．
int div = 0; //sumはかならずszに等しい．ならば分割数だけを調べればいいじゃないか．
for(int i = 0; i < len; i++) {
  if(s[i] != s[i+1]) {
    div++;
  }
 }
return 1.0*len/div;
}

medium
いろいろと厄介な問題．
大小を比較するだけでいいので、

（1:[!]のかず（階乗の数ということにする）が等しいときに根の大小を比べる）
2:xの階乗の数、根の数がyよりもともに大きい（あるいは等しい）時、あきらかにx>yが成立する．
//問題は階乗の計算．
関数を作ってやると、例えば、456!とかを一気に計算してしまうとどんな整数の型でもoverflowを起こすので、一回一回計算するごとに常に2)の確認をする。
あと、0!は1なのでそこだけ注意．

  string compare(string x, string y) {
    vector<string> num(2); num[0] = x; num[1] = y;
    //LL edit[2]にした方がいいかも。
    int edit[2]; int fact[2]; //根と階乗の数

    //Parse
    for(int i = 0; i < 2; i++) {
      int pos = num[i].find('!');
      if(pos == string::npos) fact[i] = 0; //string::nposの処理系依存性の問題より場合分けが必要となる．( Topcoderでは[string::npos=-1] )
      else {fact[i] = num[i].length()-pos;}
      num[i] = num[i].substr(0, pos);
      sscanf(num[i].c_str(), "%d", &edit[i]);
    }
    bool flag = true; //x > y
    //calculate
    while(1) {
      if(fact[0] == fact[1]) {
	if(edit[0] == edit[1]) {
	  return "x=y";
	} else {
          //ここは必要．9999999!! > 10000000!!とかだと次の作業にいって、edit[1] = 10000000*9999999;でoverflowする可能性あり．
	  flag = (edit[0] > edit[1]);
	  break;
	}
      }
      //fact[0] == fact[1]が真になることはない。階乗の数の大きい方を計算する．
      int mimz = (fact[0] > fact[1]) ? 0 : 1;
      fact[mimz]--;
      bool ok = false;
      //0!の場合の考慮
      if(edit[mimz] == 0) {
	edit[mimz] = 1; continue;
      }
      //初期値:i=edit[mimz] ではない。
      for(int i = edit[mimz]-1; i >= 1; i--) {
	edit[mimz] *= i;
	if(edit[mimz] > edit[1-mimz]) {
	  ok = true; break;
	}
      }
      if(ok) {
	flag = (mimz) ? false : true; break;
      }
    }
    return (flag) ? "x>y" : "x<y";
  }

//parseの所を極力みじかくするならこういうコードでもよい。
int pos = remove(num[i].begin(), num[i].end(), '!') - num[i].begin();　//これなら、string::nposの処理系依存の問題を避けられる．
fact[i] = num[i].length()-pos;
sscanf(num[i].substr(0, pos).c_str(), "%d", &edit[i]);

あるいは、

fact[i] = count(num[i].begin(), num[i].end(), '!');
sscanf(num[i].substr(0, num[i].length()-fact[i]).c_str(), "%d", &edit[i]);

difficult
終点のまわりに昇順にソートする。あとはmap構造を使う。

01234567890123456789
----- 0.3
  ----- 0.4
     ----- 0.2
  ----------0.4
       -------0.3
とかのとき(既に終点のまわりに昇順ソートしてる)
prev = 0;
table[0] = 0.3;
table[5] = 0.3; prev = 5;

table[5] = 0.4;
table[7] = 0.4; prev = 7;

table[7] = 0.3+0.2; //table[0]+0.2;
table[10] = 0.5 prev = 10;

table[10] = max(0.4, 0.5);
table[12] = 0.5; prev = 12;

table[12] = max(0.3+0.4, 0.3+0.3); //max(table[0]+0.3, table[5]+0.4);
table[14] = 0.7;  -->ans = 0.7となる。

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 
--------------------------------------------------->
0.3            0.4   0.5      0.5   0.7   0.7    //みたいになる。

vector<Line>ではなくて、vector< vector<int> >を使うとソート用のclassを用意しなくていいが、arr[0], arr[1], arr[2]とやや抽象的になるので避けた．
typedef struct _line {
  int st;
  int ed;
  double prob;
} Line;

bool cmp(const _line& left, const _line& right) {
    return left.ed < right.ed;
}
typedef long long LL;

class ContestSchedule {
	public:
	double expectedWinnings(vector <string> contests) {
    int sz = contests.size();
    vector<Line> line(sz);
    //Parse
    for(int i = 0; i< sz; i++) {
      sscanf(contests[i].c_str(), "%d %d %lf", &line[i].st, &line[i].ed, &line[i].prob);
      line[i].prob = line[i].prob*1.0/100;
    }
    sort(line.begin(), line.end(), cmp );

    map<LL, double> table;
    double res = 0; //return
    map<LL, double>::iterator it;
    int prev = 0; //prev-end_point

    //Traverse、ある種のDP。
    for(int i = 0; i < sz; i++) {
      int pos = (line[i].st-prev >= 0) ? line[i].st : prev; //始点が終点より後にある-->始点をtableに格納
      double p = line[i].prob; //table[終点]にとりうる最大値を格納したい．
      for(int j = 0; j < i; j++) {
        if(line[i].st >= line[j].ed) { //いま着目している始点が別の線の終点よりも大きい時、連続してcontestに参加できる．
          it = table.equal_range(line[j].ed).first; it--;
          p = max(line[i].prob+table[ it->first ], p );
        }
      }
      res = max(p, res);
      table[pos] = res;
      table[ line[i].ed ] =res;
      prev = line[i].ed;
    }
    return res;
  }

//こっちの方が簡潔だが、本質的にやっていることは同じ．
typedef struct _line {
  int st;
  int ed;
  int prob;
} Line;
class cmp {
public:
  bool operator()(const _line& left, const _line& right) {
    if(left.ed != right.ed) {
    return left.ed < right.ed;
    } else {
      return left.st < right.st;
    }
  }
};
typedef long long LL;

class ContestSchedule {
	public:
	double expectedWinnings(vector <string> contests) {
    int sz = contests.size();
    vector<Line> line(sz);
    for(int i = 0; i< sz; i++) {
      sscanf(contests[i].c_str(), "%d %d %d", &line[i].st, &line[i].ed, &line[i].prob);
    }
    sort(line.begin(), line.end(), cmp() ); //終点のまわりに昇順ソート。
    int dp[51]; //ここで、dp[時間] = probではなくて、dp[インデックス] = probというDPの取り方をしている．
    memset(dp, 0, sizeof dp);
    for(int i = 0; i < sz; i++) {
      dp[i] = line[i].prob;
    }
    for(int i = 1; i < sz; i++) {
      for(int j = 0; j < i; j++) {
	if(line[i].st >= line[j].ed) {
	  dp[i] = max(dp[i], dp[j]+line[i].prob); //iの始点がjの終点より後になるときだけjのコンテストに引き続いてiのコンテストに参加することができる．
        }
      }
    }
    return (*max_element(dp, dp+51) )*1.0/100;
  }

};