ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

AtCoder-ABC187 D - Choose Me【Python解答例】

AtCoder Beginner Contest187に出場したときはD問題が解けませんでしたが、解説をみてACできた解答例を書いていきます。
コンテスト時に提出したプログラムもNG例として載せてみます。
AtCoder Beginner Contest 187 - AtCoder


AtCoder Beginner Contest187 D - Choose Me

D - Choose Me

問題文

AtCoder 市で市長選挙が行われます。候補者は青木氏と高橋氏です。
市にはN個の町があり、i番目の町には青木派の有権者がAi人、高橋派の有権者がBi人います。他に有権者はいません。
高橋氏は、それぞれの町で演説を行うことができます。
高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。
一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。
高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか?

制約

・入力は全て整数
・1≤N≤2×10^5
・1≤Ai,Bi≤10^9

解答例

n = int(input())

x = 0
X = []
for i in range(n):
    a, b = map(int,input().split())
    x -= a
    X.append(a + a + b)

X.sort(reverse = True)

i = 0
while x <= 0:
    x += X[i]
    i += 1

print(i)

解説

N個町があり高橋氏が青木氏に勝って当選するのに必要な演説数を求める問題です。
i番目の町にはAi人の青木派とBi人の高橋派がいて、演説をすればAi + Bi人が高橋氏に投票します。
演説をしなければAi人の青木派が青木氏に投票し、Bi人の高橋派は投票しません。

公式解説にあるようにx = (高橋氏が得る票数) - (青木氏が得る票数)としてx > 0となるまで多くxが増加する町を演説していきます。
i番目の町を訪れたとき増加する高橋派の人数は2Ai + Biになりますので、リストXにはその人数を格納していきます。

入力を受け取り終わったら、リストXを降順でソートします。

whileをxが0より大きくなるまでループさせます。
ループ内ではxの増加が多い順でリストXに格納されていますので演説が必要な最小の町の数i が求まります。

ループを抜けてiを出力すればACをとれました。


NG例

n = int(input())

A = []
SUM = []
SUM_S = []
sum_a = 0
for i in range(n):
    a, b = map(int,input().split())
    A.append(a)
    SUM.append(a + b)
    SUM_S.append(a + b)
    sum_a += a

SUM_S.sort(reverse = True)

sum_takahashi = 0

i = 0
while True:
    if sum_takahashi > sum_a :
        break
    else:
        num = SUM_S[i]
        max_i = SUM.index(num)
        sum_takahashi += num
        sum_a -= A[max_i]
        del SUM[max_i]
        i += 1
print(i)

NG例としてコンテストに提出したプログラムも載せます。

変数名がめちゃくちゃわかりにくくて申し訳ないです…
青木氏に投票する人数をsum_a、高橋氏に投票する人数をsum_takahashiに代入していきました。

青木氏に投票する人数を高橋氏に投票する人数が多くなるまでループを回しました。
各町の青木派と高橋派の人数の合計をリストSUMに格納していき、合計人数が大きい順に町を演説するようにしています。
町を演説するたびにsum_takahashiにその町の合計人数を足し、sum_aからその町の青木派の人数を引いてます。

たぶんこの考え方では合計人数の順に演説するので、その町の青木派と高橋派の割合は考慮されていません。
実際TLEだけでなくWAも出たので、もっと考える必要がありました。



欲を言えば今回のD問題は解きたかったです…
D問題を解けるように今後も頑張りたいです。


ABC187の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com