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