AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginner Contest 027 B – 島と橋
高橋君の独裁者っぷりが発揮される問題。
端から順番に見ていきながら、必要なら橋を掛けていけばいい。
# AtCoder Beginner Contest 027 B - 島と橋
# https://atcoder.jp/contests/abc027/tasks/abc027_b
# tag: 考察 高橋君
# 左側から順番に、橋をかける必要があるかどうか判定していく。
def main():
N = int(input())
pops = list(map(int, input().split()))
total = sum(pops)
# そもそも人数を均等にできないなら、-1 を返して終了
if total % N != 0:
print(-1)
return
# 各島あたりの人数を確認しておく
each = total // N
# 今繋げている島の数と、そこにいる人数を管理
n_islands = 0
g_pop = 0
result = 0
# 左端から島を見ていき、今の状態で各島の人数を
# 条件に合うように分配可能かどうかを確認する。
# 条件にあっていれば、次の島に橋を架ける必要はないが、
# 条件にあってなければ、橋を架ける必要がある。
for p in pops:
n_islands += 1
g_pop += p
# 今の状態で分配可能なら、橋は架けずに次の島から改めて見ていく
if g_pop / n_islands == each:
n_islands = 0
g_pop = 0
# ダメなら、橋を架ける ＝ 次の島の分も加算して考えていく
else:
result += 1
print(result)
main()
関連
