Cork

banbooooのブログ

統計、機械学習、数学に関する記事を投稿します。

ARC094/ABC093 D:Worst Case

700点問題のD問題。むずかった。
D - Worst Case
高橋君のとった得点を A,B ( A \leq B) とする。
高橋君よりスコアの小さい最大の人数を求めたいので、1つ目のコンテストが高いスコアならば、2回目は低いスコア(逆もしかり)というように掛け算のペアを作ってあげる。(考察1)
(わからなければ解説放送へ)
www.youtube.com
高橋君よりスコアが小さい人のスコア a,b ( a \leq b) は必ず a < A または  b < B を満たすので
まず、 a < A の場合を考えてみる。
(考察1)より、以下のようにペアを考えることができる。
f:id:banboooo:20180408143002j:plain
すると、この場合はすべてのペアの積がABより小さくなることがわかる。
次に b < B の場合を考えてみる。先ほどのように 1 \sim (B-1) を元に、対応する A より大きい数を考えても、必ずABより大きいことが保証される数列が見つからない。
ここで発想を転換して、(A+1) \sim を元に、対応する数を考える。すると、積の最大値がABを超えない範囲で数列の長さを最大にする問題と捉えることができる。
ここまでを整理すると以下の図になる。
f:id:banboooo:20180408152026j:plain
ここからは2つほど解法があると思ったのだが、2つ目の方は実装で挫折してしまった。1つ目は、editorialの方法。2つ目は2分探索と3分探索を組み合わせる方法。
考え方などで間違っていたら教えていただきたいです。

1.editorialの方法
https://beta.atcoder.jp/contests/arc094/submissions/2325009
 C^2 < AB を満たす C を取ると、 C(C+1) または  C^2 が積の最大値となることを利用する方法。
これは掛け算のペアの和が常に一定ならば
ペアの数が同じくらいの大きさの時に、積の値が最大となるからである。
さらに例外的に、 A = B の時と  A+1 = B の時は、 C = A となってしまうので、別で処理しないといけない。
これを踏まえると以下のように考えることができる。


2.三分探索 & 二分探索の方法 (仮)
https://beta.atcoder.jp/contests/arc094/submissions/2325717 <- 不正解になってしまった提出。
 C の値をとることに気づかない場合は、こっち。
積の最大値を求めたいため、探索をするが逐次探索では当然間に合わない。
そこで、積の値の関数の形に注目してみると上凸の関数になっているはずである。

こういう時は、三分探索を使えば、極値、今回で言えば積の最大値を非常に効率よく求められる。
極値 Xの関数と見れば、この関数は単調非減少の関数なので、こちらは二分探索でXを定めてあげれば答えがもとまる。