問題
結論
ピックした2人「人$i$と人$j$」に対して下記の比較をするようにカスタムしたソートを実装します。これでソートすれば題意を満たす順にソートできます。
- $A_i(A_j + B_j) - A_j(A_i + B_i) > 0$ → 人$i$のほうが前
- $A_i(A_j + B_j) - A_j(A_i + B_i) < 0$ → 人$j$のほうが前
- $A_i(A_j + B_j) - A_j(A_i + B_i) = 0$ → 人の番号がより小さいほうが前
なぜこれでOKなのか、考察で説明してきます。
考察
「成功率が高い順→番号が小さい順」の優先順位でソートしてくださいという問題です。人$i$の成功率が$\dfrac{A_i}{A_i + B_i}$と問題文で定義されています。この定義に従ってそれぞれの成功率を求めてソートをかけていけば良さそうな気がします。ところが、成功率は多くの場合小数で出てきます。そのため、誤差が生じてWAになる可能性があります。うまく工夫して小数が発生することなくソートをかけることができないか考えていきたいです。
ところで、配列のソートは2つの要素をピックして比較することを繰り返すことで成り立っています。ソートを標準で備えているプログラミング言語については、「ピックした2つの要素をどのように比較するか」をカスタムできる仕組みを備えていることがほとんどです。C++の場合、下記の記事が参考になります。
この比較をカスタムすることで小数が発生しないようにできるか考えていきます。
ピックした2人を「人$i$と人$j$」とします。それぞれの成功率は$\dfrac{A_i}{A_i + B_i}$と$\dfrac{A_j}{A_j + B_j}$です。今回の問題は成功率がソートに関わってきます。そこで、成功率を比較していきます。比較するときは、2つ差と0との大小を考えればいいです。2つの差を通分してみましょう。
$$\dfrac{A_i}{A_i + B_i} - \dfrac{A_j}{A_j + B_j} = \dfrac{A_i(A_j + B_j) - A_j(A_i + B_i)}{(A_i + B_i)(A_j + B_j)}$$
通分すると上記のように1つの分数になります。これが0より大きいと人$i$の成功率のほうがより高く、0より小さいと人$j$の成功率のほうがより高いということになります。肝心なのは0との大小関係になってきますので、分数の分子のみに注目すれば良いことになります。分子のみで0との大小関係を考えれば、小数を発生させることなく比較できそうです。ここまでから、$A_i(A_j + B_j) - A_j(A_i + B_i)$と0との大小関係で比較するようにカスタムしたソートを用意すれば良いことがわかりました。
あとは$A_i(A_j + B_j) - A_j(A_i + B_i) = 0$のケースも注意し、比較をカスタムしてソートすれば題意を満たす順になります。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。
参考