問題一覧 > 通常問題

No.1365 [Cherry 1st Tune] Whose Fault?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-3}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 28
作問者 : KazunKazun / テスター : Kanten4205Kanten4205 iaNTUiaNTU
2 ProblemId : 5507 / 出題時の順位表
問題文最終更新日: 2021-01-23 01:52:55

注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

お詫び

$A_i, B_i, P_i$ の制約を $10$ 以下にしました. この結果殆どのWAACになりました. 大切なお時間を奪ってしまい申し訳ありませんでした.

問題文

$N$ 人からなるグループがあり, 人 $i$ は最初エネルギーとして $A_i$ を持っている. 機械 $j$ を用いることによって, 人 $X_j$ と, 人 $Y_j$ の間でエネルギーのやり取りが出る. ただし, この機械は使い捨てである. より厳密には, 機械 $j$ を用いることによって, 以下の2つの行動のうち, 一方が1回だけできるようになる.

  • ある正の実数 $g$ を選び, 人 $X_j$ の持っているエネルギーを $g$ 減らし, 人 $Y_j$ の持っているエネルギーを $g$ 増やす.
  • ある正の実数 $g$ を選び, 人 $X_j$ の持っているエネルギーを $g$ 増やし, 人 $Y_j$ の持っているエネルギーを $g$ 減らす.
なお, このエネルギーのやり取りによって, 持っているエネルギーが負になっていてもよい.

このグループのマネージャーであるあなたは $Q$ 個の機械を用いて, $i$ 番目の人のエネルギーをなるべく $B_i$ にしたい. そこで, 以下のように定義される不安度を最小化するように機械を使いたい.

 人 $i$ が持っているエネルギーが $E_i~(i=1, \dots, N)$ のときの不安度は $\displaystyle \sum_{i=1}^N P_i (E_i-B_i)^2$ である.

しかし, この機械は1個ずつしか作れず, また, 作るのに非常に時間がかかる. しかも, 使い捨てなので, 時間と不安度のトレードオフを考慮しなければならない. そこで, $q$ 個目の機械が完成した時点でどのくらい不安度を小さくできるかを考えたい.

より厳密には, $q=1,\dots, Q$ に対して, 以下の問題を解け.

機械$1$, $\dots$, 機械$q$ の $q$ 個の機械のみを用いて実現できる不安度の最小値を求めよ. ただし, 使わない機械があってもよい.

制約

  • $2 \leq N \leq 10^5$
  • $0 \leq A_i \leq 10$
  • $0 \leq B_i \leq 10$
  • $0 \leq P_i \leq 10$
  • $1 \leq Q \leq 2 \times 10^5$
  • $1 \leq X_j, Y_j \leq N$
  • $X_j \neq Y_j$
  • 入力は全て整数.

入力

$N$
$A_1\ \dots\ A_N$
$B_1\ \dots\ B_N$
$P_1\ \dots\ P_N$
$Q$
$X_1\ Y_1$
$\vdots$
$X_Q\ Y_Q$

出力

$Q$ 行出力せよ. 上から $n$ 行目では, $q=n$ としたときの答えを出力せよ. 各出力について, 正しい値との絶対誤差または相対誤差が $10^{-3}$ 以下ならば, 正解と判定される.

サンプル

サンプル1
入力
3
3 5 4
4 4 5
1 1 1
3
1 2
2 1
1 3
出力例
1.0
1.0
0.3333333333333333

  • $q=1$ のときを考える. 機械 $1$ を用いて, 人 $1$ から人 $2$ にエネルギーを $1$ 移動させると, 不安度は $(4-4)^2+(4-4)^2+(4-5)^2=1$ になり, これが最小値である.
  • $q=2$ のとき, $q=1$ のときと同様にして, 不安度の最小値は $1$ である. 必ずしも全ての機械を用いる必要はない.
  • $q=3$ のとき, 以下のようにして不安度を $\dfrac{1}{3}$ にすることができる. ここで, $g$ として選ぶ正の実数 $g$ は整数である必要はないことに注意せよ.
    • 機械$3$ を用いて, 人$1$ から 人$3$ にエネルギーを $\dfrac{2}{3}$ 移動させる.
    • 機械$1$ を用いて, 人$2$ から 人$1$ にエネルギーを $\dfrac{4}{3}$ 移動させる.

サンプル2
入力
10
0 1 2 3 4 5 0 1 2 3
5 4 3 2 1 5 4 3 2 1
1 2 3 4 5 1 2 3 4 5
7
1 8
2 10
4 9
5 6
6 2
7 5
3 8
出力例
158.75
122.17857142857143
120.17857142857143
82.67857142857143
75.85526315789474
43.41666666666667
42.06666666666667
サンプル3
入力
26
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3
20 24
24 26
26 20
出力例
0.0
0.0
0.0

このグループに不安はありません.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。