1122 文字列の \(2\) つの文字の境目となる場所を全探索することを考えます。

境目を \(S\) の \(i\) 文字目と \(i+1\) 文字目の間に固定して考えます。

境目をこの位置に固定した際に答えが \(1\) つ以上ある条件は \(S_i\) に \(1\) を足した数字が \(S_{i+1}\) になることです。逆に、この条件を満たす場合に条件を満たす 1122文字列 の個数は \(S_i,S_{i+1}\) が連続する数をそれぞれ \(c_1,c_2\) として \(\min(c_1,c_2)\) 個です。

以上を全ての \(i\) に対して足し合わせた値が問題の答えとなります。

例えば \(S=\) 11223 の場合、以下のように答えが求まります：

• \(i=1\) のとき： \(S_1=\) 1 、 \(S_2=\) 1 なので答えへの寄与はない。
• \(i=2\) のとき： \(S_2=\) 1 、 \(S_3=\) 2 で 1 は \(2\) 文字、2 は \(2\) 文字連続しているので答えへの寄与は \(\min(2,2)=2\) である。
• \(i=3\) のとき： \(S_3=\) 2 、 \(S_4=\) 2 なので答えへの寄与はない。
• \(i=4\) のとき： \(S_4=\) 2 、 \(S_5=\) 3 で 2 は \(2\) 文字、3 は \(1\) 文字連続しているので答えへの寄与は \(\min(2,1)=1\) である。
• 以上より、求める答えは \(2+1=3\) である。

以上より、文字 \(S_i\) が何文字連続しているかを求めることができればこの問題に正答できることが分かります。

文字 \(S_i\) が何文字連続しているかを求める方法はいくつか存在しますが、この解説では大きく \(2\) つ紹介します。

---

1. ランレングス圧縮

ランレングス圧縮とは値とその文字の出現回数を圧縮したデータとして持つものです。例えば \(S=\) 11223 をランレングス圧縮すると \((\)1\(,2),(\)2\(,2),(\)3\(,1)\) となります。 それぞれの文字が何回連続しているかの情報はまさにこのランレングス圧縮そのものです。ランレングス圧縮は \(O(N)\) 時間でできるので、全体として \(O(N)\) 時間で解くことができます。

---

2. 愚直に求める

以下のようなアルゴリズムでこの問題を解くことを考えます。

• \(i=1,2,\ldots,N-1\) に対して \(S_i\) に \(1\) を足して \(S_{i+1}\) になるならば以下の一連の操作を行う。
  • \(j=i\) として、 \(S_j=S_i\) を満たしている間 \(j\) を \(1\) 減らす操作を行う。
  • \(k=i+1\) として、 \(S_k=S_{k+1}\) を満たしている間 \(k\) を \(1\) 増やす操作を行う。
  • 答えへの寄与として \(\min(i-j,k+1-i)\) を得る。
• 上で得た答えへの寄与が問題の答えとなる。

上のアルゴリズムで答えが求まることは簡単に分かります。このアルゴリズムの計算量を考えます。

上のアルゴリズムでボトルネックとなる部分は \(j\) を減らす操作と \(k\) を減らす操作です。しかし、異なる \(i\) に対して \(j\) が同じ値を取ることがないので、 \(j\) を動かす操作にかかる計算量は全体で \(O(N)\) となります。 \(k\) についても同様です。したがって、全体の計算量は \(O(N)\) となることが分かります。

---

1.と2.のどちらの解法でも計算量 \(O(N)\) で解くことができます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3) (解法 1)

from itertools import groupby

s = input()
a = [(v, len(list(x))) for v, x in groupby(s)]
ans = 0
for i in range(len(a) - 1):
    if int(a[i][0]) + 1 == int(a[i + 1][0]):
        ans += min(a[i][1], a[i + 1][1])
print(ans)

実装例(Python3) (解法 2)

s = input()
n = len(s)
ans = 0
for i in range(n - 1):
    if int(s[i]) + 1 != int(s[i + 1]):
        continue
    j = i
    while j != -1 and s[j] == s[i]:
        j -= 1
    k = i + 1
    while k != n and s[k] == s[i + 1]:
        k += 1
    ans += min(i - j, k - i - 1)
print(ans)