原案、解答、問題文を担当していました。とこはるさんが解法、解答。
まずこの問題、一番辛いところは自炊パワーが自炊でも食堂でも変動する事なのでなんとかします。
自炊パワーは
自炊で+1、食堂で-1ですが、コレを自炊で+2、食堂で変動無し(±0)にしたと考えます。
仮にこのようにすると、i日目、自炊パワーは本来よりi-1高いです。
なので、自炊した場合本来より(i-1)*P高い幸福度を得ます。
このままだと答えはおかしくなりますが、i日目の食堂に事前に(i-1)*Pを足しておきます。
すると、本来より自炊しても食堂に行っても(i-1)*P高い幸福度を得るので、必ず本来より
1*P+2*P+3*P+..+(N-1)*P高い幸福度を得るので、この仮定での幸福度のMaxからコレを引けば正しい答えになります。
自炊パワーが自炊で+2、食堂で変動無しだとすると、どのように解けば良いでしょうか。
これは、自炊で得る幸福度の総和が自炊の回数だけに依存するので、自炊する日数を決めてしまえば残りは食堂を高い順に取ればOKです。
なので、自炊する日数KをK=0,1,2..と決めうちすればどこかで正しい答えが出ます。
色々雑なのでイミワカンナイ場合@yosupotまで
