ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

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個になります。

 A_{i} = 0 のとき以外は、条件を満たす  A_{j} \frac{m}{A_{i}} を境として、それ以上もしくはそれ以下の範囲にあるものです。これは最初に数列をソートしておけば、やはり二分探索を用いて求めることができます。

f:id:betrue12:20200216234625p:plain

図のように  A_{i} 以降のものは数えてはいけないのと、 \frac{m}{A_{i}} が整数にならない(しかも負の数になる)場合があるため、C++lower_bound などを用いて二分探索するにしてもちょっと実装が難しいです。

※尺取り法でもできますが、この方針で尺取り法をやろうとすると  m の符号によって境界がずれる方向が変わるので非常に面倒でした…

または以下のようにするのも1つの手です。こっちのほうが楽かも。

  1. 右端を考えずに、毎回全ての  A_{i} について計算する。
  2. 同じ要素同士を掛けたものを取り除きたいので、 A_{i}^{2} を全部試して  m 以下だったものの個数だけ引く。
  3. ペアの順番が逆になったものが重複して入っているので、全体を  2 で割る。

これで積が  m 以下となるような要素のペアの個数を求めることができたので、それが  k 以上かどうかを見れば判定問題が解けます。

ACコード

このコードはlower_bound/upper_boundとイレテータの足し引きをゴリゴリに使っているので読みづらいかもしれません…。あとで尺取り法での実装もリンクを貼りたいと思います。→書きましたが、 m の符号で場合分けが必要なのでこの方針だと微妙でした…。