概要

各分割位置 \(k\) について、変換後の値列 \(A\) に対して「非負・単調非増加」の補正列 \(D\) で全要素を英小文字範囲 \([97,122]\) に入れられるかを判定し、可能な \(k\) の個数を数える問題です。
XOR の前計算と、各位置での許容区間チェックを貪欲に行うことで解けます。

考察

まず、分割位置 \(k\) を固定したときに何が決まるか整理します。

• 前半 XOR: \(X_L = s_1 \oplus \cdots \oplus s_k\)
• 後半 XOR: \(X_R = s_{k+1} \oplus \cdots \oplus s_N\)

各文字の変換後値 \(A_i\) は - \(i \le k\) なら \(A_i = s_i \oplus X_R\) - \(i > k\) なら \(A_i = s_i \oplus X_L\)

です。

---

補正列 \(D\) の条件は、 1. \(D_i \ge 0\) 2. \(D_1 \ge D_2 \ge \cdots \ge D_N\) 3. \(97 \le A_i + D_i \le 122\)

位置 \(i\) だけ見ると、\(D_i\) は次の範囲にいなければなりません：

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

これを - 下限 \(L_i = \max(0,97-A_i)\) - 上限 \(U_i = 122-A_i\) とおくと、各 \(i\) で「\(D_i \in [L_i,U_i]\)」かつ全体で非増加列、という問題になります。

---

素朴法の問題点

• 各 \(k\) で \(X_L, X_R\) を毎回前後走査で計算すると \(O(N)\)、さらに判定も \(O(N)\) で合計 \(O(N^2)\) にはなるが、XOR計算を無駄に重ねると定数倍が大きい。
• また、\(D\) を探索的に試す（バックトラック等）はもちろん間に合いません。

重要な気づき

1. XORは累積で即時計算できる
   prefix XOR を持てば
   [ X_L = \text{pref}[k],\quad X_R = \text{pref}[N]\oplus \text{pref}[k] ] で \(O(1)\)。

2. \(D\) 判定は貪欲でよい
   左から順に、直前までで選んだ値を cur（次に使える最大値）として管理する。
   非増加条件より、次の \(D_i\) は cur 以下である必要があります。
   さらに区間条件で \([L_i,U_i]\) に入る必要があるので、

   • まず cur = min(cur, U_i) として上限を反映
   • その結果 cur < L_i なら不可能
   • そうでなければ \(D_i = cur\) と置ける

「毎回できるだけ大きい値を取る」ことで、後続にも有利（小さくしすぎると以降で詰む可能性が増える）なのでこの貪欲が正当です。

アルゴリズム

1. 文字列 \(S\) の prefix XOR 配列 pref を作る。
2. 全体 XOR totalXor = pref[N]。
3. 各分割位置 \(k=1..N-1\) について：
   1. \(X_L = pref[k]\), \(X_R = totalXor \oplus X_L\) を計算。
   2. cur = 122 で開始（\(D_1\) の最大候補）。
   3. \(i=0..N-1\) を順に処理：
      • \(A_i\) を計算（前半なら S[i]^XR、後半なら S[i]^XL）
      • \(L=\max(0,97-A_i)\), \(U=122-A_i\)
      • \(U<0\) なら即不可能（\(D_i\ge0\) でも上限を満たせない）
      • cur = min(cur, U)
      • cur < L なら不可能
   4. 最後まで通ればこの \(k\) は良い分割位置。
4. 良い分割位置の個数を出力。

計算量

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

実装のポイント

• S[i] は C++ では char なので、XOR時は (int)S[i] に明示キャストして扱うと安全です。

• cur は「直前までの条件を満たす中で、現在取りうる最大値」を意味します。更新順は
  

  1. 上限で絞る cur=min(cur,U)
     
  2. 下限判定 cur<L
     の順にするのが分かりやすいです。

• \(k\) は問題条件より 1 から N-1 までを走査します。

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    vector<int> pref(N + 1, 0);
    for (int i = 0; i < N; i++) {
        pref[i + 1] = pref[i] ^ (int)S[i];
    }
    int totalXor = pref[N];

    int good = 0;

    for (int k = 1; k <= N - 1; k++) {
        int XL = pref[k];
        int XR = totalXor ^ XL;

        int cur = 122; // maximal allowed D_1 due to upper bound

        bool ok = true;
        for (int i = 0; i < N; i++) {
            int c = (int)S[i];
            int A = (i < k) ? (c ^ XR) : (c ^ XL);

            int L = max(0, 97 - A);
            int U = 122 - A;

            if (U < 0) { // impossible even with D_i >= 0
                ok = false;
                break;
            }

            if (cur > U) cur = U; // enforce D_i <= U and non-increasing from previous
            if (cur < L) { // no feasible D_i
                ok = false;
                break;
            }
            // choose D_i = cur (max feasible) to keep future flexibility
        }

        if (ok) good++;
    }

    cout << good << '\n';
    return 0;
}

---

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