SRM343Div2

250

int rec(int n, int depth)
{
  if( n < 10 )return depth;
  int m = 1;
  while( n ){
    m *= n % 10;
    n /= 10;
  }
  return rec(m, depth + 1);
}

class PersistentNumber {
public:
  int getPersistence(int n) {
    return rec(n, 0);
  }
};

500

bool valid(string s, int n)
{
  set<int> vis;
  for(int i=0; i<s.size(); ++i){
    if( vis.size() == n ) vis.clear();
    if( vis.count( s[i] ) ) return false;
    vis.insert( s[i] );
  }
  return true;
}

class CDPlayer {
public:
  int isRandom(vector <string> songlist, int n) {
    string s;
    for(int i=0; i<songlist.size(); ++i){
      s += songlist[i];
    }
    for(int i=0; i<min(n, (int)s.size()); ++i){
      string t = s.substr(0, i);
      string u = s.substr(i);
      if( valid(t, n) && valid(u, n) )return i;
    }
    return -1;
  }
};

1000
メモ化か?! と思ったけど、全探索でいけるみたい。

const int N = 16;
const int BIT = 1 << N;

int res[N][N];
vector<int> g;
int player;
bool alive[N];

int day(void);
int night(void);

int day(void)
{
  if( !alive[ player ] ) return 0;
  
  int rm, v = -1;
  for(int i=0; i<g.size(); ++i){
    if( !alive[i] ) continue;
    if( v < g[i] ){
      v = g[i];
      rm = i;
    }
  }
  
  alive[ rm ] = false;
  int ret = night();
  alive[ rm ] = true;
  
  return ret;
}

int night(void)
{
  if( !alive[ player ] ) return 0;

  int mx = 0;
  vector<int> tmp = g;
  for(int i=0; i<g.size(); ++i){
    if( !alive[i] )continue;
    if( i == player )continue;
    
    for(int j=0; j<g.size(); ++j){
      g[j] += res[i][j];
    }

    alive[i] = false;
    mx = max( mx, day()+1 );
    alive[i] = true;
    g = tmp;
  }  

  return mx;
}

class Mafia {
public:
  int play(vector <int> guilt, vector <string> r, int idx) {

    fill( alive, alive + N, true );
    g = guilt;
    player = idx;

    for(int i=0; i<r.size(); ++i){
      for(int j=0; j<r[i].size(); ++j){
        char c = r[i][j];
        res[i][j] = toupper( c ) - 'A' + 1;
        if( islower( c ) ) res[i][j] *= -1;
      }
    }
    
    return guilt.size() % 2 ? day() : night();
  }
};