ABC224 G - Roll or Increment (600)
数を大きくしてから振り直すのは無駄なので振り直すのは最初のみ
$ S \le Tなら振り直しをしない場合の期待値は$ (T-S)A
$ S \gt Tなら振り直すしか無い
振り直した後の費用の期待値$ E = \frac{AT(T-1)}{2T} \frac{T}{N} + \frac{N-T}{N}(E+B)
これに更に振り直し一回のコスト$ Bがかかる
整理すると、$ E = \frac{A(T-1)}{2} + \frac{B(N-T)}{T}
実際にはある$ X以下の場合には振り直した方が期待値が小さい可能性がある
$ X以下で振り直す場合、$ T-X = dとして$ E = \frac{Ad(d-1)}{2d} \frac{d}{N} + \frac{N-d}{N}(E+B)
整理すると、$ E = A(d-1) - B + \frac{2BN}{d}
これを全ての$ Xで試すと$ \mathcal{O}(N)になり間に合わない
相加相乗平均から$ Ad = \frac{2BN}{d}の時最小になるので、$ d = \sqrt{\frac{2BN}{A}}の前後の整数が答え
コンテスト中はBの項は消したがAの項を消し忘れ$ A(d-1) = \frac{2BN}{d}を求めてWA
この求めたdの周辺でだけ上の式を当てはめると$ \mathcal{O}(1)になる