Chokudai SpeedRun002 I. カツサンドくんβ

問題

N種類の食べ物があり、食べ物iの体力がAi、攻撃力がBiで与えられる。
この食べ物同士を戦わせ、最強の食べ物を決めたい。

最強の食べ物は、以下のような対戦を行ったとき、どの他の食べ物と戦っても勝利できるような食べ物とする。

食べ物iと食べ物jが対戦する場合、以下のような流れで行われる。
1. 互いに攻撃する。このとき食べ物iの体力はBj減り、食べ物jの体力はBiだけ減る。
2. 体力が0以下になった食べ物が戦闘不能になる
3. いずれの食べ物も戦闘不能になっていない場合は1に戻る
4. 両方が同時に戦闘不能になったら引き分け、片方のみが戦闘不能ならもう片方を処理とする

最強の食べ物を求めよ。

制約

• 1 <= N <= 2*10^5
• 1 <= Ai, Bi <= 10^9
• 入力される値はすべて整数

解法

最強の食べ物が存在する場合は、どう戦っても必ず勝つはずなので、N種類の食べ物が順番に現れて勝ち抜き戦をするような感じで求めればよい。
引き分けの場合は、いったんどちらかを選んでおく。
最後に勝ち抜いた食べ物が最強候補だが、引き分けの食べ物があったかもしれないので、最後に、他のすべての食べ物に勝てるかチェックすればよい。

解法2(未証明)

勝敗判定を考えると、iとjが戦った場合にiが戦闘不能になるまでのターン数は(Ai+Bj-1)/Bj)-1?回なので、iが勝つには「floor( (Ai+Bj-1)/Bj ) > floor( (Aj+Bi-1)/Bi )」である必要がある。
floorを外して小数考えると、整数部分が違う場合はただしく不等号比較ができているが、整数部分が同じ場合にfloorでは等号になるものが不等号の比較になってしまう。
これは、本当は引き分けなのに、どちらか優劣をつけることになるが、上記の解法でのいったんどちらかが勝ち残るのと同じ感じになる。
floorを外して小数で考えて、移項して整理すると「(Ai - 1)*Bi > (Aj - 1)*Bj」である必要がある。
したがって、(Ai-1)*Biでソートしたときに一番大きい値になるものが最強候補といえるので、他のすべての食べ物に勝てるかチェックして答えを求めればよい。