B - Bought Review Editorial
by 
physics0523
ヒント
Hint 0
平均評価を星 \(3\) 以上にしたい状況で、星 \(1,2\) のレビューを追加することは無駄でしょう。
Hint 1
平均評価が星 \(3\) 以上であるとはどのようなことでしょうか。立式してみましょう。 (この立式によって、 Hint 0 に説明を与えることができます)
Hint 2
もともと \(q\) 件のレビューがついており、星の合計が \(p\) 個であったとしましょう。
更に、星 \(i\) のレビューを \(B_i\) 件追加したとしましょう。
このとき、平均評価が星 \(3\) 以上であるということを以下のように立式できます。
\(\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\)
ここから式変形を進めてください。
Hint 3
式変形によって、以下を得ます。
\(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\)
この式より、星 \(3\) 以下のレビューを追加することは無意味または有害であることがわかります。
以降、 \(B_1=B_2=B_3=0\) として更に変形すると \(B_4+2B_5 \ge 3q-p\) を得ます。
最小の賄賂でこの式を満たすことを考えましょう。
Hint 4
Hint 3 の式について、「星 \(4\) のレビューを \(2\) 件追加する」ことと「星 \(5\) のレビューを \(1\) 件追加する」ことは同じ効果を持つことがわかります。
Hint 5
『「星 \(4\) のレビューを \(2\) 件追加する」ことと「星 \(5\) のレビューを \(1\) 件追加する」ことが同じ効果を持つ 』
これを換言すると、この \(2\) つの操作を交換してもよいと言い換えられます。
この交換を用いると、 ( どのような追加費用 \(P_4,P_5\) に対しても ) 最適な \(B_4, B_5\) の候補はそう多くないことがわかります。
さらに言うと、いくつかのパターンについて必要な費用を求め、それらの \(\min\) を取ることでこの問題に正解できます。
posted:
last update: