概要

メッセージを位置 \(k\) で分割してXOR変換した後、単調非増加な補正列を加えて全文字を英小文字範囲に収められるかを各 \(k\) について判定し、良い分割位置の個数を求める問題です。

考察

補正列の条件を整理する

変換後の値 \(A_i\) に対して、\(D_i\) が満たすべき条件は： - \(97 \le A_i + D_i \le 122\) より、\(\max(0,\ 97 - A_i) \le D_i \le 122 - A_i\)

各位置 \(i\) で \(D_i\) が取れる範囲 \([lo_i,\ hi_i]\) が決まります： - \(lo_i = \max(0,\ 97 - A_i)\) - \(hi_i = 122 - A_i\)

まず \(hi_i < 0\) や \(hi_i < lo_i\) なら、その位置だけで不可能です。

単調非増加条件をどう扱うか

\(D_1 \ge D_2 \ge \cdots \ge D_N\) という制約があるため、右から左に向かってグリーディに最小値を決めていけばよいことに気づきます。

右端（\(i = N-1\)）では \(D_N = lo_N\)（最小値）を選ぶのが最適です。左に進むとき、\(D_i \ge D_{i+1}\) が必要なので、\(D_i \ge \max(lo_i,\ D_{i+1})\) となります。各位置で可能な限り小さい値を選ぶ（＝左側の制約を緩める）のが最善です。もし \(\max(lo_i, D_{i+1}) > hi_i\) となったら、その分割位置は不可能です。

なぜこのグリーディが正しいか

右から見て \(D_i\) を最小化すると、それは左隣 \(D_{i-1}\) の下限を最も小さくします。逆に \(D_i\) を必要以上に大きくすると、左側の自由度が狭まるだけです。よって各位置で最小値を選ぶ貪欲法が最適です。

アルゴリズム

1. 累積XOR配列 prefix_xor を前計算する。
2. 各分割位置 \(k\)（\(1 \le k < N\)）について：
   • \(X_L = \text{prefix\_xor}[k]\)、\(X_R = \text{total\_xor} \oplus X_L\) を計算。
   • 各位置 \(i\) の変換値 \(A_i\) を求める（前半なら \(s_i \oplus X_R\)、後半なら \(s_i \oplus X_L\)）。
   • 右端から左端へ走査し、cur_d（現在の \(D\) の最小必要値）を更新：
     • cur_d = max(lo_i, cur_d)
     • cur_d > hi_i なら不可能と判定。
   • 最後まで走査できれば、その \(k\) は良い分割位置。
3. 良い分割位置の個数を出力。

計算量

• 時間計算量: \(O(N^2)\)（\(N-1\) 通りの \(k\) に対し、各 \(O(N)\) の判定）
• 空間計算量: \(O(N)\)（累積XOR配列とASCIIコード配列）

\(N \le 5000\) なので \(O(N^2) = O(25{,}000{,}000)\) は十分高速です。

実装のポイント

• 右から左への走査: 単調非増加制約は、右から左へ見ると「非減少」制約になるため、cur_d を max で更新していくだけで済みます。

• 早期打ち切り: hi_i < 0 や cur_d > hi_i の時点で break することで定数倍を改善しています。

• 累積XOR: \(X_L\) と \(X_R\) は累積XORから \(O(1)\) で求められます。全体XOR \(= X_L \oplus X_R\) の関係を使います。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    string S;
    cin >> N >> S;
    
    vector<int> s(N);
    for (int i = 0; i < N; i++) s[i] = (int)S[i];
    
    vector<int> prefix_xor(N + 1, 0);
    for (int i = 0; i < N; i++) prefix_xor[i + 1] = prefix_xor[i] ^ s[i];
    
    int total_xor = prefix_xor[N];
    int ans = 0;
    
    for (int k = 1; k < N; k++) {
        int XL = prefix_xor[k];
        int XR = total_xor ^ XL;
        
        bool valid = true;
        int cur_d = 0;
        
        for (int i = N - 1; i >= 0; i--) {
            int ai;
            if (i < k) ai = s[i] ^ XR;
            else ai = s[i] ^ XL;
            
            int lo = max(0, 97 - ai);
            int hi = 122 - ai;
            
            if (hi < 0 || hi < lo) { valid = false; break; }
            
            if (i == N - 1) {
                cur_d = lo;
            } else {
                cur_d = max(lo, cur_d);
            }
            
            if (cur_d > hi) { valid = false; break; }
        }
        
        if (valid) ans++;
    }
    
    cout << ans << endl;
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。