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

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

問題

Problem - 351A - Codeforces

解法

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

例えば、N=2, A=[0.1, 0.3, 0.5, 0.7]のとき、この問題の答えは0.4である。
ここで重要なのは、どのようにペアを作って切り上げ/切り下げを行っても、差(答え)は0.4になる、ということである。
なぜなら、どのようなペアを作っても、Aのうち2つは1になり、残り2つは0となるので、その差は となるからである。
よって、着目すべきは、切り上げられて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になる場合を全て試し、最小の場合を選べばよい

具体的には、で求めることができる。

計算量

O(N)

コード

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

感想など

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