No.1365 [Cherry 1st Tune] Whose Fault?
タグ : / 解いたユーザー数 34
作問者 : 👑
Kazun
/ テスター :
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, mostWA 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$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。