AtCoder ABC 033 B – 町の合併 Python解説

スポンサーリンク

町の合併

N 個の町が合併し、1 つの新しい市になることになりました。合併前の i 番目の町は名称がSi​で、人口がPi人です。
新しい市の名称を、以下のように決めようとしています。

N 個の町の人口の合計の過半数以上の人口を有する町が存在するならば、新しい市の名称はその町の名称を引き継ぐことにする。

そのような町が存在しないならば、新しい市の名称は atcoder とする。

それぞれの町の名称と人口が与えられるので、合併後の新しい市の名称を出力してください。

AtCoder Beginner Contest 033 「町の合併」

入力から合併前の町の数、名称、人口が与えられるので、合併前の一番人口が多い町の名称と人口を保存しておきます。最後に人口の合計を出し、一番人口の多い町が過半数以上なのか、そうでないのかを見ていきます。

n = int(input())

ans = ""
num = 0
cnt = 0

for _ in range(n):
    s, p = input().split()
    p = int(p)
    cnt += p
    if p >= num:
        ans = s
        num = p
        
if num > cnt // 2:
    print(ans)
else:
    print("atcoder")

使う変数の説明をすると、ansにその時点で一番人口が多い町の名称、numはその時点で一番人口が多い町の人口、cntは合併後の人口の総数を入れます。

for文の中のif文で町の人口を上回ったら、人口と名称を更新しています。
最後にnumが過半数(cnt // 2)を超えたらansを、そうでなかったらatcoderを出力します。