読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

Codeforces Round #204(Div. 1) - A. Jeff and Rounding

練習会に参加して☀0完☀だった。

解法

この問題では、整数部分は必要ないため、小数部分のみについて見ればよい。
まず、簡単のため、全ての数の小数部分が0でない場合を考える。

例えば、N=2, A=[0.1, 0.3, 0.5, 0.7]のとき、この問題の答えは0.4である。
ここで重要なのは、どのようにペアを作って切り上げ/切り下げを行っても、差(答え)は0.4になる、ということである。
なぜなら、どのようなペアを作っても、Aのうち2つは1になり、残り2つは0となるので、その差は  \mathrm{abs}(2 - (0.1 + 0.3 + 0.5 + 0.7)) = 0.4となるからである。
よって、着目すべきは、切り上げられて1となる数が何個あるか、ということである。

ただし注意しなければいけないのは、小数部分が0になる数は切り上げ/切り下げをおこなっても、差が0になる(変わらない)ということである。
これは、以下のように考えることができる

  1. 小数部分が0になる数がk(<= N) 個ある場合
    • N-k個は0か1か(切り上げるか切り捨てるか)どちらかを選ぶことができる(上の例は小数部分が0個の場合であると考えればよい)
    • よって、N-k個〜N個まで1になる場合を全て試し、最小の場合を選べばよい
  2. 小数部分が0になる数がk(> N)個ある場合
    • 小数が0でない数について全て、0か1か選ぶことができる
    • よって、0個〜2N-k個まで、1になる場合を全て試し、最小の場合を選べばよい

具体的には、 \mathrm{min}\{\mathrm{abs}(1となる個数 - 小数部分の合計)\}で求めることができる。

計算量

O(N)

コード

このコードでは、上記のkはcntになっています。

感想など

  • 頑張ってペアを作ろうと頑張っていたけど筋が悪かった
  • 小数じゃなくて整数になおして回答した方が速い。参考: Submission #14038157 - Codeforces
    • 小数: 60ms、整数30ms(100ms未満なので誤差の範囲内かもしれない?)