AtCoder Beginner Contest 155 D - Pairs

D - Pairs

※正直、これがABC-Dとして出るのはここ最近の傾向からすると異常です。じっくり解説を読んで理解するか、どうしても分からなければ温めておくのも手でしょう。

解法

二分探索に落とし込む

与えられた数列などに対して大量の数を計算し、その $k$ 番目の数を求めよ…という問題でよく使うテクニックがあります。これは思いつくのは大変なのでパターンとして覚えてしまいましょう。二分探索です。

判定問題として、

数える対象となる $\frac{N(N-1)}{2}$ 個の数のうち、 $m$ 以下の数は $k$ 個以上あるか？

というものを考えます。もしこれがYesだった場合、 $k$ 番目の数は $m$ 以下です。逆にNoだった場合、 $k$ 番目の数は $m$ より大きくなります。

f:id:betrue12:20200216231301p:plain

二分探索では判定問題が「絶対にYesになる値」と「絶対にNoになる値」を初期値に選びます。判定問題を「対象となる数のうち、 $m$ 以下の数は $k$ 個以上あるか？」とすると、 $m$ が大きいほど条件を満たしやすいので、Yes側の初期値を非常に大きい値、No側の初期値を非常に小さい値にします。そしてこの判定問題がYesになるような最小の整数 $m$ が、求めたい答えになります。

今回の答えは $-10^{9} \le A_{i} \le 10^{9}$ の範囲にある数2つを掛け算した値のどれかなので、絶対値が $10^{18}$ 程度まで大きくなり得ることに注意して初期値を決めましょう。

このタイプの二分探索は「○○の最大値を求めよ」のようなタイプよりも判定条件や初期値の設定がイメージしづらいので、図を使って整理するのがオススメです。では判定問題の解き方を考えましょう。

判定問題を解く

後々のために $A_{i}$ をソートして、小さい方から順に見ていきましょう。対象となるのは異なる2要素の積で、ペアの入れ替えは重複して数えません。そのため要素 $A_{i}$ を見るときには、既に見終わった $i-1$ 番目までの要素 $A_{j}$ のうち、 $A_{i}A_{j} \le m$ となるものの個数を数えます。

この不等式の解き方は、 $A_{i}$ の符号によって場合分けされます。

$A_{i} \gt 0$ のとき、不等式は $A_{j} \le \frac{m}{A_{i}}$ となります。
$A_{i} \lt 0$ のとき、不等式の両辺を負の数で割ると符号が逆転するので、条件は $A_{j} \ge \frac{m}{A_{i}}$ となります。
$A_{i} = 0$ のとき、不等式は $0 \le m$ となってしまいます。つまり $m$ の符号に応じて、条件を満たす $j$ は全部もしくは0個になります。