【Python】加算と回転操作から辞書順最小の文字列を求めるプログラム

問題の概要

数字のみで構成された文字列 s と、2つの整数 a・b が与えられます。文字列 s に対しては、次の2つの操作を任意の回数・任意の順序で適用できます。

• 加算操作：奇数番目（インデックスは0始まり）のすべての桁に a を加えます。9にさらに加算した場合は0に戻る（循環する）ものとします。
• 回転操作：文字列 s を右方向に b 桁だけ回転します。

目的は、これらの操作を何度でも組み合わせて得られる文字列の中から、辞書順で最小の文字列を見つけることです。

入力例と出力例

たとえば、s = "5323"、a = 9、b = 2 が与えられた場合、出力は "2050" になります。この結果に至る操作の手順は次のとおりです。

• 回転："5323"
• 加算："5222"
• 加算："5121"
• 回転："2151"
• 加算："2050"

解法の考え方：幅優先探索（BFS）

操作を適用して生成できる文字列の総数は有限であるため、到達可能なすべての状態を探索すれば必ず答えが得られます。ここでは、キューを使った幅優先探索（BFS）で重複なく全状態を調べる方法を採用します。

具体的な手順は以下のとおりです。

1. 訪問済みの文字列を記録する集合 seen を用意します。
2. 初期状態として s を1つだけ持つキュー deq を作成します。
3. キューが空になるまで、次の処理を繰り返します。
   • キューの先頭から文字列 curr を取り出し、seen に追加します。
   • curr に加算操作を適用した結果 ad が未訪問であれば、deq と seen に追加します。
   • curr に回転操作を適用した結果 ro が未訪問であれば、deq と seen に追加します。
4. 探索終了後、seen に含まれる文字列のうち最小のものを返します。

すでに見た文字列を二度とキューに入れないことで、無駄な計算を避けながら確実にすべての候補を網羅できるのがこの手法のポイントです。

Pythonでの実装例

それでは、上記のアルゴリズムをPythonで実装してみましょう。

from collections import deque

def add_(s, a):
    res = ''
    for idx, i in enumerate(s):
        if idx % 2 == 1:
            num = (int(i) + a) % 10
            res += str(num)
        else:
            res += i
    return res

def rotate_(s, b):
    idx = len(s) - b
    res = s[idx:] + s[0:idx]
    return res

def solve(s, a, b):
    seen = set()
    deq = deque([s])

    while deq:
        curr = deq.popleft()
        seen.add(curr)

        ad = add_(curr, a)
        if ad not in seen:
            deq.append(ad)
            seen.add(ad)

        ro = rotate_(curr, b)
        if ro not in seen:
            deq.append(ro)
            seen.add(ro)

    return min(seen)

s = "5323"
a = 9
b = 2
print(solve(s, a, b))

コードのポイント

• add_ 関数：enumerate で各文字のインデックスを取得し、奇数番目の桁のみ (int(i) + a) % 10 で加算と循環を処理します。
• rotate_ 関数：スライスを活用し、末尾 b 文字を先頭へ移動させることで右回転を実現します。
• solve 関数：deque によるBFSで全状態を探索し、set で重複を排除したうえで min() により辞書順最小の文字列を返します。

実行結果

入力

"5323", 9, 2

出力

2050

まとめ

本記事では、加算と回転の2種類の操作を自由に組み合わせたときに得られる辞書順最小の文字列を、幅優先探索で求める方法を解説しました。状態空間が有限であることを利用し、訪問済み管理によって重複探索を防ぐのが重要なポイントです。この手法は、パズルやゲームの状態探索など、さまざまな問題にも応用できます。