Replace [第七回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202107-open/tasks/past202107_d

解説

https://atcoder.jp/contests/past202107-open/submissions/24466988

ちょっと考察、ちょっと実装の問題。

操作回数が最大となる操作

ここがまず1つ考察が必要な部分である。
今回は実は最適戦略があり、先頭から変換できるならば変換していくのが最も良い。
先頭から順にという部分が重要で例えば、axaxaxaの場合は真ん中で消すと損してしまうからである。
先頭から消せば最適なのかという問いについては、はっきりとした証明で答えることはできないのだが、
今回考慮するべき状況はaxaxaxa...のような?x?xの状況だけであり、この状況に限っては先頭を消さずに残すことで
それ以降有利になることはない、逆に言うと、先頭が残っている状態は消した場所を先頭に移すことでより良い状態に
遷移可能であるため、最適である。
（言葉を重ねた所でっぽいくらいの説得力しかないかも）

実装

よって、あとは消せるだけ消すを実装する。
stringから部分文字列を抜き出すときは、substrを使えばいい。
それでpatternと一致するものがあれば、3文字分を.に変換するという実装をしている。
一行で書いているので、見にくいかもしれないが、パターンに合致すれば...に変換するということをしているだけ。

int N; string S;
string patterns[] = { "axa","ixi","uxu","exe","oxo" };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, N) fore(pattern, patterns) if (S.substr(i, 3) == pattern) S[i] = S[i + 1] = S[i + 2] = '.';
    cout << S << endl;
}