概要

メッセージを2つの部分に分割し、それぞれの部分の XOR 総和を用いて文字を変換したあと、特定の条件を満たす「単調非増加な補正値 \(D_i\)」を加えて元の英小文字の範囲（97〜122）に収められる分割位置 \(k\) の個数を求める問題です。

考察

1. 変換後の値 \(A_i\) の整理

分割位置 \(k\)（\(1 \le k < N\)）を固定したとき、変換後の値 \(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\)

ここで、\(X_L\) は \(S_1 \dots S_k\) の XOR 総和、\(X_R\) は \(S_{k+1} \dots S_N\) の XOR 総和です。これらは累積的な XOR 和（Prefix XOR）を事前に計算しておくことで、各 \(k\) に対して \(O(1)\) で求めることができます。

2. 補正値 \(D_i\) の条件

各 \(i\) について、最終的な値 \(A_i + D_i\) が \(97 \le A_i + D_i \le 122\) を満たす必要があります。 ここから、\(D_i\) が取り得る値の範囲 \([L_i, R_i]\) を導き出せます。 - \(D_i \ge 97 - A_i\) - \(D_i \le 122 - A_i\) - 問題文より \(D_i \ge 0\)

これらをまとめると、 - \(L_i = \max(0, 97 - A_i)\) - \(R_i = 122 - A_i\) となります。もし \(L_i > R_i\)（つまり \(A_i > 122\)）となる \(i\) が一つでもあれば、その分割位置 \(k\) は不適格です。

3. 単調非増加条件の判定

さらに、\(D_1 \ge D_2 \ge \dots \ge D_N\) という条件を満たす数列 \(D\) が存在するかを判定する必要があります。 各 \(D_i\) は \(L_i \le D_i \le R_i\) を満たしつつ、後ろの項ほど小さくなる（または等しくなる）必要があります。

この条件を満たす \(D\) が存在するための必要十分条件は、「自分自身以降のすべての下限値 \(L_j\) (\(j \ge i\)) の最大値が、自分の上限値 \(R_i\) 以下であること」です。 数式で表すと： $\(\max_{j=i}^{N} L_j \le R_i \quad (\text{すべての } i \text{ について})\)$

なぜなら、単調非増加であるためには \(D_i \ge D_{i+1} \ge \dots \ge D_N\) である必要があり、各 \(D_j\) は少なくとも \(L_j\) 以上でなければならないため、\(D_i\) は \(L_i, L_{i+1}, \dots, L_N\) のすべて以上である必要があるからです。その最小値（\(\max L_j\)）が自分の許容上限 \(R_i\) を超えてしまうと、条件を満たす \(D_i\) は選べません。

アルゴリズム

1. 前処理: 文字列 \(S\) の累積 XOR 和を計算し、任意の区間の XOR 総和を \(O(1)\) で出せるようにします。
2. ループ: \(k = 1\) から \(N-1\) まで繰り返します。
   • \(X_L\) と \(X_R\) を計算します。
   • 各 \(i\) について \(A_i\) を求め、そこから範囲 \([L_i, R_i]\) を計算します。
   • 配列の末尾から走査して「現在の \(L_j\) の最大値」を更新しながら、上記の判定式 \(\max L_j \le R_i\) をチェックします。
   • すべての \(i\) で条件を満たせば、カウントを 1 増やします。
3. 出力: 最終的なカウントを出力します。

計算量

• 時間計算量: \(O(N^2)\)
  • 分割位置 \(k\) の候補が \(N-1\) 個あり、各 \(k\) に対して長さ \(N\) の配列を走査するため、\(O(N \times N)\) となります。\(N=5000\) のとき \(N^2 = 2.5 \times 10^7\) であり、制限時間内に十分収まります。
• 空間計算量: \(O(N)\)
  • 累積 XOR 和や \(L, R\) 配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 累積 XOR: prefix_xor[i+1] = prefix_xor[i] ^ S[i] とすることで、S[0...k-1] の XOR 和は prefix_xor[k] で取得できます。

• 判定の効率化: 各 \(k\) のループ内で、後ろから走査（\(i = N-1\) から \(0\)）することで、current_max_L を更新しながら \(R_i\) との比較を一度の走査で行うことができます。

• 早期終了: \(A_i > 122\) となった時点でその \(k\) はスキップして構いません。

  ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

/**
 * Problem Summary:
 * A split position k (1 <= k < N) is "good" if there exists a correction sequence D such that:
 * 1. D_i >= 0 for all i
 * 2. D_1 >= D_2 >= ... >= D_N (non-increasing)
 * 3. 97 <= A_i + D_i <= 122 for all i, where A_i is the transformed ASCII code.
 * 
 * Transformed ASCII code A_i:
 * - A_i = S_i XOR X_R for 1 <= i <= k
 * - A_i = S_i XOR X_L for k+1 <= i <= N
 * where X_L is the XOR sum of the first k characters and X_R is the XOR sum of the rest.
 * 
 * Condition (3) with (1) implies:
 * max(0, 97 - A_i) <= D_i <= 122 - A_i
 * Let L_i = max(0, 97 - A_i) and R_i = 122 - A_i.
 * 
 * A non-increasing sequence D exists within [L_i, R_i] if and only if
 * max(L_i, L_{i+1}, ..., L_N) <= R_i for all i.
 */

int main() {
    // Optimize standard input and output
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;
    string S;
    cin >> S;

    // Precompute prefix XOR sums to calculate the XOR sum of any substring in O(1) time.
    // prefix_xor[i] = S[0] ^ S[1] ^ ... ^ S[i-1]
    vector<int> prefix_xor(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        prefix_xor[i + 1] = prefix_xor[i] ^ (int)(unsigned char)S[i];
    }

    int good_count = 0;
    // Pre-allocate memory for L and R to avoid repeated allocation in the loop.
    vector<int> L(N);
    vector<int> R(N);

    // Iterate through all possible split positions k (1 <= k < N).
    for (int k = 1; k < N; ++k) {
        int XL = prefix_xor[k];
        int XR = prefix_xor[N] ^ prefix_xor[k];

        bool possible = true;
        // Compute A_i and its corresponding correction range [L_i, R_i] for each i.
        for (int i = 0; i < N; ++i) {
            int Ai = (int)(unsigned char)S[i] ^ (i < k ? XR : XL);
            
            // If Ai > 122, no non-negative correction Di can bring Ai + Di into [97, 122].
            if (Ai > 122) {
                possible = false;
                break;
            }
            // L_i and R_i are the lower and upper bounds for the correction value D_i.
            L[i] = (Ai < 97) ? (97 - Ai) : 0;
            R[i] = 122 - Ai;
        }

        // If a valid range exists for every Ai, check the non-increasing constraint.
        if (possible) {
            int current_max_L = 0;
            // The condition max(L_j for j >= i) <= R_i must hold for all i.
            // We iterate backwards to maintain the running maximum of L_j.
            for (int i = N - 1; i >= 0; --i) {
                if (L[i] > current_max_L) {
                    current_max_L = L[i];
                }
                if (current_max_L > R[i]) {
                    possible = false;
                    break;
                }
            }
        }

        // If all conditions are satisfied, k is a good split position.
        if (possible) {
            good_count++;
        }
    }

    // Output the total number of good split positions.
    cout << good_count << endl;

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。