ABC027-B - 島と橋を解く - 考えて競プロする

ABC027-B - 島と橋

N個の横一列に並んだ島があり、各島にいる人の数が与えられる

各島間に橋を渡して自由に人を行き来させることができるとき、

すべての島の人数を同じにするには最低いくつの橋が必要かを求める問題だ

すべての島の人数が同じになる、ということは

各島の人数は、全島の人数を島の数で割った平均になるということになる

この平均だが、全島の人数と島の数によっては整数にならない場合もある

この場合は割り切ることができないので

問題文中に示されている通り、"-1" を出力する必要がある

それでは、均等にできる数字が与えられた場合

どのようにして橋の数を求めるかを考えていく

まずは小さいサンプルで考えてみよう

1 2 3 1 2 3

この場合は左の3つと、右の3つ間に橋を渡して

2-2-2 2-2-2

のようになる（橋4本）

上記の例では、左右3つずつの2グループに分かれていることがわかると思う

なぜそのように分かれたか？

よく見ると、左右のどちらとも "1 2 3" と同じ数のまとまりであることがわかる

それでは、同じ数の並び同士でないといけないのだろうか？

ここで、問題に書かれている入力例2 に注目している

2 0 0 0 3

こちらは、左2個と右3個間で橋を渡すことで均等にできる

1-1 1-1-1

今度は同じ数のまとまりではない…

合計も 2 と 3 でバラバラである

しかし、左右とも均等にすると各項が 1 になるという共通点がある

つまり、各グループの平均が同じということになる

以上より、次のような方針で解いていきたいと思う

まずはじめに、全体の平均を求める

次に、端から平均を計算していって、全体の平均と一致したところで一区切り

そこで区切ったときにかける端の数をカウントする

以上の処理を最後の島まで続ける

以下にイメージを記載する

2 0 0 0 3　平均1

2 0 0 0 3　平均2

2-0 0 0 3　平均1　橋1本

2-0 0 0 3　平均0　橋1本

2-0 0-0 3　平均0　橋1本

2-0 0-0-3　平均1　橋1本 + 橋2本 = 橋3本

提出したコード

# 入力
N=int(input())
l=list(map(int,input().split()))

# 全島の人数を同じにできない場合
if sum(l)%N!=0:
  print(-1)
  exit()

# 全島の平均人数
ave=sum(l)//N

c=s=a=0
for x in l:
  a+=1 # 島の数
  s+=x # 人数

  # 全棟の平均人数と一致したとき、橋をかける
  if s/a==ave:
    c+=a-1 # 橋の数をカウント

    # 橋と人数をリセット
    a=0
    s=0

# 出力
print(c)