Pythonで倍加・反転・入替を繰り返すパターン列のn番目を求める方法

整数 n が与えられたとき、特定の規則に従って生成される文字列パターン列の n 番目の値を求める問題を考えます。このパターン列は次のように始まります。

• xxy
• xxyxxy
• yxxyxx
• xyyxyy
• xyyxyyxyyxyy
• …

パターンを生成する3つのルール

最初の項を xxy とし、次の値を作るには以下のルールを順番に適用します。

• 倍加（ダブル）： 文字列をそれ自身と連結して、長さを2倍にします。
• 反転（リバース）： 直前の操作が倍加だった場合、文字列を前後逆に並べ替えます。
• 入替（スワップ）： 直前の操作が反転だった場合、すべての x を y へ、y を x へ置き換えます。
• この一連の手順を繰り返します。

たとえば入力が n = 5 のとき、出力は "yyxyyxyyxyyx" となります。

変化の過程を追ってみる

解き方のアプローチ

ポイントは、「倍加 → 反転 → 入替」という3種類の操作が周期的に巡回することです。そこでカウンタ i を用意し、i % 3 の値に応じて適用する操作を切り替えながら、n 回の処理を繰り返します。

• i = 0、ret = "xxy" として初期化します。
• i < n の間、次を繰り返します。
  • i % 3 == 0 のとき：ret = ret + ret で倍加します。
  • i % 3 == 1 のとき：ret を反転します。
  • 上記以外のとき：ret 内の x と y をすべて入れ替えます。
• 各周回の末尾で i を1増やし、ループ終了後に ret を返します。

Pythonでの実装例

class Solution:
    def solve(self, n):
        i = 0
        ret = "xxy"
        while i < n:
            if i % 3 == 0:
                ret += ret                    # 倍加：文字列を自身と連結
            elif i % 3 == 1:
                ret = ret[::-1]               # 反転：スライスで前後を逆順に
            else:
                # 入替：x と y を相互に置換
                ret = "".join("y" if c == "x" else "x" for c in ret)
            i += 1
        return ret

ob = Solution()
print(ob.solve(5))

入力

5

出力

yyxyyxyyxyyx

計算量のポイント

倍加操作が行われるのは i % 3 == 0 のタイミング、すなわち3回に1回なので、n 回の操作後の文字列長は約 3 × 2^(n/3) になります。n が大きくなると文字列は指数関数的に増大するため、このアプローチは n が小〜中規模の場合に適しています。なお、入替操作は str.maketrans() と translate() を使うと、さらに簡潔に記述することも可能です。