AtCoder Beginner Contest 027 B問題

B: 島と橋 - AtCoder Beginner Contest 027 | AtCoder

問題

  • N個の横一列に並んだ島にそれぞれ何人か住人がいる.
    • 左からi番目の島にはa_i人が住んでいる
  • 隣り合う島には橋をかけることができ,住人を相互に移動させることができる.
  • すべての島に均等に人を住まわせることは可能か.
    • 可能なら,少なくともいくつ橋が必要か.

解法

  • 住人の合計が島の数で割り切れなければ,均等に住まわせることが不可能.
  • 可能な場合,任意のiについて,以下が満たされればよい.

(Σ[k=1,i]a_k)/i = (Σ[k=i+1,N]a_k)/(N-i)

  • つまりどこで分けても(左側1島あたりの人口)=(右側1島あたりの人口)にしたらいい.

コード

"可能な場合"の解法が素敵だった(というか頭が悪くて思いつかなかった)ので.

N = int(input())
a = list(map(int,input().split()))

ans = 0
if sum(a) % N != 0:
	print(-1)
else:
	for i in range(N):
		if sum(a[:i+1])/(i+1) != sum(a)/N:
			ans += 1
	print(ans)

今のところ(コンテスト終了後1h30min経過)コード長最短っぽくてちょっと嬉しい.
しかしforブロック内がグッチャグチャで見にくい......

for i in range(1,N-1):
    if sum(a[:i])/i != sum(a)/N:

としたほうがよかった気もする.目が疲れて夏風邪悪化しましたとさ.