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; }