概要

各分割位置 \(k\) について、暗号変換後の値 \(A_i\) に対して、条件を満たす補正列 \(D_i\) が存在するか判定します。
補正列を直接探すのではなく、各 \(D_i\) が取り得る範囲を考えることで効率よく判定します。

考察

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

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

• \(i < k\) のとき、\(A_i = c_i \oplus X_R\)
• \(i \ge k\) のとき、\(A_i = c_i \oplus X_L\)

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

---

次に、補正値 \(D_i\) について考えます。

条件

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

かつ

\[ D_i \ge 0 \]

より、各 \(D_i\) はある区間に入っていなければなりません。

具体的には、

\[ D_i \ge 97 - A_i \]

ですが、\(D_i\) は非負なので、

\[ L_i = \max(0, 97 - A_i) \]

また、

\[ D_i \le 122 - A_i \]

なので、

\[ U_i = 122 - A_i \]

とすると、

\[ L_i \le D_i \le U_i \]

である必要があります。

---

さらに、補正列は単調非増加です。

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

つまり、後ろの値ほど大きくなってはいけません。

ここで、先頭から順に見ていくことを考えます。

位置 \(i\) で \(D_i\) を選ぶとき、過去の \(D_1, \ldots, D_{i-1}\) より大きくすることはできません。
また、それぞれの \(D_j\) は高々 \(U_j\) です。

したがって、\(D_i\) は少なくとも次の値以下でなければなりません。

\[ \min(U_1, U_2, \ldots, U_i) \]

これを limit とします。

位置 \(i\) において、

\[ L_i > \min(U_1, U_2, \ldots, U_i) \]

となると、\(D_i\) を選ぶことができないため、その分割位置は不可能です。

逆に、すべての \(i\) で

\[ L_i \le \min(U_1, U_2, \ldots, U_i) \]

が成り立つなら、実際に

\[ D_i = \min(U_1, U_2, \ldots, U_i) \]

と選べばよいです。
この列は明らかに単調非増加で、各 \(D_i\) も許される範囲に入ります。

---

例えば、ある分割位置で補正値の範囲が次のようになったとします。

\[ [0, 22], [0, 3], [7, 32] \]

3 番目では \(D_3 \ge 7\) が必要です。
しかし、2 番目までを見ると \(D_2 \le 3\) なので、単調非増加条件より \(D_3\) は \(D_2\) 以下でなければなりません。
つまり \(D_3 \le 3\) である必要があり、\(D_3 \ge 7\) と矛盾します。
この場合は不可能です。

---

素朴に補正列 \(D\) を全探索すると、各位置で複数の候補があるため指数時間になってしまいます。
そこで、各 \(D_i\) の区間と、これまでの上限の最小値だけを管理することで、各分割位置を \(O(N)\) で判定できます。

また、\(X_L, X_R\) は累積 XOR を使うことで高速に求められます。

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

\[ X_L = \text{pref}[k] \]

\[ X_R = \text{total} \oplus X_L \]

です。

アルゴリズム

1. 各文字を ASCII コードに変換して配列 c に入れる。
2. 累積 XOR 配列 pref を作る。
   • pref[i] は先頭 \(i\) 文字の XOR。
3. 各分割位置 \(k = 1, 2, \ldots, N-1\) について以下を行う。
   1. \(X_L = \text{pref}[k]\) を求める。
   2. \(X_R = \text{pref}[N] \oplus X_L\) を求める。
   3. limit を十分大きい値で初期化する。
   4. 各位置 \(i\) について、変換後の値 \(A_i\) を計算する。
   5. \(D_i\) の取り得る範囲 $\( L_i = \max(0, 97 - A_i) \)\( \)\( U_i = 122 - A_i \)$ を求める。
   6. limit = min(limit, U_i) と更新する。
   7. もし \(L_i > \text{limit}\) なら、この分割位置は不可能。
4. 最後まで不可能にならなければ、その分割位置を良い分割位置として数える。
5. 答えを出力する。

計算量

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

分割位置は \(N-1\) 個あり、それぞれについて長さ \(N\) の列を確認するため、全体で \(O(N^2)\) です。
制約は \(N \le 5000\) なので十分高速に実行できます。

実装のポイント

• 累積 XOR により、各分割位置の \(X_L, X_R\) を \(O(1)\) で求められます。

• \(D_i\) の範囲は $\( [\max(0, 97 - A_i),\ 122 - A_i] \)$ です。

• limit は「現在位置までの \(U_i\) の最小値」を表します。

• 各位置で L > limit なら、その時点でその分割位置は不可能です。

  ソースコード

#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> c(N), pref(N + 1, 0);
    for (int i = 0; i < N; i++) {
        c[i] = (int)S[i];
        pref[i + 1] = pref[i] ^ c[i];
    }

    int total = pref[N];
    int ans = 0;

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

        bool ok = true;
        int limit = 1e9;

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

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

            limit = min(limit, U);
            if (L > limit) {
                ok = false;
                break;
            }
        }

        if (ok) ans++;
    }

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

---

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