SRM 402: LargestGap

(問題概要)
循環する文字列の連続する'X'を1箇所消して、連続する'.'の数を最大化する
(正確には連続する'.'の数の配列を辞書順最大化する)

(解法)
ただのシミュレーション。おもしろくない・・・

#include <algorithm>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class LargestGap {
public:
  int getLargest(vector <string> board);
  

};

string delAt(const string &str, size_t pos){
  vector<bool> del(str.size(), false);

  for(size_t i = pos; ! del[i] && str[i] == 'X';
      i = (i == str.size() - 1 ? 0 : i + 1))
    del[i] = true;

  for(size_t i = (pos == 0 ? str.size() - 1 : pos - 1);
      ! del[i] && str[i] == 'X';
      i = (i == 0 ? str.size() - 1 : i - 1))
    del[i] = true;

  stringstream ss;
  REP(i,str.size()) if(!del[i])
    ss << str[i];
  return ss.str();
}

vector<int> gaps(const string &str){
  vector<bool> check(str.size(), false);
  vector<int> ret;

  REP(pos,str.size()) if(!check[pos] && str[pos] == '.'){
    int cnt = 0;
    for(size_t i = pos; ! check[i] && str[i] == '.';
	i = (i == str.size() - 1 ? 0 : i + 1)){
      check[i] = true; cnt++; }

    for(size_t i = (pos == 0 ? str.size() - 1 : pos - 1);
	! check[i] && str[i] == '.';
	i = (i == 0 ? str.size() - 1 : i - 1)){
      check[i] = true; cnt++; }

    if(cnt)
      ret.push_back(cnt);
  }

  sort(ret.rbegin(), ret.rend());

  return ret;
}

int LargestGap::getLargest(vector <string> board){
  stringstream ss;
  REP(i,board.size()) ss << board[i];
  string bd = ss.str();
  vector<pair<vector<int>, int> > memo;

  REP(i,bd.size())
    if(bd[i] == 'X' && (i == 0 || bd[i - 1] != 'X')){
      const string deleted = delAt(bd, i);
      const vector<int> cnt = gaps(deleted);
      cout << i << ": " << deleted << endl;
      REP(j,cnt.size()) cout << cnt[j] << " "; cout << endl;
      memo.push_back(make_pair(cnt, -i));
    }

  sort(memo.rbegin(), memo.rend());

  return -memo[0].second;
}