B - Bought Review 解説 by evima
HintsHint 0
If you want the average rating to be at least \(3\) stars, adding reviews with \(1\) or \(2\) stars would be a waste.
Hint 1
What does it mean for the average rating to be at least \(3\) stars? Let’s formulate it. (This formulation can explain Hint 0)
Hint 2
Suppose there were originally \(q\) reviews with a total of \(p\) stars.
Furthermore, suppose we add \(B_i\) reviews with \(i\) stars.
In this case, the condition for the average rating to be at least \(3\) stars can be formulated as follows:
\(\displaystyle \frac{p+B_1+2B_2+3B_3+4B_4+5B_5}{q+B_1+B_2+B_3+B_4+B_5} \ge 3\)
From here, proceed with transforming the equation.
Hint 3
By transforming the equation, we obtain the following:
\(p+B_1+2B_2+3B_3+4B_4+5B_5 \ge 3 \times (q+B_1+B_2+B_3+B_4+B_5)\)
\(p-3q-2B_1-B_2+B_4+2B_5 \ge 0\)
From this equation, we can see that adding reviews with \(3\) stars or less is meaningless or harmful.
Continuing with the transformation by setting \(B_1=B_2=B_3=0\), we get \(B_4+2B_5 \ge 3q-p\).
Let’s consider satisfying this equation with the minimum bribe.
Hint 4
Regarding the equation in Hint 3, it can be seen that “adding two \(4\)-star reviews” has the same effect as “adding one \(5\)-star review”.
Hint 5
“Adding two 4-star reviews” has the same effect as “adding one 5-star review.”
In other words, these two actions can be exchanged.
Using this exchange, we can see that (for any additional costs \(P_4, P_5\)) there are not so many optimal candidates for \(B_4, B_5\).
Furthermore, by calculating the necessary costs for several patterns and taking the \(\min\) of them, we can solve this problem.
投稿日時:
最終更新: