概要

各分割位置 \(k\) について、XOR 変換後の値 \(A_i\) に対して、条件を満たす単調非増加な補正列 \(D\) が存在するかを判定します。

補正列の存在判定は、各 \(D_i\) が取り得る区間を考え、左から貪欲に決めることで効率よく行えます。

考察

分割位置 \(k\) を固定して考えます。

前半部分の XOR を \(X_L\)、後半部分の XOR を \(X_R\) とすると、変換後の値 \(A_i\) は次のようになります。

• \(1 \le i \le k\) のとき、\(A_i = S_i \oplus X_R\)
• \(k+1 \le i \le N\) のとき、\(A_i = S_i \oplus X_L\)

ここで \(S_i\) は文字の ASCII コードです。

---

次に、ある \(A_i\) に対して補正値 \(D_i\) が満たすべき条件を考えます。

問題の条件より、

\[ 97 \le A_i + D_i \le 122 \]

かつ

\[ D_i \ge 0 \]

です。

したがって、\(D_i\) が取り得る範囲は

\[ \max(0, 97 - A_i) \le D_i \le 122 - A_i \]

となります。

この下限を \(L_i\)、上限を \(U_i\) とします。

つまり、各位置 \(i\) について

\[ D_i \in [L_i, U_i] \]

を満たしつつ、

\[ D_1 \ge D_2 \ge \cdots \ge D_N \]

となるように選べるか、という問題になります。

---

単に各 \(i\) について \(L_i \le U_i\) かを見るだけでは不十分です。

例えば、

\[ D_1 \in [0, 0], \quad D_2 \in [1, 1] \]

の場合、それぞれ単独では選べますが、\(D_1 \ge D_2\) を満たせないので不可能です。

---

この判定は左から貪欲にできます。

現在選べる最大値を prev とします。

位置 \(i\) では、\(D_i\) は

• 前の値以下、つまり \(D_i \le prev\)
• 区間内、つまり \(D_i \le U_i\)

である必要があります。

そのため、選べる最大の値は

\[ \min(prev, U_i) \]

です。

これが \(L_i\) 未満なら、どの値を選んでも条件を満たせないので失敗です。

そうでなければ、その最大値を \(D_i\) として選びます。

最大値を選ぶのが最適なのは、次以降の値は「今の値以下」でなければならないため、今の値を大きくしておくほど後続の自由度が大きくなるからです。

---

また、各分割位置 \(k\) に対する \(X_L\), \(X_R\) は prefix XOR を使って高速に求めます。

文字列全体の XOR を total、先頭 \(k\) 文字の XOR を px[k] とすると、

\[ X_L = px[k] \]

\[ X_R = total \oplus X_L \]

です。

これは

\[ total = X_L \oplus X_R \]

であり、XOR には

\[ x \oplus x = 0 \]

という性質があるためです。

アルゴリズム

1. 文字列 \(S\) を ASCII コードの配列 vals に変換する。
2. prefix XOR 配列 px を作る。
   • px[i] は先頭 \(i\) 文字の XOR。
3. 各値 \(a = 0, 1, \ldots, 127\) について、
   • low[a] = max(0, 97 - a)
   • high[a] = 122 - a

を前計算しておく。 4. 分割位置 \(k = 1, 2, \ldots, N-1\) を全て試す。 5. 各 \(k\) について、 - \(X_L = px[k]\) - \(X_R = px[N] \oplus X_L\)

を求める。 6. 左から順に変換後の値 \(A_i\) を求め、補正値 \(D_i\) の範囲を使って貪欲に判定する。 - prev を十分大きい値、例えば 123 で初期化する。 - 各 \(A_i\) について、選べる最大値は min(prev, high[A_i])。 - それが low[A_i] 未満なら失敗。 - そうでなければ prev をその値に更新する。 7. 最後まで失敗しなければ、その \(k\) は良い分割位置なので答えを \(1\) 増やす。

計算量

• 時間計算量: \(O(N^2)\)
• 空間計算量: \(O(N)\)

各分割位置ごとに最大 \(N\) 文字を確認するため、全体で \(O(N^2)\) です。
制約は \(N \le 5000\) なので、十分間に合います。

実装のポイント

• Python では bytes として文字列を読むと、各文字を直接 ASCII コードの整数として扱えます。

  vals = list(data[1])
  

• ASCII コードは \(0\) 以上 \(127\) 以下なので、low と high は長さ \(128\) の配列として前計算できます。

• prev = 123 としているのは、補正値の上限は最大でも \(122\) だからです。
  したがって、123 は「最初は制限なし」を表す十分大きな値として使えます。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    vals = list(data[1])

    px = [0] * (N + 1)
    x = 0
    for i in range(N):
        x ^= vals[i]
        px[i + 1] = x
    total = x

    low = [0] * 128
    high = [0] * 128
    for a in range(128):
        high[a] = 122 - a
        if a < 97:
            low[a] = 97 - a

    ans = 0
    v = vals
    lo = low
    hi = high
    p = px
    n = N
    tot = total

    for k in range(1, n):
        xl = p[k]
        xr = tot ^ xl
        prev = 123
        ok = True

        for i in range(k):
            a = v[i] ^ xr
            u = hi[a]
            if prev > u:
                prev = u
            if prev < lo[a]:
                ok = False
                break

        if ok:
            for i in range(k, n):
                a = v[i] ^ xl
                u = hi[a]
                if prev > u:
                    prev = u
                if prev < lo[a]:
                    ok = False
                    break

        if ok:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。