本記事では、CSP（中国情報オリンピック予選）直前に実施された模擬コンテストの4問について、解法と実装を解説する。

A. 素因数分解による数字列変換

各桁の数字を素因数に分解し、大きい素因数から順に出力する問題。例えば「6」は2×3なので、最終的な出力では「3」より「2」が先に来る必要がある。

各数字の素因数の個数を前計算し、7, 5, 3, 2の順に貪欲に出力する。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int tc;
    cin >> tc;
    while (tc--) {
        int len;
        string str;
        cin >> len >> str;
        
        bool only01 = true;
        for (char c : str) {
            if (c != '0' && c != '1') {
                only01 = false;
                break;
            }
        }
        if (only01) {
            cout << "-1\n";
            continue;
        }
        
        int cnt[10] = {};
        for (char c : str) {
            int d = c - '0';
            if (d <= 1) continue;
            // 各数字の素因数分解: 2,3,5,7
            if (d == 2) cnt[2]++;
            else if (d == 3) cnt[2]++, cnt[3]++;
            else if (d == 4) cnt[2] += 3, cnt[3]++;
            else if (d == 5) cnt[2] += 3, cnt[3]++, cnt[5]++;
            else if (d == 6) cnt[2] += 4, cnt[3] += 2, cnt[5]++;
            else if (d == 7) cnt[2] += 4, cnt[3] += 2, cnt[5]++, cnt[7]++;
            else if (d == 8) cnt[2] += 7, cnt[3] += 2, cnt[5]++, cnt[7]++;
            else if (d == 9) cnt[2] += 7, cnt[3] += 4, cnt[5]++, cnt[7]++;
        }
        
        // 大きい素因数から貪欲に出力
        while (cnt[7]--) {
            cnt[5]--, cnt[3] -= 2, cnt[2] -= 4;
            cout << '7';
        }
        while (cnt[5]--) {
            cnt[3]--, cnt[2] -= 3;
            cout << '5';
        }
        while (cnt[3]--) {
            cnt[2]--;
            cout << '3';
        }
        while (cnt[2]--) {
            cout << '2';
        }
        cout << '\n';
    }
    return 0;
}

B. 辞書順制約付き列削除

n個の文字列をm列比較し、辞書順を崩す列を最小化する問題。ある列で下の文字列が上より小さい場合、その列を削除するか、既に確定している行（前の列で大小関係が確定した行）を使って回避する。

確定済みの行を管理しつつ、削除が必要な列をカウントする。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    vector<bool> fixed(n, false); // fixed[i]: iとi-1の大小関係が確定
    int removed = 0;
    
    for (int col = 0; col < m; col++) {
        bool needRemove = false;
        for (int row = 1; row < n; row++) {
            if (grid[row][col] < grid[row-1][col] && !fixed[row]) {
                needRemove = true;
                break;
            }
        }
        if (needRemove) {
            removed++;
            continue;
        }
        // この列で確定する関係を記録
        for (int row = 1; row < n; row++) {
            if (grid[row][col] > grid[row-1][col]) {
                fixed[row] = true;
            }
        }
    }
    
    cout << removed << '\n';
    return 0;
}

C. 区間マージDP（メモリ最適化版）

隣接する同値区間をマージできる操作を繰り返し、得られる最大値を求める問題。dp[i][j] = 「値iを左端jからマージして得られる右端+1」の形で定義すると、dp[i][j] = dp[i-1][dp[i-1][j]] と遷移する。

メモリ制約に注意し、2行のスクロール配列で実装する。

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

const int MAXN = 3e6 + 10;
const int LOGV = 60;

int nxt[MAXN];
int val[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    
    long long answer = 0;
    
    for (int v = 1; v <= LOGV; v++) {
        for (int pos = 1; pos <= n; pos++) {
            if (val[pos] == v) {
                nxt[pos] = pos + 1;
            } else if (nxt[pos]) {
                nxt[pos] = nxt[nxt[pos]];
            }
            if (nxt[pos]) answer = v;
        }
    }
    
    cout << answer << '\n';
    return 0;
}

D. 区間異或と出現回数の組み合わせ

静的区間クエリで「区間内に偶数回出現する値の異或和」を求める問題。これは「区間内の全要素の異或和」と「区間内に奇数回出現する値の異或和」の差として表せる。

後者はMo's algorithmやBITで処理できるが、ここでは「最終出現位置」を管理するBIT解法を用いる。各値について、出現位置をトグルしながら前処理する。

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

const int MAXN = 1e6 + 10;

int arr[MAXN], prefixXor[MAXN];
int lastPos[MAXN], coord[MAXN];
int bit[MAXN], answer[MAXN];

struct Query {
    int L, R, idx;
    bool operator<(const Query& o) const {
        return R < o.R;
    }
} queries[MAXN];

void bitUpdate(int pos, int val, int n) {
    for (; pos <= n; pos += pos & -pos) bit[pos] ^= val;
}

int bitQuery(int pos) {
    int res = 0;
    for (; pos > 0; pos -= pos & -pos) res ^= bit[pos];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 座標圧縮
    vector<int> allVals;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        prefixXor[i] = prefixXor[i-1] ^ arr[i];
        allVals.push_back(arr[i]);
    }
    sort(allVals.begin(), allVals.end());
    allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end());
    
    int m = allVals.size();
    for (int i = 1; i <= n; i++) {
        coord[i] = lower_bound(allVals.begin(), allVals.end(), arr[i]) - allVals.begin() + 1;
    }
    
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> queries[i].L >> queries[i].R;
        queries[i].idx = i;
    }
    sort(queries, queries + q);
    
    // 右端でソートして処理
    int ptr = 0;
    for (int r = 1; r <= n; r++) {
        int c = coord[r];
        if (lastPos[c]) {
            bitUpdate(lastPos[c], arr[r], n); // 前回の出現をキャンセル
        }
        bitUpdate(r, arr[r], n);
        lastPos[c] = r;
        
        while (ptr < q && queries[ptr].R == r) {
            int L = queries[ptr].L, R = queries[ptr].R;
            int oddXor = bitQuery(R) ^ bitQuery(L-1);
            answer[queries[ptr].idx] = prefixXor[R] ^ prefixXor[L-1] ^ oddXor;
            ptr++;
        }
    }
    
    for (int i = 0; i < q; i++) {
        cout << answer[i] << '\n';
    }
    return 0;
}

この問題はCodeforces 703D「Mishka and Interesting sum」と同一の構造を持つ。区間クエリの前処理テクニックとして重要なパターンである。