AtCoder Problemsが🟫茶diffと判定した問題から重点的にやっておこう。
という方針を立てました。

このレベル帯の問題が出来ないことが多いと感じるんですよ。
問題に書いてある通りに実装するとTLEで、実は数学的に計算量減らせますよ。系の問題が多い、このレベル帯。

とりあえず、この問題やります。

問題概要

青木氏と高橋氏が選挙をする。

市にはN個の町があり、i番目の街には青木派がAi人、高橋派がBi人います。

高橋氏が青木氏より多く票を獲得するためには、最小でいくつの町で演説をする必要があるでしょうか？

解法

$X =$ 高橋派の票数 $-$ 青木派の票数

と定義します。

$X > 0$
になると高橋氏の勝利。

高橋派と青木派の票数の差分で考えるのが、この問題のポイント。
それによって町ごとの高橋氏が演説した時の効率がシンプルに一つの数字で、あわらすことができるようになる。

あとは町ごとの効率を計算して、ソート。
効率が良い町から演説していって、何回演説すれば勝てるかを計算すればよい。

高橋氏が演説をしなかった時、青木派の票はすべて青木氏に投票され、高橋派の票はどちらにも投票されない。
ゆえに

$X = -\displaystyle{ \sum_{j=1}^n Ai }$

Σが出てくると、難しい感じしますが数列Aの全合計というだけ。

町iで高橋氏が演説したとき

$青木派の票数 = \displaystyle{ \sum_{j=1}^n Ai } - Ai$

$高橋派の票数 = Ai + Bi$

ゆえにXについて考えると

$X = Ai + Bi -(\displaystyle{ \sum_{j=1}^n Ai } - Ai) = 2Ai + Bi -\displaystyle{ \sum_{j=1}^n Ai }$

つまり高橋氏が町iで演説したときに変化する $X$ の値は $2Ai + Bi$
$2Ai + Bi$ を町ごとに計算しておいてソート。
効率のよい町から順に演説を行なっていけば、演説の最小回数はわかる。

解説の内容をPythonでコードに落としこんだモノが以下。

公式の解説が、この問題は解説わかりやすい。