001 - Three Color Reduction　解説

実行時間制限: 2sec / メモリ制限: 1024 MB

解説

　本問題は、文字を対称群 $S_3$ の互換（長さ2の巡回置換）に紐付けることで、状態数の非常に少ない動的計画法（DP）に帰着させることができます。

1. 群論への帰着（$S_3$との対応）

　'A', 'B', 'C' の3種類の文字を、それぞれ3要素の置換（互換）に対応させます。

'A' $\leftrightarrow (1\ 2)$
'B' $\leftrightarrow (2\ 3)$
'C' $\leftrightarrow (1\ 3)$

この対応付のもとでは、操作は以下のように考えられます：

連続する同じ2文字を消す：
'A' + 'A' $\to$ 空文字列。置換で考えると $(1\ 2)(1\ 2) = id$（単位元）となり、文字列の積が不変に保たれます。
「XYX」を「Z」に置き換える：
'A' + 'B' + 'A' $\to$ 'C'。置換で考えると $(1\ 2)(2\ 3)(1\ 2) = (1\ 3)$ となり、これも積が一致します。
「XYZ」を「Y」に置き換える：
'A' + 'B' + 'C' $\to$ 'B'。置換で考えると $(1\ 2)(2\ 3)(1\ 3) = (2\ 3)$ となり、やはり積が一致します。

この考察により、各文字を $S_3$ の元とみなして、全体の積が $id$ になるような置き換え方のうち、コストが最小のものを求めればよいということがわかります。

S_3 との同一視に関する厳密な証明

【命題の定式化】
　文字 '$\text{A}$', '$\text{B}$', '$\text{C}$' をそれぞれ対称群 $S_3$ の互換 $a=(1\ 2), b=(2\ 3), c=(1\ 3)$ と対応させます。文字列 $T$ に対し、その各文字に対応する $S_3$ の元を順番に掛け合わせた積を $\pi(T)$ と定義します（空文字列の場合は単位元 $e$ とします）。このとき、「文字列 $T$ が問題の操作を繰り返して空文字列にできる」ための必要十分条件は、「$\pi(T) = e$」であること、という命題が成り立ちます。

【必要性の証明】（空文字列にできる $\implies \pi(T) = e$）
　問題で許可されている3つの操作が、文字列全体が表す $S_3$ の元の積 $\pi(T)$ を不変に保つことを示します。

操作1（$\text{X}\text{X} \to$ 空）:
各互換は2乗すると単位元になるため、$x^2 = e$ が成り立ちます。したがって、隣り合う同じ文字を消去しても全体の積は変わりません。
操作2（$\text{X}\text{Y}\text{X} \to \text{Z}$）:
異なる2つの互換の積に、さらに左の互換を掛けると残りの互換になります。例えば $(1\ 2)(2\ 3)(1\ 2) = (1\ 3)$ すなわち $a b a = c$ です。したがって置換の前後で積は不変です。
操作3（$\text{X}\text{Y}\text{Z} \to \text{Y}$）:
異なる3つの互換の積は、中央の互換と等しくなります。例えば $(1\ 2)(2\ 3)(1\ 3) = (2\ 3)$ すなわち $a b c = b$ です。これも積の値を不変に保ちます。

　初期文字列にどのような操作を行っても $\pi(T)$ の値は変わらず、最終的に空文字列（$\pi(\text{空}) = e$）に到達できるのであれば、初期状態の文字列 $T$ についても $\pi(T) = e$ でなければなりません。

【十分性の証明】（$\pi(T) = e \implies$ 空文字列にできる）
　$\pi(T) = e$ である文字列 $T$ は、適切な操作を行うことで必ず長さを真に短くできることを、文字列の長さ $|T|$ に関する数学的帰納法で示します。

　$|T| = 0$ のときは既に空文字列であるため自明に成り立ちます。任意の操作で文字列の長さは2だけ減るので、偶奇性を考えれば、$\pi(T) = e$ のとき $|T|$ は必ず偶数になります。 $|T| \ge 2$ とし、文字列が空でないと仮定します。

隣り合う2文字が同じ場合:
操作1を適用することで、文字列の長さを $2$ 減らすことができます。
隣り合う2文字がすべて異なる場合:
$|T| = 2$ の場合、$\text{X} \neq \text{Y}$ ならば $\pi(T) = x y \neq e$ となり、$\pi(T) = e$ という仮定に矛盾します。よって $|T| \ge 4$（偶数長）です。隣り合う文字がすべて異なる長さ $3$ 以上の部分文字列は、必ず「$\text{X}\text{Y}\text{X}$」または「$\text{X}\text{Y}\text{Z}$」のいずれかのパターンを含みます。この部分にそれぞれ操作2または操作3を適用することで、積の値を $e$ に保ったまま文字列の長さを $2$ 減らすことができます。

　したがって、$\pi(T) = e$ であり $|T| \ge 2$ である限り、必ずいずれかの操作を適用して長さを $2$ 減らした文字列 $T'$（$\pi(T') = e$）を得ることができます。これを繰り返すことで、有限回の操作で必ず空文字列に到達できることが示されました。

2. 動的計画法 (DP) によるコスト最小化

　左から順番に文字を決定していくため、以下のDPを考えます。

dp[i][g] ：先頭から $i$ 文字目までを決定したとき、そこまでの $S_3$ における積が $g$ になるための最小コスト

　対称群 $S_3$ の要素数は $3! = 6$ 個しかないため、状態数は $N \times 6$ であり、遷移は次に選ぶ文字（'A', 'B', 'C'）に対応する置換を右から掛けるだけです。'?' の場合は、それぞれの文字に対応するコストを加算したうえで、3通りすべての遷移を行い min を取ります。

　最終的な答えは dp[N][id] となります（到達不可能な場合や $N$ が奇数の場合は -1 となります）。以上より、この問題を $O(N)$ の計算量で解くことができました。

コード例

　以下はC++による想定解法のコードです。

                            C++
                        

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

using namespace std;

const long long INF = 1e18;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    string s;
    cin >> s;

    // '?' の個数をカウント
    int k = 0;
    for (char c : s) {
        if (c == '?') k++;
    }

    // コストの読み込み
    vector<vector<long long>> cost(k, vector<long long>(3));
    for (int i = 0; i < k; i++) {
        cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
    }

    // 対称群 S3 の全要素を配列の置換として定義
    // 0: id, 1: A(1 2), 2: B(2 3), 3: C(1 3), 4: (1 2 3), 5: (1 3 2)
    vector<vector<int>> S3 = {
        {0, 1, 2}, 
        {1, 0, 2}, 
        {0, 2, 1},
        {2, 1, 0}, 
        {1, 2, 0}, 
        {2, 0, 1}
    };

    // 置換 p が S3 の何番目の要素かを取得するラムダ式
    auto get_idx = [&](const vector<int>& p) {
        for (int i = 0; i < 6; i++) {
            if (S3[i] == p) return i;
        }
        return -1;
    };

    // 積の乗積表を事前計算
    vector<vector<int>> mult(6, vector<int>(6));
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            vector<int> p(3);
            for (int m = 0; m < 3; m++) p[m] = S3[i][S3[j][m]];
            mult[i][j] = get_idx(p);
        }
    }

    // dp[要素のインデックス] = 最小コスト
    vector<long long> dp(6, INF);
    dp[0] = 0; // 初期状態は単位元 id、コスト0

    int q_idx = 0;
    for (char c : s) {
        vector<long long> next_dp(6, INF);
        for (int i = 0; i < 6; i++) {
            if (dp[i] == INF) continue;

            // 'A' または '?' の遷移
            if (c == 'A' || c == '?') {
                int nxt = mult[i][1];
                long long add_cost = (c == '?') ? cost[q_idx][0] : 0;
                next_dp[nxt] = min(next_dp[nxt], dp[i] + add_cost);
            }
            // 'B' または '?' の遷移
            if (c == 'B' || c == '?') {
                int nxt = mult[i][2];
                long long add_cost = (c == '?') ? cost[q_idx][1] : 0;
                next_dp[nxt] = min(next_dp[nxt], dp[i] + add_cost);
            }
            // 'C' または '?' の遷移
            if (c == 'C' || c == '?') {
                int nxt = mult[i][3];
                long long add_cost = (c == '?') ? cost[q_idx][2] : 0;
                next_dp[nxt] = min(next_dp[nxt], dp[i] + add_cost);
            }
        }
        // '?' を処理したらインデックスを進める
        if (c == '?') q_idx++;
        
        dp = next_dp;
    }

    // 長さが奇数、または到達不可能な場合は -1
    if (n % 2 != 0 || dp[0] == INF) {
        cout << -1 << endl;
    } else {
        cout << dp[0] << endl;
    }

    return 0;
}

                        