はてなブックマーク

この記事は Dwango Programming Contest 6th でNosubをやってしまったお詫びとして書かれたものです。このコンテストのB問題もこの記事の中で解説されます。 まず、この記事で説明する「主客転倒」とは、 得点 \(A_i\) をいくつか足した和で表される総得点 \(S_i\) が沢山あって、ありうる全ての場合について \(S_i\) を足し合わせたいときに、 \(A_i\) が何回足されるかを考えるテク です。これだけ言われてもよくわからないと思うので、今から具体例をいくつか挙げて説明します。 まずは簡単な例から。 物理好きさんはあるゲームをした。 \(1\) 回目では \(A_1+A_2+A_3+A_4\) 点を得た。 \(2\) 回目では \(A_1+A_3+A_4\) 点を得た。 \(3\) 回目では \(A_2+A_3+A_4\) 点を得た。 \(4\)