問題一覧 > 通常問題

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

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-3}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 34
作問者 : 👑 Kazun / テスター : Kanten4205 iaNTU
お気に入りにしたユーザー ProblemId : 5507 / 自分の提出
問題文最終更新日: 2021-01-23 01:52:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 279 (Zelkova and Cherry) (順位表) の他の問題:

Note

The problems of yukicoder contest 279 (Zelkova and Cherry) are not sorted in order of difficulty. Therefore, we strongly recommend choosing which problems to attempt based on publicly available information, such as the problem statements, the number of stars indicating difficulty, and the number of solvers.

Apology

The constraints on $A_i, B_i, P_i$ have been changed to at most $10$. As a result, most WA verdicts have become AC. We apologize for taking up your valuable time.

Problem Statement

There is a group of $N$ people, and person $i$ initially has energy $A_i$. By using machine $j$, energy can be exchanged between person $X_j$ and person $Y_j$. However, each machine is single-use. More precisely, using machine $j$ allows you to perform one of the following 2 actions, exactly once.

  • Choose a positive real number $g$, decrease the energy of person $X_j$ by $g$, and increase the energy of person $Y_j$ by $g$.
  • Choose a positive real number $g$, increase the energy of person $X_j$ by $g$, and decrease the energy of person $Y_j$ by $g$.
Note that a person's energy may become negative through these exchanges.

You are the manager of this group, and you want to use the $Q$ machines to bring the energy of the $i$-th person as close to $B_i$ as possible. To this end, you want to use the machines so as to minimize the anxiety level, defined as follows.

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

However, these machines can only be built one at a time, and building each one takes a very long time. Moreover, since they are single-use, the trade-off between time and anxiety level must be taken into account. Therefore, you want to find out how small the anxiety level can be made at the point when the $q$-th machine is completed.

More precisely, solve the following problem for $q=1,\dots, Q$.

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

Constraints

  • $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$
  • All input values are integers.

Input

$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$

Output

Output $Q$ lines. On the $n$-th line from the top, output the answer for $q=n$. Each output is judged as correct if its absolute or relative error from the correct value is at most $10^{-3}$.

Sample

Sample 1
Input
3
3 5 4
4 4 5
1 1 1
3
1 2
2 1
1 3
Sample Output
1.0
1.0
0.3333333333333333

  • Consider the case $q=1$. Using machine $1$ to move energy $1$ from person $1$ to person $2$, the anxiety level becomes $(4-4)^2+(4-4)^2+(4-5)^2=1$, which is the minimum.
  • For $q=2$, in the same way as for $q=1$, the minimum anxiety level is $1$. It is not necessary to use all the machines.
  • For $q=3$, the anxiety level can be made $\dfrac{1}{3}$ as follows. Note here that the positive real number $g$ chosen as $g$ does not have to be an integer.
    • Using machine $3$, move energy $\dfrac{2}{3}$ from person $1$ to person $3$.
    • Using machine $1$, move energy $\dfrac{4}{3}$ from person $2$ to person $1$.

Sample 2
Input
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
Sample Output
158.75
122.17857142857143
120.17857142857143
82.67857142857143
75.85526315789474
43.41666666666667
42.06666666666667
Sample 3
Input
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
Sample Output
0.0
0.0
0.0

This group has no anxiety.

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