SRM616Div1Medium
解法
TopCoder SRM 616 Div1 Medium ColorfulCoins - kmjp's blog
kmjpさんの記事のお陰でようやく解法を理解できた。
- 最上位を除く各コインについて次の価値のコインの比率を求める。
- 登場した各比率kについて、その比率以下のコイン枚数をX枚としたとき、k^n-1>=Xとなる最小のnを求める。
- nの最大値が答え。
コインの枚数Xを全ての枚数ではなく、その比率以下にできる理由を説明する。
比率の数列が[2 2 2 3 3]でk=3の時を考える。この場合に上記の方法を試すと、比率以下の枚数をすべて数えるので[3 3 3 3 3]を計算していることになる。しかし、これでは実際のケースより少ないクエリ回数で答えが出せてしまう。ここでポイントとなるのは、nの最大値が答えになるという点である。k=2の時を考える。この場合は[2 2 2]となる。この時の最小のクエリ数で[2 2 2 3 3]を満たすことはできる。理由は2の出現回数より3の出現回数の方が少ないので、新しく増えた2を使用できるからである。
逆の場合である[2 2 3 3 3]を考える。この時は[3 3 3 3 3]のクエリ数で[2 2 3 3 3]も満たす。3の出現回数の方が多いので2より少ない1の数が多いからである。
これを拡張することで、nの最大値が答えとなる。
計算量
