AtCoder Grand Contest 019: B - Reverse and Compare
solution
実験。$O(N)$。
区間$[l, r)$の反転で変化しないのは$\mathrm{substr}(l, r) = \mathrm{reverse}(\mathrm{substr}(l, r))$のときだけ。 $\mathrm{substr}(l, r) \ne \mathrm{reverse}(\mathrm{substr}(l, r))$と仮定して、他の反転の結果と一致するのは$A_l = A_{r - 1}$ (あるいは$A_{l - 1} = A_r$) の場合のみ。 これは実験すれば出る。 反転を左端$l$と右端$r$から$[l, r)$で見るのでなく、中心$c$と半径$\delta$で$[c - \delta, c + \delta]$で見ておくと分かりやすい。 逆に$A_l \ne A_{r-1}$な$l \lt r-1$があればその反転は代表元のように見れて、これを数えればよい。
implementation
#include <iostream>
#include <array>
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using ll = long long;
using namespace std;
int main() {
string s; cin >> s;
int n = s.size();
array<int, 26> cnt = {};
ll result = 1;
repeat_reverse (i, n) {
char c = s[i] - 'a';
cnt[c] += 1;
result += n - i - cnt[c];
}
cout << result << endl;
return 0;
}