SRM335Div2

250

bool p(string s)
{
  string t = s;
  reverse( t.begin(), t.end() );
  return s == t;
}

class Palindromize {
public:
  string minAdds(string s) {
    for(int i=0; i<s.size(); ++i){
      string t = s.substr(i);
      if( p(t) ){
        t = s.substr(0, i);
        reverse( t.begin(), t.end() );
        return s + t;
      }
    }
    return "@";
  }
};

500
BigIntは自作のクラス。

string itoa(int n)
{
  ostringstream oss;
  oss << n;
  return oss.str();
}

class Multifactorial {
public:
  string calcMultiFact(int N, int K) {
    BigInt mx("1000000000000000000");
    BigInt zero("0");
    BigInt n( itoa(N) );
    BigInt k( itoa(K) );
    BigInt r("1");
    while( zero < n ){
      r = r * n;
      n = n - k;
      if( mx < r ){
        return "overflow";
      }
    }
    return r.toString();
  }
};

1000

const int N = 50 + 1;
double t[N][N];
double opt[N][N][N];

double rec(int begin, int end, int div)
{
  if( div == 1 )return t[begin][end];
  if( opt[begin][end][div] != -1 )return opt[begin][end][div];

  double mn = 1e256;

  for(int i=begin; i<end; ++i){
    double a = rec(begin, i, div / 2) + rec(i+1, end, div - div / 2);
    double b = rec(begin, i, div - div / 2) + rec(i+1, end, div / 2);
    mn = min( mn, min(a, b) );
  }

  return opt[begin][end][div] = mn;
}

class MinimumVariancePartition {
public:
  double minDev(vector <int> m, int k) {
    fill( &opt[0][0][0], &opt[N-1][N-1][N], -1 );

    sort( m.begin(), m.end() );
    for(int i=0; i<m.size(); ++i){
      for(int j=i+1; j<=m.size(); ++j){
        double ave = 0;
        for(int k=i; k<j; ++k){
          ave += m[k];
        }
        ave /= (double)(j - i);
        double sum = 0;
        for(int k=i; k<j; ++k){
          double n = (double)m[k] - ave;
          sum += n * n;
        }
        t[i][j-1] = sum / (double)(j - i);
      }
    }

    return rec(0, (int)m.size()-1, k);
  }
};