AtCoder ABC 027 B – 島と橋 Python解説

2021年11月22日

島と橋

N 個の島が横一列に並んでいる。左から i 番目の島と i+1 番目の島は隣り合っている。
はじめ、左から i 番目の島には a_i 人の住人が住んでいる。 高橋君はすべての島に同じ人数の住人が住むようにしたいと考えている。

高橋君は隣り合う 2 つの島の間に橋を架けることができる。 また、直接的または間接的に橋で結ばれた複数の島の間で、住人を自由に移動させることができる。
すべての島に同じ人数の住人が住むようにするために、架ける必要のある橋の本数の最小値を求めよ。

AtCoder Beginner Contest 027「島と橋」

入力から島の数と住民の数を受け取ったら、まず最初に、住民の総数を島の数で割ります。この数が、すべての島に同じ人数の住人が住むための数の目標になります。

n = int(input())
a = [int(x) for x in input().split()]
bridge = 0
human = 0
land = 1
cnt = sum(a) // n


for i in range(n):
    human += a[i]
    if human / land == cnt:
        human = 0
        land = 1
        pass
    else:
        bridge += 1
        land += 1
            
if sum(a) % n != 0:
    print(-1)
else:
    print(bridge)

for文の動きを見てみると、変数humanに最初の島の住民の数を入れ、human / land == cntになったら、島に住む人数と目標となるcntの数が同じなので、変数humanとlandを初期化しています。もし、 human / land == cnt ではなかったら、橋を架け、変数llandの値も1つ増やしています。

最後に住民の数を島の数で割り、もし余りが0でなかったら-1を出力。
もし、余りが0だったらbridgeの数を答えとして出力します。