Pythonでバイナリ文字列を使った電球スイッチ問題を解くプログラム

問題の概要

部屋にn個の電球があり、0からn-1までの番号が振られています。これらの電球は左から右へ一列に並べられており、初期状態ではすべて消灯しています（0の状態）。ここで、与えられたターゲット配列「t」で表される状態を作り出すことが目標です。t[i]は、i番目の電球が点灯していれば「1」、消灯していれば「0」を意味します。

電球の状態を切り替えるスイッチが1つあり、反転操作は次のように定義されます。

• 任意の電球のインデックスiを選択する。
• インデックスiからn-1（右端）までのすべての電球の状態を反転させる。

このとき、ターゲットの状態を実現するために必要な最小の反転回数を求めます。

例えば、入力が t = "0101" の場合、出力は3になります。2番目の電球から反転すると状態は「0111」になり、次に3番目から反転すると「0100」になり、最後に最後の電球を反転することで「0101」が完成します。

解法のアプローチ

この問題は、左から右へ電球を走査しながら「現在の状態」と「ターゲットの状態」を比較することで効率的に解けます。反転操作は選んだ位置から右端までのすべての電球に影響を与えるため、左から順に処理すれば、各位置で状態が異なるときだけ反転を行えばよいことがわかります。

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

• カウンターcountを0で初期化する。
• 現在の状態を表すxを'0'で初期化する。
• tの各文字iについて以下を繰り返す。
• iがxと異なる場合、countを1増やし、xをiに更新する。
• 最終的なcountを結果として返す。

Pythonコード例

def solve(t):
    count = 0
    x = '0'
    for i in t:
        if i != x:
            count += 1
            x = i
    return count

t = "0101"
print(solve(t))

入力

"0101"

出力

3

まとめ

このアルゴリズムの計算量はO(n)で、文字列を一度走査するだけで答えが求まります。反転操作が右側全体に影響するという特性を利用し、状態が切り替わる回数を数えるだけというシンプルな発想で、最小反転回数を効率的に導き出せるのがポイントです。