ABC093 D-Worst Case
D - Worst Case
A*Bより小さな積となる二組の整数のマッチングを最大化する問題です. ただしA,Bを用いてはいけません.
A,Bを用いないことや重複を考えず, まず貪欲にマッチングを作ることを考えます. A*Bが十分大きいとして, ２項(C,D)(C<=Dとしておきます)において例えばC = 1のとき, Dの値としては1,2,3...A*B-1などが考えられます. 貪欲にマッチングを作りたいので, あとで使えないような整数を使う出来る限り厳しい条件をとり, A*B-1をとります. 同様にして C= 2 のときは, (A*B)/2 (小数点切り捨て)を取りたいです. しかし, A*Bより小さいもののマッチングを探しているのに, A*Bが2の倍数のとき2*(A*B/2)はA*Bと等しくなってしまいます. できる限り厳しい条件を取りたいので, A*Bが2で割り切れるときは(A*B/2) - 1を採用することにします.
同じようにしてC = n を考えると,
D = (A*B)/n (A*B % n != 0)
D = (A*B)/n -1 (otherwise)
という式ができます.
C <= Dとなる組を全部列挙して, 対称性からその個数を二倍すれば, だいたい答えに近い値になります.
Cは1から単調に増加し, Dは単調に減少していくため, C <= Dが満たされている境界のCを求めると, C <= Dとなる組を求めたことになります. ループを回していくと, おそらくO(N^(1/2))かかりTLEとなりますが, 単調性から, 二分探索を用いることができ, O(log max(a,b)) で計算できます.
上で作成した組で, (C,C)となる組やA,Bを用いているものを除くことができれば正答が得られます.
(C,C)となるような組の検出は, 返ってってきた境界のCに対してペアをもう一度計算することで確かめられます. 単調性から, C = Dが成り立つのは境界部分でしかありえないからです.
A,Bを用いているものの数は, Cの単調性からC >= AまたはC >= Bであることを確認すればよいです. 多分必ずどちらかは成り立つので, 1は減らすことに鳴ると思います. Dの方では, 実はBにならないようにマッチングをとりなおすことができるので考えなくてもよいです.
