Google Code Jam 2012 Round 3 Problem D. small "Lost Password"

gistfile1.cpp

// Problem Statement : http://code.google.com/codejam/contest/1835486/dashboard#s=p3

// (include, using省略)

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

int INF = 100000000;

typedef long long ll;

int k;
string s;
string leet = "oieastbg";
bool g[35][35];

ll solve() {
  rep(i, 35) {
    rep(j, 35) {
      g[i][j] = false;
    }
  }

  for(int i = 0; i+1 < s.size(); ++i) {
    g[s[i]-'a'][s[i+1]-'a'] = true;
    rep(j, 8) {
      if(s[i] == leet[j]) {
	g[26+j][s[i+1]-'a'] = true;
        break;
      }
    }
    rep(j, 8) {
      if(s[i+1] == leet[j]) {
        g[s[i]-'a'][26+j] = true;
        break;
      }
    }
    rep(j, 8) {
      rep(k, 8) {
        if(s[i] == leet[j] && s[i+1] == leet[k]) {
          g[26+j][26+k] = true;
        }
      }
    }
  }

  int ans = 1;
  vector<bool> used(35, false);
  rep(i, 35) {
    rep(j, 35) {
      if(g[i][j]) {
	used[i] = used[j] = true;
	++ans;
      }
    }
  }

  int sum = 0;
  rep(i, 35) {
    if(!used[i]) {
      continue;  
    }
    int in = 0;
    int out = 0;
    rep(j, 35) {
      if(g[i][j]) {
	++in;
      }
      if(g[j][i]) {
	++out;
      }
    }
    sum += max(out-in, 0);
  }
  ans += max(sum-1, 0);
  return ans;
}

int main(){
  srand(time(NULL));
  int T; scanf("%d\n", &T);
  for(int j = 1;j<=T;j++){
    cin >> k >> s;
    ll ans = solve();
    cout << "Case #" << j << ": " << ans <<endl;
  }
  return 0;
}