C++で拡張行列の直前の要素を効率的に求めるアルゴリズム

拡張行列（エクスパンディングマトリックス）とは、サイズが一定の倍率で増加し続ける行列のことです。本記事では、この拡張行列を題材とした問題について解説します。

ここでは、サイズが2倍ずつ拡大していく文字行列を扱います。元の行列のサイズがN×Nである場合、拡張後の行列は2N×2Nになります。座標(i, j)に存在する文字列が与えられたとき、その左隣、すなわち(i, (j - N - 1)%N)に存在する文字列を返すことが求められます。

拡張行列の仕組み

まず、初期段階の拡張行列を視覚化して理解を深めましょう。

元の行列 -> [ a, b ] [ c, d ]、2×2行列
{ a, b, c, d } を掛け合わせる
A X [ a, b ]
B X [ a, b ]
C X [ a, b ]
D X [ a, b ]
[ c, d ] [ c, d ] [ c, d ] [ c, d ]

拡張行列 -> [ aa, ab, ba, bb ]
[ ac, ad, bc, bd ]
[ ca, cb, da, db ]
[ cc, cd, dc, dd ]、4×4行列
さらに拡張するには { a, b, c, d } を掛け合わせ、8×8の行列が生成されます。

拡張行列 -> [ aaa, aab, aba, abb, baa, bab, bba, bbb ]
[ aac, aad, abc, abd, bac, bad, bbc, bbd ]
[ aca, acb, ada, adb, bca, bcb, bda, bdb ]
[ acc, acd, adc, add, bcc, bcd, bdc, bdd ]
[ caa, cab, cba, cbb, daa, dab, dba, dbb ]
[ cac, cad, cbc, cbd, dac, dad, dbc, dbd ]
[ cca, ccb, cda, cdb, dca, dcb, dda, ddb ]
[ ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd ]

上記は2つの初期拡張行列の例です。例えば、文字列「bcc」が与えられた場合、その左隣にある「add」を返す必要があります。また、行列は循環構造を持つと仮定します。つまり、与えられた文字列が(i, 0)の位置にある場合は、同じ行の(i, N-1)の位置にある文字列を返します。

入力: abb
出力: aba
説明: 8×8行列において、abbの左隣にあるのはabaです。

入力: aadc
出力: aacd

入力: abbcd
出力: abbcc

素朴なアプローチ

問題を見たときに最初に思いつく解法は、与えられた文字列を含む拡張行列を実際に構築することです。しかし、この方法は非常に複雑で非効率です。まず行列全体を生成し、その後に目的の文字列を検索する必要があるためです。

効率的なアプローチ

いくつかの初期拡張行列を注意深く観察すると、直前の要素を特定できる規則性が見つかります。具体的には以下の手順に従います。

• 文字列を末尾のインデックスから先頭に向かって走査します。

• 現在の要素が「b」または「d」である場合、「a」または「c」に変更し、走査を終了します。

• 現在の要素が「a」または「c」である場合、「b」または「d」に変更し、次のインデックスへ移動して同様の判定を繰り返します。

この規則は桁上がりの概念に似ています。「b」と「d」は各区画の後半に、「a」と「c」は前半に位置するため、左隣の要素を求める際には繰り下がりのような処理が必要になるのです。

C++での実装例

上記アプローチのC++コード

#include <bits/stdc++.h>
using namespace std;
int main (){
    string seq = "abbcd";
    int n = seq.length ();
    // 文字列を末尾から走査する
    for (int i = n; i >= 0; i--){
        // 要素が b または d の場合、変更して走査を終了する
        if (seq[i] == 'b'){
            seq[i] = 'a';
            break;
        }
        if (seq[i] == 'd'){
            seq[i] = 'c';
            break;
        }
        // 要素が a または c の場合、変更して次の要素へ進む
        if (seq[i] == 'a')
            seq[i] = 'b';
        else if (seq[i] == 'c')
            seq[i] = 'd';
    }
    cout << "The Previous sequence is: " << seq;
    return 0;
}

出力結果

The previous sequence is: abbcc

まとめ

本記事では、拡張文字行列の概念とその生成方法について解説しました。さらに、拡張行列内で特定の文字列の直前の要素を見つける問題を取り上げ、行列の拡張によって生じるパターンを理解することで、行列を実際に構築せずに効率的に解決する方法を紹介しました。

紹介したC++コードのロジックは、C、Java、Pythonなど他のプログラミング言語でも同様に実装可能です。このチュートリアルが皆様のお役に立てば幸いです。