うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

Advent Calendar Contest 2017 C hel__world (2) 解説（？）

Advent Calender Contest yukicoder

解説 Advent Calendar 2017

これは解説 Advent Calendar 2017 の 4日めの記事です。
adventar.org
まだまだ全然埋まってないので助けてください。

解説（？）

問題はこちら。テスターをしました。
No.603 hel__world (2) - yukicoder


まずは、嘘が見つかってしまい大変申し訳ありませんでした。


さて、問題についてですが、本質というかもはや 99% は
{\displaystyle \prod_{1 \leq k \leq n} {}_{x_k}\mathrm{C}_{a_k}} を最大化するような {X = \{ x_1, ... , x_n \} \ \sum X = Const}
を探す問題になります（詳しい式は解説や元ネタ問題の解説の方を参照してください）。

https://yukicoder.me/problems/no/295/editorial の priority queue 解の方を読んでもらえばわかりますが、{x_k} の値を 1 増やす場合、全体の値は {\displaystyle \frac{x_k + 1}{x_k - a_k + 1}} 倍になります。そしてこれらは {x_k} の値が増えていくと単調に減少していくので、つまり今選べる中で一番大きいものを貪欲にとっていけば良い、ということがわかり、priority queue 解が生まれます。

ここで、お、これ二分探索したくない？ と思うはずです。きっとそう思うのです。
でも、実はそこからの道のりが意外と長いです。

今回は、解説というより、方針が思い浮かんでからここがつらかったダイジェスト、みたいな感じでお送りしたいと思っております。

（実は writer 解はこれとは違いますが、自分にはよくわからないです。）

二分探索の中で二分探索？

ここはそこまで大変とかいう話ではないですが、まず一つ重要なところだと思うので。
二分探索をするとなると、まずは、ある実数 {m} に対して、 {\displaystyle \frac{x + 1}{x - a + 1} > m > \frac{x + 2}{x - a + 2}} となるような {x} を探したい気持ちになります。
もちろんこれは二分探索をしても良いのですが（多分）、{c = x - a + 1} とおくと、これはそのままそこを使う回数（つまり求めるもの）と一致していて、かつ上の式が
{\displaystyle \frac{a + c}{c} > m > \frac{a + c + 1}{c + 1} \Leftrightarrow \frac{a}{c} > m - 1 > \frac{a}{c + 1} \Leftrightarrow c = \lfloor \frac{a}{m - 1} \rfloor}
となり、定数時間で求められるようになります。

分数の比較

二分探索をする上で分数の比較が必要不可欠ですが、普通にかけ算をしてしまうとオーバーフローしてしまいます。
そこで、2 つの分数 {\displaystyle \frac{a}{b}, \frac{c}{d}} に対し、

  1. {a / b} と {c / d} を比較する
  2. 同じだった場合、その値を {e} とおき、{\displaystyle \frac{d}{c - d \cdot e}, \frac{b}{a - b \cdot e}} に対して 1. を行う

とすると、log 回くらいで比較が完了します（今回は分母と分子の差が小さいことが保証されているのでもう少し早そうですし、オーバーフローしないところまで小さくなったらかけ算で比較してしまうと良いです）。

combination の計算

これはみなさん大丈夫だと思うので省略します。前もって階乗とその逆数を計算しておいて、n を Mod 取って n - k を Mod 取ったものより小さくなったら 0 、そうでなければその間を計算して k! で割る、みたいな感じ。

精度が足りない

これで全て大丈夫、かと思いきや、このままだとまだ通りません。というのも、m の値が 1 付近で精度を求められ、 1.00000000000000000114514 みたいな数を扱う羽目になります。でもそこについては簡単に対処できて、m ではなく m - 1 の値を決めることにより探索範囲を [1, 1e6] から [0, 1e6] に変更して対処できます（1 付近でないところで精度を求められると死にますが、恐らく大丈夫だろうという結論になりました）。あ、ちなみにもちろん long double じゃないと精度が足りません。

時間が足りない

これで今度こそ大丈夫、かと思いきやそうではありません。二分探索時に要求される精度が高いのでどうしてもループ回数が多くなってしまい、微妙に間に合いません（高速化のプロなら間に合うかもしれないです）。
そこで、二分探索をする範囲を絞ります。
上で定義した {c} と式変形で得られた式を用いて、
{\displaystyle a_k > (m - 1) \cdot c_k > a_k - (m - 1) \\ \displaystyle \Rightarrow \sum a_k > (m - 1) \cdot \sum c_k > \sum a_k - n \cdot (m - 1) \\ \displaystyle \Rightarrow \frac{\sum a_k}{\sum c_k} > m - 1 > \frac{\sum a_k}{n + \sum c_k}}
とすることができ、これで二分探索の範囲を絞ることができ（自分の雑な計算では二分探索のループが最大 40 回程度で終わるという結論になりましたが本当かどうかは知りません）、これでようやく通るようになりました。


という感じで、テスターをしながらとても大変だなぁと思っていました。

難易度設定については、そもそもネタ元問題が★5 あるかなぁという気持ちはあって、ネタ元★4 今回の★5 くらいが適正かなぁと（個人的には）思いました。