AtCoder Beginner Contest 027 B – 島と橋 をPython3で解く

Share


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()
Share

コメントを残す

メールアドレスが公開されることはありません。