C++で文字列の最大重み変換を求めるアルゴリズムと実装方法

問題の概要

AとBのみで構成された文字列が与えられます。任意の文字を別の文字に切り替える(トグルする)ことで、この文字列を別の文字列へと変換できます。つまり、1つの文字列からは多数の変換パターンが考えられます。ここでの課題は、これらの変換の中で「最大の重み」を持つ変換を見つけ、その重みを求めることです。

重みの計算方法

文字列の重みは、以下の式で計算されます。

文字列の重み = ペアの重みの合計 + 単一文字の重みの合計 − トグル(切り替え)の総数

重みの計算には、以下のルールが適用されます。

• 連続する2文字は、互いに異なる場合にのみ「ペア」として扱われます。
• 1つのペアの重み(2文字が異なる場合)= 4
• 単一文字の重み = 1

具体例

入力文字列が「AA」の場合、出力は3になります。

• 「AA」から作れる変換は「AA」「AB」「BA」「BB」の4通りです。
• 最大の重みを持つのは「AB」または「BA」で、その重みは「1ペア − 1トグル」= 4 − 1 = 3 となります。

アルゴリズム

この問題は、再帰とメモ化(動的計画法)を組み合わせることで効率的に解けます。基本的な考え方は以下の通りです。

1. n == 1 の場合
   maxWeight(str[0..n-1]) = 1
2. str[0] != str[1] の場合(先頭2文字が異なる)
   maxWeight(str[0..n-1]) = Max(1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1]))
3. それ以外の場合(先頭2文字が同じ)
   maxWeight(str[0..n-1]) = Max(1 + maxWeight(str[1..n-1]), 3 + getMaxRec(str[2..n-1]))

各位置で「その文字を単独として扱う」か「次の文字とペアにする」かの2択を再帰的に試し、より大きな重みを選択していきます。ペアにする場合、2文字が異なるなら重み4が加算され、同じなら重み3(ペアの重み4からトグル1を引いた値)が加算されます。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
int getMaxRec(string &str, int i, int n, int lookup[]){
    if (i >= n) {
        return 0;
    }
    if (lookup[i] != -1) {
        return lookup[i];
    }
    int ans = 1 + getMaxRec(str, i + 1, n, lookup);
    if (i + 1 < n) {
        if (str[i] != str[i+1]) {
            ans = max(4 + getMaxRec(str, i + 2, n, lookup), ans);
        } else {
            ans = max(3 + getMaxRec(str, i + 2, n, lookup), ans);
        }
    }
    return lookup[i] = ans;
}
int getMaxWeight(string str){
    int n = str.length();
    int lookup[n];
    memset(lookup, -1, sizeof lookup);
    return getMaxRec(str, 0, str.length(), lookup);
}
int main(){
    string str = "AA";
    cout << "Result = " << getMaxWeight(str) << endl;
    return 0;
}

コードの解説

この実装では、メモ化再帰を用いて計算量を大幅に削減しています。lookup配列に「各位置から始まる部分文字列の最大重み」をキャッシュすることで、同じ部分問題を何度も再計算することを避けています。その結果、時間計算量はO(n)、必要なメモリもO(n)に抑えられます。単純な再帰のみの実装では指数時間かかる可能性がありますが、メモ化により文字列長に比例した高速な処理が可能になります。

出力

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Result = 3