【ABC081 B】「Shift only」を解く【Python3】

「AtCoder」解説一覧へ

AtCoder過去問精選10問まとめへ

「N 個の正の整数がすべて偶数だったとき、すべてを2で割ったものに置き換える」

という操作を行った際に、最大何回操作できるのか、という問題です。

一つずつ操作する

すべてを2で割ったものに置き換えるわけですが、これは一つ一つ見ていくことができます。

例えば、3個の整数で、操作できる回数がそれぞれ「A₁は13回」「A₂は3回」「A₃は7回」だった場合、最小の3回が答えになります。

以下に提出コードを書きます。

n = int(input())
a = list(map(int, input().split()))
ans = 100

for i in range(n):
    num = a[i]
    count = 0
    while(True):
        if num%2 == 0:
            num = num//2
            count += 1
        else:
            break
    if ans>count:
        ans = count

print(ans)

numに現在操作している数を入力しています。numが偶数の場合には割ったものに置き換えます。

countで回数を数えておき、numが奇数になってwhile文を抜けた後に、ansと比較します。

最小のものが答えなので、小さければansを置き換えます。

初期値のansが100なのは適当です。1≤A_i≤10⁹が制約であり、2¹⁰=1024であることから、ansは30以上にはならないと予測できるので、それより大きい数字であれば問題ありません。

すべて操作する

一つずつではなく、すべて偶数であるときにすべて操作する方法は、以下のように書けます。

n = int(input())
a = list(map(int, input().split()))
ans = 0

while True:
    li = []
    for i in a:
        if i%2 == 0:
            li.append(i//2)
        else:
            print(ans)
            exit(0)
    ans += 1
    a = li

空のリストliを作成しておいて、リストaの中身が偶数の場合に、割ったものをappend()で追加していきます。

2で割ったものを、リストliに入れ終えたら、リストaをそれに置き換えて、上の処理に戻ります。

この処理の回数が答えです。

上記のコードは以下のように簡略して書くこともできます。

n = int(input())
a = list(map(int, input().split()))
ans = 0

while all(i%2 == 0 for i in a):
    a = [i/2 for i in a]
    ans += 1

print(ans)

all()関数を使って、リストaの中身が偶数かどうか（i%2 == 0）をチェックします。

all()の中身がすべてTrueであるときにのみTrueを返すため、一つでも奇数があればループを抜けます。

ループ処理では、すべて2で割ったものをリストaに代入して、ansに1を加えています。

【ABC081】解説記事リスト

【ABC081 A】「Placing Marbles」を解く【Python3】

【ABC081 B】「Shift only」を解く【Python3】

「AtCoder」解説一覧に戻る