少しでも実装を楽にしたい

問題概要

英小文字のみからなる長さ $N$ の文字列 $S$ が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。

$S$ のどこかに 'x' を挿入する

制約

$N \le 10^{5}$

考えたこと

まず可能かどうかの判定だけなら簡単！！！
S から 'x' を取り除いたときに回文でなかったら不可能。回文だったら可能。

最小回数は以下のようにして求まる。たとえば

xxxaxxbxxxax

とかであれば、'x' なしなら "aba" であって、"aba" の両端と隙間にある 'x' の個数を数えると、

(3, 2, 3, 1)

となっている。これに対して

左端の 3 と右端の 1 とを比べて、1 を 3 にする (+2)
左から二番目の 2 と右から二番目の 3 とを比べて、2 を 3 にする (+1)

という風にすれば OK。この場合の答えは 3 となる。さて実装方針については以下のものが考えられる

以上のことを愚直に実装する (ランレングス圧縮して 'x' の個数ベクトルを求める)
もっと楽に実装する

実装方針 (1)：愚直

愚直に書いてもそれほど大変ではないが、ランレングス圧縮部分は慣れてないとややこしそう。とくに "axxbbax" のようなケースでは (0, 2, 0, 0, 1) となるが、このように 0 を含む場合に注意する。

#include <bits/stdc++.h>
using namespace std;

long long solve(string S) {
    string T = "";
    for (auto c : S) if (c != 'x') T += c;
    string T2 = T;
    reverse(T2.begin(), T2.end());
    if (T != T2) return -1;

    int N = T.size();
    vector<long long> nums(N+1, 0);
    int iter = 0;
    for (int i = 0; i < S.size();) {
        int j = i;
        while (j < S.size() && S[j] == 'x') ++j;
        nums[iter++] = j-i;
        i = j+1;
    }

    long long res = 0;
    for (int i = 0; i*2 < nums.size(); ++i) {
        res += max(nums[i], nums[(int)nums.size()-1-i]) -
            min(nums[i], nums[(int)nums.size()-1-i]);
    }
    return res;
}

int main() {
    string S;
    while (cin >> S) cout << solve(S) << endl;
}

実装方針 (2)：もっと楽に

そもそも可能かどうかの判定と、最小回数を求めるのは同時に行うこともできる。こんな風にすればよい。

左端から進めるポインタ i と、右端から進めるポインタ j をもつ
S[ i ] と S[ j ] が一致しているときは、i も j も進める (i は右に j は左に)
一致していないとき
- S[ i ] も S[ j ] も 'x' でない場合は不可能なので -1 を返す
- S[ i ] のみが 'x' の場合は、「回数」をインクリメントして、i のみ進める
- S[ j ] のみが 'x' の場合は、「回数」をインクリメントして、j のみ進める

この方針ならとても短く実装できる。

#include <bits/stdc++.h>
using namespace std;

long long solve(string S) {
    int res = 0;
    for (int i = 0, j = S.size() - 1; i < j; ) {
        if (S[i] == S[j]) ++i, --j;
        else if (S[i] == 'x') ++res, ++i;
        else if (S[j] == 'x') ++res, --j;
        else return -1;
    }
    return res;
}

int main() {
    string S;
    while (cin >> S) cout << solve(S) << endl;
}