反転

反転問題

次のような問題があります。

[問題]

Ｎ頭の牛が１列に並んでいて、それぞれの牛は前か後ろのいずれかを向いています。

農夫は全ての牛を前向きにするために、牛を回転する機械を買うことにしました。

この機会は購入時に 数Ｋ を設定する必要があり、１回の操作で Ｋ頭の連続する

牛 の向きを反転させることができます。

全ての牛を前向きにするために必要な最小の 操作回数Ｍ と、それを達成する

最小のＫ を求めてください。

解法・ソースコード

まず、一番左端の牛に注目します。この牛を含む区間は１つしかありません。

したがって、この牛が前を向いているならば、その区間は反転させる必要がありません。

逆に、この牛が後ろを向いているならば、その区間は反転させる必要があります。

そして、これ以降はこの１番左の区間は考える必要がなくなります。

これを繰り返し行うことによって、必要な最小の反転回数を求めることができます。

また、計算量 を落とすためにリストfを定義し、区間を反転させた場合は１そうでない場合は０を設定し、その合計値が奇数である場合は最初の向きとは逆に、そうでなければ最初の向きのままとなっていることを確認しています。

[Google Colaboratory]

#---------- 入力例 ----------
cows = 'BBFBFBB'    # F:前向き、B:後ろ向き
#----------------------------
n = len(cows)   # 牛の頭数
k = 1           # 求める最小の牛を回転させる連続頭数（初期化）
m = n           # 求める最小の操作回数（初期化）

# 牛を回転させる連続頭数ｋを固定した時の最小操作回数を求める
# 解が存在しない場合は -1 を返す
def calc(k):
    # 区間[i, i + k - 1 ]を回転させたかどうか
    f = [0 for _ in range(n)]
    res = 0         # 操作回数
    total = 0       # リストfの和
    for i in range(n - k + 1):
        if (dir[i] + total) % 2 != 0:   # 先頭の牛が後ろを向いている場合
            # 回転操作を行う
            res += 1
            f[i] = 1
        total += f[i]
        if i - k + 1 >= 0:
            total -= f[i - k + 1]
    # 残りの牛が前を向いているかどうかチェック
    for i in range(n - k + 1, n):
        if (dir[i] + total) % 2 != 0:
            return -1
        if i - k + 1 >= 0:
            total -= f[i - k + 1]
    return res

# 牛の方向を0(F：前向き),1(B：後ろ向き)に変換
dir = [0 if x == 'F' else 1 for x in list(cows)]

for i in range(1, n + 1):   # 牛の頭数分ループする
    print(i, '頭回転させる機械の場合')
    x = calc(i)
    if x >= 0 and m > x:    # 牛を全部前向きにでき、かつ操作回数がより少ない場合
        print(x, '回操作で牛を全部前向きにできる。')
        m = x       # 最小の操作回数を更新
        k = i       # 回転させる最小の連続頭数を更新
    else:
        print('牛の向きを全部前向きにするとはできない。')
    print()

print(f'解：回転させる最小の連続頭数={k}　最小の操作回数={m}')

[実行結果]

1 頭回転させる機械の場合
5 回操作で牛を全部前向きにできる。

2 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

3 頭回転させる機械の場合
3 回操作で牛を全部前向きにできる。

4 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

5 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

6 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

7 頭回転させる機械の場合
牛の向きを全部前向きにするとはできない。

解：回転させる最小の連続頭数=3　最小の操作回数=3

牛を連続で ３頭回す機械<.b> を購入すれば、最小３回の操作</ > で牛を全部前向きにできることが分かりました。