この記事では2021年1月2日に行われたAtCoder Beginner Contest 187のD問題について、Python3における解法をお伝えします。
なるべく分かりやすく解説できるよう心がけますが、競プロ初心者のため改善点・問題点がありましたらコメントまたはTwitterでご指摘ください。
Twitter：@soh_1121_
D：Choose Me
問題文
AtCoder 市で市長選挙が行われます。候補者は青木氏と高橋氏です。
市には N 個の町があり、i 番目の町には青木派の有権者が Ai 人、高橋派の有権者が Bi 人います。他に有権者はいません。
高橋氏は、それぞれの町で演説を行うことができます。
高橋氏がある町で演説を行った場合、その町の高橋派も青木派も全員高橋氏に投票します。
一方、高橋氏がある町で演説を行わなかった場合、その町の青木派は全員青木氏に投票し、高橋派は投票に行きません。
高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか？制約
・入力は全て整数
・1 ≤ N ≤ 2 × 105
・1 ≤ Ai , Bi ≤ 109入力
入力は以下の形式で標準入力から与えられる。N
A1 B1
⋮
AN BN出力
AtCoder Beginner Contest 187 D – Choose Me
答えを出力せよ。
具体的に高橋氏がある町で演説を行ったらどうなるか考えてみることで正解にたどり着きました。
いずれの町でも演説をしない場合、青木派の有権者は青木氏に投票し、高橋派の有権者は投票ないので、最大で青木氏が取りうる票数はすべての Ai の和となります。
n 番目の町1つだけで高橋氏が演説を行うと、n 番目の町の青木派 An 名は高橋派に寝返り、高橋派の有権者は Bn 名も投票に行くようになります。
こうなった際、どの程度高橋氏が盛り返すかというと、青木氏が失った An と高橋氏が獲得した An + Bn の差が縮まることとなります。
つまり、n 番目の町1つで演説することで 2 ✕ An + Bn 票、差が縮まるのです。
そこで、高橋氏が町を回ることで縮めた得票数が青木氏が得うる最大の得票数を超えたときが答えとなります。
ただし、演説する町の数を最小にする必要があります。
これは、縮められる票数を大きい順にソートして獲得できる票数の多い順に町で演説すると最小の町の数が求められます。
それでは実装を見てみましょう！
def main():
N = int(input())
A_max = 0
towns = []
for _ in range(N):
A, B = list(map(int, input().split()))
A_max += A
towns.append(2 * A + B)
towns.sort(reverse=True)
count = 0
T = 0
for town in towns:
count += 1
T += town
if A_max < T:
break
print(count)
main()
まず町の数 N を標準入力から取得し、青木氏の得うる最大の得票数 A_max を初期化、町ごとに何票差が縮められるかを保持する towns というリストを用意しています。
町の数だけループを回し、標準入力から青木派・高橋派の人数を取得。青木派の数は A_max に加算し、ループを回し終えれば最大の得票数が得られるようにしておきます。towns には前述した差を縮められる 2 * A + B を次々保存します。
入力値の処理が終わったら大きく差を縮められる順にソートします。ソートしたらあとは何個目の町で青木派の最大得票数を超えられるかを記憶する count と、町で演説したときの高橋氏の得票数 T を初期化します。
towns に保存されている文だけループを回し、演説した町の個数 count をインクリメント、高橋氏の得票数 T に縮められる票数 town を加算。青木派の最大得票数を超えたことろでループから出て count を出力してACです。
まとめ：ややこしそうな問題も１つずつ考えれば解けることも！
この記事では2021年1月2日に行われたAtCoder Beginner Contest 187のD問題について、Python3における解法をお伝えしました。
普段D問題は中々解けないのですが、今回は冷静に順に考えることで解くことができて嬉しかったですね…！
どちらかというと数学的な問題でプログラミング力とは異なるかもしれませんが、こういう問題もすぐ解けるようになると普段のプログラミングでも計算量の少ない実装方法を思いつきやすいのかなと思ったりもしています。
実務に役立つかはわかりませんが、趣味として楽しく精進していきたいです！