C - Not Adjacent Editorial by seekworser


この問題では、同じ文字が隣接しないような極大な区間全てに対して、区間の長さを \(k\) として \(\frac{k(k+1)}{2}\) を足し合わせたものが答えです。 これは、全ての連続する同じ文字の間に ,を挿入したのち、文字列を , で分割したときの各部分文字列について同様の計算を行うことで計算ができます。

ところで、全ての連続する a の間に , を挿入する操作は文字列に対して出現する(出現位置に被りのない) aaa,aで置き換える操作を \(2\) 回行うことにより可能です。(このような置き換えは Python の replace などが対応します。)詳細は以下の実装例も参照ください。

以上によりこの問題を解くことができます。

(実装例: python)

s = input()
for c in "abc":
    s = s.replace(c + c, c + "," + c)  # 一度目のreplaceで "aaaaaa..." が "a,aa,aa,a..." になる
    s = s.replace(c + c, c + "," + c)  # 二度目のreplaceで "a,aa,aa,a..." が "a,a,a,a,a,a..." になる
s = s.split(",")
ans = 0
for t in s:
    m = len(t)
    ans += m * (m+1) // 2
print(ans % 998244353)

posted:
last update: