AtCoder TTPC 2015 C - おおおかやま

問題
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_c

リンク先を読んで下さい


愚解法
指定された手順に従ってやる。
しかしこれは面倒だし無駄な作業なので、本当は規則性見つけてやるのが正解法です。
規則性を見つける解法ではまだ提出していませんので、解説も後日。

string S;
 
pair<int, int> findMaxT() {
  string r;
  pair<int, int> ret;
  string ookayama = "ookayama";
  int M = ookayama.size();
  int N = S.size();
  rep(i, N-M+1) {
    if(S[i] == 'o') {
      bool ok = 1;
      rep(j, M) {
        if(S[i+j] != ookayama[j]) ok = 0;
      }
      if(!ok) continue;
      int next_start = i-1;
      while(next_start >= 0 && S[next_start] == 'o')
        next_start --;
      next_start ++;
      if(next_start != i) {
        string t = string(S.begin() + next_start, S.begin() + i + M);
        if(r.size() < t.size()) {
          r = t;
          ret = make_pair(next_start, i + M);
        }
      }
    }
  }
  return ret;
}
 
void processB(string& T) {
  rep(i, T.size()-1) {
    if(T[i] == 'O' && T[i+1] == 'O') {
      T = T.substr(0, i) + 'o' + T.substr(i+2);
    }
  }
}
 
void processA(string& T) {
  while(1) {
    bool ok = 0;
    rep(i, T.size()-1) {
      if(T[i] == 'o' && T[i+1] == 'o') {
        T = T.substr(0, i) + 'O' + T.substr(i+2);
        processB(T);
        ok = 1;
      }
    }
    if(!ok) break;
  }
}
 
void solve() {
  rep(_, 100) {
    auto p = findMaxT();
    auto T = string(S.begin() + p.first, S.begin() + p.second);
    processA(T);
    S = S.substr(0, p.first) + T + S.substr(p.second);
  }
}
 
int main() {
  cin >> S;
  solve();
  cout << S << endl;
  return 0;
}